Abstract
This paper presents an algorithm for the time-scaled repeated pattern discovery problem in symbolic music. Given a set of n notes represented as geometric points, the algorithm reports all time-scaled repetitions in the point set. The idea of the algorithm is to use an onset-time-pair representation of music, which reduces the musical problem of finding repeated patterns to the geometric problem of detecting maximal point sets where all points are located on one line. The algorithm works in 𝑂(𝑛^4log𝑛) time, which is almost optimal because the size of the output can be Θ(𝑛^4). We also experiment with the algorithm using real musical data, which shows that when suitable heuristics are used to restrict the search, the algorithm works efficiently in practice and is able to find small sets of potentially interesting repeated patterns.
| 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, J Kastine, E Lluis-Puebla, B Milam |
| Number of pages | 12 |
| Publisher | Springer LNCS |
| Publication date | 2022 |
| Pages | 168-179 |
| 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
- 113 Computer and information sciences
- Music pattern discovery
- Transposition and time-scaling invariance
- Geometric algorithms