Advanced Polyphonic Music Pattern Matching Algorithms with Timing Invariances

This paper considers polyphonic pattern matching in symbolically encoded music under transposition invariance. We show how, in two specific retrieval problems, the worst-case time complexities can be improved by an order of magnitude by applying a relatively straightforward algorithm design technique. Moreover, the technique applies to most of the previously best-known algorithms for the other cases of the problem category, giving comparable worst-case running times. In general, given two point sets, a musical work T and a pattern P, the task is to find possibly transposed occurrences of P in T. The occurrences may be full or partial, with or without time-warping or time-scaling. The technique uses a merge-like approach to incrementally build pattern occurrences using sorted lists of notes. The algorithms search for incomplete matches that are subsequently extended as far as possible.