On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery

Antti Laaksonen; Kjell Lemström

doi:10.1007/978-3-031-07015-0_15

On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery

Tietojenkäsittelytieteen osasto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

SIA is a fundamental algorithm in symbolic musical pattern discovery, which reports all maximal translatable patterns in a point set. The original SIA algorithm requires 𝑂(𝑘𝑛^2log𝑛) time and 𝑂(𝑘𝑛^2) space, where n is the number of points in the data set, and k is the number of coordinates in each point. In this paper, we present a sweepline algorithm that shares the running time of SIA but requires only O(kn) space, enabling to process of larger data sets without running out of memory. Since SIA is the first step in many pattern discovery tasks, our new algorithm can have a broad impact. For example, we discuss the problem of finding all occurrences of maximal translatable patterns with specific properties. We also compare the algorithms in practice and show that reduced memory usage can benefit real data sets.

Alkuperäiskieli	englanti
Otsikko	MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022) : Proc. 8th International MCM Conference, Atlanta
Toimittajat	M Montiel, O A Agustín-Aquino, F Gómez, F Kastine, J Lluis-Puebla, E Milam
Sivumäärä	12
Kustantaja	Springer LNCS
Julkaisupäivä	2022
Sivut	180-191
ISBN (painettu)	978-3-031-07014-3
ISBN (elektroninen)	978-3-031-07015-0
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-031-07015-0_15
Tila	Julkaistu - 2022
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Conference on Mathematics and Computation in Music - Atlanta, Yhdysvallat (USA) Kesto: 21 kesäk. 2022 → 24 kesäk. 2022 Konferenssinumero: 8

Julkaisusarja

Nimi	Lecture Notes in Computer Science book series (LNAI)
Vuosikerta	13267

Tieteenalat

6131 Teatteri, tanssi, musiikki, muut esittävät taiteet
113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.1007/978-3-031-07015-0_15

Siteeraa tätä

Laaksonen, A., & Lemström, K. (2022). On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery. teoksessa M. Montiel, O. A. Agustín-Aquino, F. Gómez, F. Kastine, J. Lluis-Puebla, & E. Milam (Toimittajat), MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022): Proc. 8th International MCM Conference, Atlanta (Sivut 180-191). ( Lecture Notes in Computer Science book series (LNAI); Vuosikerta 13267). Springer LNCS. https://doi.org/10.1007/978-3-031-07015-0_15

Laaksonen, Antti ; Lemström, Kjell. / On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery. MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022): Proc. 8th International MCM Conference, Atlanta. Toimittaja / M Montiel ; O A Agustín-Aquino ; F Gómez ; F Kastine ; J Lluis-Puebla ; E Milam. Springer LNCS, 2022. Sivut 180-191 ( Lecture Notes in Computer Science book series (LNAI)).

@inproceedings{d3cb6e87e01b4bd8a41662d882dcf065,

title = "On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery",

abstract = "SIA is a fundamental algorithm in symbolic musical pattern discovery, which reports all maximal translatable patterns in a point set. The original SIA algorithm requires 푂(푘푛^2log푛) time and 푂(푘푛^2) space, where n is the number of points in the data set, and k is the number of coordinates in each point. In this paper, we present a sweepline algorithm that shares the running time of SIA but requires only O(kn) space, enabling to process of larger data sets without running out of memory. Since SIA is the first step in many pattern discovery tasks, our new algorithm can have a broad impact. For example, we discuss the problem of finding all occurrences of maximal translatable patterns with specific properties. We also compare the algorithms in practice and show that reduced memory usage can benefit real data sets.",

keywords = "6131 Theatre, dance, music, other performing arts, 113 Computer and information sciences, Pattern discovery, SIA algorithms, Memory usage",

author = "Antti Laaksonen and Kjell Lemstr{\"o}m",

year = "2022",

doi = "10.1007/978-3-031-07015-0_15",

language = "English",

isbn = "978-3-031-07014-3",

series = " Lecture Notes in Computer Science book series (LNAI)",

publisher = "Springer LNCS",

pages = "180--191",

editor = "M Montiel and Agust{\'i}n-Aquino, {O A} and F G{\'o}mez and F Kastine and J Lluis-Puebla and E Milam",

booktitle = "MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022)",

address = "Switzerland",

note = "International Conference on Mathematics and Computation in Music, MCM ; Conference date: 21-06-2022 Through 24-06-2022",

}

Laaksonen, A & Lemström, K 2022, On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery. julkaisussa M Montiel, OA Agustín-Aquino, F Gómez, F Kastine, J Lluis-Puebla & E Milam (toim), MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022): Proc. 8th International MCM Conference, Atlanta. Lecture Notes in Computer Science book series (LNAI), Vuosikerta 13267, Springer LNCS, Sivut 180-191, International Conference on Mathematics and Computation in Music, Atlanta, Yhdysvallat (USA), 21/06/2022. https://doi.org/10.1007/978-3-031-07015-0_15

On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery. / Laaksonen, Antti ; Lemström, Kjell.

MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022): Proc. 8th International MCM Conference, Atlanta. toim. / M Montiel; O A Agustín-Aquino; F Gómez; F Kastine; J Lluis-Puebla; E Milam. Springer LNCS, 2022. s. 180-191 ( Lecture Notes in Computer Science book series (LNAI); Vuosikerta 13267).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

TY - GEN

T1 - On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery

AU - Laaksonen, Antti

AU - Lemström, Kjell

N1 - Conference code: 8

PY - 2022

Y1 - 2022

N2 - SIA is a fundamental algorithm in symbolic musical pattern discovery, which reports all maximal translatable patterns in a point set. The original SIA algorithm requires 푂(푘푛^2log푛) time and 푂(푘푛^2) space, where n is the number of points in the data set, and k is the number of coordinates in each point. In this paper, we present a sweepline algorithm that shares the running time of SIA but requires only O(kn) space, enabling to process of larger data sets without running out of memory. Since SIA is the first step in many pattern discovery tasks, our new algorithm can have a broad impact. For example, we discuss the problem of finding all occurrences of maximal translatable patterns with specific properties. We also compare the algorithms in practice and show that reduced memory usage can benefit real data sets.

AB - SIA is a fundamental algorithm in symbolic musical pattern discovery, which reports all maximal translatable patterns in a point set. The original SIA algorithm requires 푂(푘푛^2log푛) time and 푂(푘푛^2) space, where n is the number of points in the data set, and k is the number of coordinates in each point. In this paper, we present a sweepline algorithm that shares the running time of SIA but requires only O(kn) space, enabling to process of larger data sets without running out of memory. Since SIA is the first step in many pattern discovery tasks, our new algorithm can have a broad impact. For example, we discuss the problem of finding all occurrences of maximal translatable patterns with specific properties. We also compare the algorithms in practice and show that reduced memory usage can benefit real data sets.

KW - 6131 Theatre, dance, music, other performing arts

KW - 113 Computer and information sciences

KW - Pattern discovery

KW - SIA algorithms

KW - Memory usage

U2 - 10.1007/978-3-031-07015-0_15

DO - 10.1007/978-3-031-07015-0_15

M3 - Conference contribution

SN - 978-3-031-07014-3

T3 - Lecture Notes in Computer Science book series (LNAI)

SP - 180

EP - 191

BT - MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022)

A2 - Montiel, M

A2 - Agustín-Aquino, O A

A2 - Gómez, F

A2 - Kastine, F

A2 - Lluis-Puebla, J

A2 - Milam, E

PB - Springer LNCS

T2 - International Conference on Mathematics and Computation in Music

Y2 - 21 June 2022 through 24 June 2022

ER -

Laaksonen A , Lemström K. On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery. julkaisussa Montiel M, Agustín-Aquino OA, Gómez F, Kastine F, Lluis-Puebla J, Milam E, toimittajat, MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022): Proc. 8th International MCM Conference, Atlanta. Springer LNCS. 2022. s. 180-191. ( Lecture Notes in Computer Science book series (LNAI)). doi: 10.1007/978-3-031-07015-0_15