Discovering distorted repeating patterns in polyphonic music through longest increasing subsequences. Issue 2 (4th May 2021)

• Record Type: Journal Article
• Authors: Laaksonen, Antti; Lemström, Kjell
• Is Part Of: Journal of mathematics and music. Volume 15:Issue 2(2021)
• Page Start: 99
• Page End: 111
• Publication Date: 2021-05-04
• Subjects: repeating pattern discovery -- longest increasing subsequences -- symbolic music processing; music retrieval -- pattern matching; Music theory -- Periodicals; Music -- Mathematical models -- Periodicals; Music -- Mathematics -- Periodicals; 781.2
• DOI: 10.1080/17459737.2021.1896811
• Languages: English
• ISSNs: 1745-9737

Abstract

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.