Skip to main content

A Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval

Rapha?, Manolis Christodoulakis, Tim Crawford, David Meredith, Geraint Wiggins, A Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval. 7th International Conference on Music Information Retrieval (ISMIR). October 2006. No electronic version available.

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 MSMA?s performance on a retrieval problem addressed by the OMRAS project, and show that it outperforms OMRAS on this task by a considerable margin.

Bibtex entry.

Contact details

Publication Admin