Discovering distorted repeating patterns in polyphonic music through longest increasing subsequences. Issue 2 (4th May 2021) - Laaksonen, Antti; Lemström, Kjell
Abstract : We study the problem of identifying repetitions under transposition and time-warp invariances in polyphonic symbolic music. Using a novel onset-time-pair representation, we reduce the repeating pattern discovery problem to instances of the classical problem of finding the longest increasing subsequences. The resulting algorithm works in O ( n 2 log ⁡ n ) time where n is the number of notes in a musical work. We also study windowed variants of the problem where onset-time differences between notes are restricted, and show that they can also be solved in O ( n 2 log ⁡ n ) time using the algorithm.