Algorithms for discovering repeated patterns in multidimensional representations of polyphonic music

Abstract

In previous approaches to repetition discovery in music, the music to be analysed has been represented using strings. However, there are certain types of interesting musical repetitions that cannot be discovered using string algorithms. We propose a geometric approach to repetition discovery in which the music is represented as a multidimensional dataset. Certain types of interesting musical repetition that cannot be found using string algorithms can efficiently be found using algorithms that process multidimensional datasets. Our approach allows polyphonic music to be analysed as efficiently as monophonic music and it can be used to discover polyphonic repeated patterns “with gaps” in the timbre, dynamic and rhythmic structure of a passage as well as its pitch structure. We present two new algorithms: SIA and SIATEC. SIA computes all the maximal repeated patterns in a multidimensional dataset and SIATEC computes all the occurrences of all the maximal repeated patterns in a dataset. For a k -dimensional dataset of size n, the worstcase running time of SIA is O (kn 2 log 2 n) and the worst-case running time of SIATEC is O (kn 3).