Parallelising the Polyphony: High-Performance Algorithms for Music Pattern Matching

We address two fundamental problems in symbolic music pattern matching: (1) exact matching, where all notes of a pattern must align with notes in the dataset, and (2) pattern subset matching, where the goal is to identify all translations of the pattern that yield partial matches based on shared onset-pitch pairs. We propose two new bit-parallel algorithms that solve these problems in O(n'm(c/w)) and O(n'm \log m(c/w)) time, respectively, where n' is the number of distinct dataset note onset times, m is the number of pattern notes, c is the number of possible pitches and w is the computer word size. In practice, our methods can achieve substantial speedups and require less working space than the previous best-known solutions for these problems, making them well-suited for large-scale music retrieval tasks.