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

Raphaël Clifford, Manolis Christodoulakis, Tim Crawford, David Meredith, Geraint Wiggins

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

24 Citations (Scopus)

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 contributionA Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval
Original languageEnglish
Title of host publication7th International Conference on Music Information Retrieval (ISMIR)
Publication statusPublished - 2006

Bibliographical note

Other page information: -
Conference Proceedings/Title of Journal: 7th International Conference on Music Information Retrieval (ISMIR)
Other identifier: 2000546

Fingerprint Dive into the research topics of 'A Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval'. Together they form a unique fingerprint.

Cite this