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.
| Original language | English |
|---|---|
| Title of host publication | MATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022) : Proc. 8th International MCM Conference, Atlanta |
| Editors | M Montiel, O A Agustín-Aquino, F Gómez, F Kastine, J Lluis-Puebla, E Milam |
| Number of pages | 12 |
| Publisher | Springer LNCS |
| Publication date | 2022 |
| Pages | 180-191 |
| ISBN (Print) | 978-3-031-07014-3 |
| ISBN (Electronic) | 978-3-031-07015-0 |
| DOIs | |
| Publication status | Published - 2022 |
| MoE publication type | A4 Article in conference proceedings |
| Event | International Conference on Mathematics and Computation in Music - Atlanta, United States Duration: 21 Jun 2022 → 24 Jun 2022 Conference number: 8 |
Publication series
| Name | Lecture Notes in Computer Science book series (LNAI) |
|---|---|
| Volume | 13267 |
Fields of Science
- 6131 Theatre, dance, music, other performing arts
- 113 Computer and information sciences
- Pattern discovery
- SIA algorithms
- Memory usage