Dynamic programming in transposition and time-warp invariant polyphonic content-based music retrieval

Mika Laitinen, Kjell Lemström

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


We consider the problem of transposition and time-warp invariant (TTWI) polyphonic content-based music retrieval (CBMR) in symbolically encoded music. For this setting, we introduce two new algorithms based on dynamic programming. Given a query point set, of size m, to be searched for in a database point set, of size n, and applying a search window of width w, our algorithms run in time O(mnw) for finding exact TTW Ioccurrences, and O(mnw2) for partial occurrences. Our new algorithms are computationally more efficient as their counterparts in the worst case scenario. More importantly, the elegance of our algorithms lies in their simplicity: they are much easier to implement and to understand than the rivalling sweepline-based algorithms. Our solution bears also theoretical interest. Dynamic programming has been used in very basic content-based retrieval problems, but generalizing them to more complex cases has proven to be challenging. In this special, seemingly more complex case, however, dynamic programming seems to be a viable option.
OtsikkoProceedings of the 12th International Society for Music Information Retrieval Conference
TilaJulkaistu - 2011
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa

Siteeraa tätä