Abstract
We present MSM, a new maximal subset matching algorithm,
for MIR at score level with polyphonic texts and patterns.
First, we argue that the problem MSM and its ancestors,
the SIA family of algorithms, solve is 3SUM-hard
and, therefore, subquadratic solutions must involve approximation.
MSM is such a solution; we describe it, and argue
that, at O(n log n) time with no large constants, it is orders
of magnitude more time-efficient than its closest competitor.
We also evaluate MSM’s performance on a retrieval
problem addressed by the OMRAS project, and show that it
outperforms OMRAS on this task by a considerable margin.
| Translated title of the contribution | A Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval |
|---|---|
| Original language | English |
| Title of host publication | 7th International Conference on Music Information Retrieval (ISMIR) |
| Publication status | Published - 2006 |
Bibliographical note
Other page information: -Conference Proceedings/Title of Journal: 7th International Conference on Music Information Retrieval (ISMIR)
Other identifier: 2000546