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|
|Title of host publication||7th International Conference on Music Information Retrieval (ISMIR)|
|Publication status||Published - 2006|
Bibliographical noteOther page information: -
Conference Proceedings/Title of Journal: 7th International Conference on Music Information Retrieval (ISMIR)
Other identifier: 2000546