Paper Info
Title
A Fast, Randomised, Maximal Subset Matching Algorithm for Document-Level Music Retrieval
Abstract
We present MSM, a new maximal subset matching algo- rithm, for MIR at score level with polyphonic texts and pat- terns. First, we argue that the problem MSM and its an- cestors, the SIA family of algorithms, solve is 3SUM-hard and, therefore, subquadratic solutions must involve approx- imation. MSM is such a solution; we describe it, and argue that, at O(nlogn) time with no large constants, it is orders of magnitude more time-efficient than its closest competi- tor. 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.
Year
Venue
Keywords
2006
ISMIR 2013
point set representation.,pattern matching
Field
DocType
Citations 
Pattern recognition,Computer science,Speech recognition,Artificial intelligence,Time complexity,Machine learning,Blossom algorithm
Conference
20
PageRank 
References 
Authors
1.22
11
5
Name
Order
Citations
PageRank
Raphaël Clifford126828.57
Manolis Christodoulakis2649.49
Tim Crawford323128.95
David Meredith4201.22
Geraint Wiggins540152.80