Flexible and Efficient Bit-Parallel Techniques for Transposition Invariant Approximate Matching in Music Retrieval

Kjell Lemström, Gonzalo Navarro

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


Recent research in music retrieval has shown that a combinatorial approach to the problem could be fruitful. Three distinguishing requirements of this particular problem are (a) approximate searching permitting missing, extra, and distorted notes, (b) transposition invariance, to allow matching a sequence that appears in a different scale, and (c) handling polyphonic music. These combined requirements make up a complex combinatorial problem that is currently under research. On the other hand, bit-parallelism has proved a powerful practical tool for combinatorial pattern matching, both flexible and efficient. In this paper we use bit-parallelism to search for several transpositions at the same time, and obtain speedups of O(w/logk) over the classical algorithms, where the computer word has w bits and k is the error threshold allowed in the match. Although not the best solution for the easier approximation measures, we show that our technique can be adapted to complex cases where no competing method exists, and that are the most interesting in terms of music retrieval.
OtsikkoInternational Symposium on String Processing and Information Retrieval
ToimittajatMario A. Nascimento, Edleno S. de Moura, Arlindo L. Oliveira
ISBN (painettu)978-3-540-20177-9
ISBN (elektroninen)978-3-540-39984-1
TilaJulkaistu - 2003
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa


NimiLecture notes in computer science
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Siteeraa tätä