Exact and approximate rhythm matching algorithms

Joseph W T CHAN, Costas S. Iliopoulos, Spiros Michalakopoulos*, M. Sohel Rahman

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


An interesting problem in music information retrieval is to classify songs according to rhythms. A rhythm is represented by a sequence of "Quick" (Q) and "Slow" (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. Christodoulakis et al. presented an efficient algorithm that can be used to classify musical sequences according to rhythms. In this article, the above algorithm is implemented, along with a naive brute force algorithm to solve the same problem. The theoretical time complexity bounds are analyzed with the actual running times achieved by the experiments, and the results of the two algorithms are compared. Furthermore, new efficient algorithms are presented that take temporal errors into account. This, the approximate pattern matching version, could not be handled by the algorithms previously presented. The running times of two algorithmic variants are analyzed and compared and examples of their implementation are shown.

Original languageEnglish
Pages (from-to)149-158
Number of pages10
JournalInternational Journal on Digital Libraries
Issue number2-3
Publication statusPublished - Aug 2012

Scopus Subject Areas

  • Library and Information Sciences

User-Defined Keywords

  • Music information retrieval
  • Pattern matching
  • Quick-slow
  • Rhythm


Dive into the research topics of 'Exact and approximate rhythm matching algorithms'. Together they form a unique fingerprint.

Cite this