A parallel algorithm for finding maximal transformed matches of polyphonic patterns in unvoiced polyphonic music

We present a parallel algorithm for finding transformed matches of a query pattern in a database of symbolic music encodings in which voice information is absent, ambiguous or unreliable (e.g., an encoding of a score or performance of a keyboard work). Our algorithm allows users to define the class of transformations by which matches may be related to a query pattern. We assume an encoding, D, in the database and the query pattern, P, are represented by sets of k-dimensional points, D,P ⊂ Rk. In addition to P and D, the algorithm takes as input a user-defined class, F, of transformations, each of which must be a bijection over Rk.<br/>We define Q to be a maximal match of P in D with respect to F, if there is an f∈FsuchthatQ=f(P′),whereP′ ⊆PandthereisnoSsuchthatP′ ⊂S and f(S) ⊆ D. Our algorithm computes all maximal matches of P in D with respect to F. If m = |P| and n = |D|, then the algorithm does Θ((mn)β logn) work, has Θ(β(logm+logn)) span and uses Θ((mn)β) space, where β is the basis size associated with the transformation class F . For example, if F contains the traditional contrapuntal transformations of transposition, augmentation, diminution, inversion, retrograde and their combinations, then β = 2. We evaluated the algorithm on two musicological tasks: discovering occurrences of the “HAYDN” theme in Ravel’s Menuet sur le nom d’Haydn, on which the algorithm achieved an F1 score of 0.70; and discovering subject entries in Contrapunctus VI from Bach’s Die Kunst der Fuge, on which the algorithm achieved an F1 score of 0.93.