Transposition and Time-Scaling Invariant Algorithm for Detecting Repeated Patterns in Polyphonic Music

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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 languageEnglish
Title of host publicationMATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022) : Proc. 8th International MCM Conference, Atlanta
EditorsM Montiel, O A Agustín-Aquino, F Gómez, J Kastine, E Lluis-Puebla, B Milam
Number of pages12
PublisherSpringer LNCS
Publication date2022
ISBN (Print)978-3-031-07014-3
ISBN (Electronic)978-3-031-07015-0
Publication statusPublished - 2022
MoE publication typeA4 Article in conference proceedings
EventInternational Conference on Mathematics and Computation in Music - Atlanta, United States
Duration: 21 Jun 202224 Jun 2022
Conference number: 8

Publication series

Name Lecture Notes in Computer Science book series (LNAI)

Fields of Science

  • 113 Computer and information sciences
  • Music pattern discovery
  • Transposition and time-scaling invariance
  • Geometric algorithms

Cite this