Flexible music retrieval in sublinear time

Kimmo Fredriksson, Veli Mäkinen, Gonzalo Navarro

Tutkimustuotos: ArtikkelijulkaisuArtikkeliTieteellinenvertaisarvioitu

Kuvaus

Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases.
Alkuperäiskielienglanti
LehtiInternational Journal of Foundations of Computer Science
Vuosikerta17
Numero6
Sivut1345-1364
Sivumäärä20
ISSN0129-0541
DOI - pysyväislinkit
TilaJulkaistu - 2006
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä, vertaisarvioitu

Lainaa tätä

Fredriksson, Kimmo ; Mäkinen, Veli ; Navarro, Gonzalo. / Flexible music retrieval in sublinear time. Julkaisussa: International Journal of Foundations of Computer Science. 2006 ; Vuosikerta 17, Nro 6. Sivut 1345-1364.
@article{81a74b1cc35b447cb74496755042b670,
title = "Flexible music retrieval in sublinear time",
abstract = "Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases.",
author = "Kimmo Fredriksson and Veli M{\"a}kinen and Gonzalo Navarro",
year = "2006",
doi = "10.1142/S0129054106004455",
language = "English",
volume = "17",
pages = "1345--1364",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "WORLD SCIENTIFIC PUBL CO PTE LTD",
number = "6",

}

Flexible music retrieval in sublinear time. / Fredriksson, Kimmo; Mäkinen, Veli; Navarro, Gonzalo.

julkaisussa: International Journal of Foundations of Computer Science, Vuosikerta 17, Nro 6, 2006, s. 1345-1364.

Tutkimustuotos: ArtikkelijulkaisuArtikkeliTieteellinenvertaisarvioitu

TY - JOUR

T1 - Flexible music retrieval in sublinear time

AU - Fredriksson, Kimmo

AU - Mäkinen, Veli

AU - Navarro, Gonzalo

PY - 2006

Y1 - 2006

N2 - Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases.

AB - Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases.

U2 - 10.1142/S0129054106004455

DO - 10.1142/S0129054106004455

M3 - Article

VL - 17

SP - 1345

EP - 1364

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 6

ER -