Parallel Non-Trivial Repeating Pattern Discovering for Music Data

Y.-L. Lo and C.-Y. Chen (Taiwan)


parallel computing, music database, repeating pattern, nontrivial repeating pattern, contentbased retrieval


A repeating pattern is a sequence of notes appearing more than once in a music object. Most of the repeating patterns are key melodies or easy to familiarize and remember for people. We can use the themes or the repeating patterns to construct indices for speedup music retrieval. A non-trivial repeating pattern is commonly used in analyzing the repeated part of a music object and looking for its theme. Non-trivial repeating patterns exclude those patterns that are all contained in other longer patterns, such that we can reduce the redundancy of the repeating patterns. However, the existing techniques for discovering the non-trivial repeating patterns for a music object are significantly time consuming and with time complexity of O(n2 ). In this paper, we propose a parallel algorithm for discovering non-trivial repeating patterns for music data. This algorithm can reduce the time complexity to a linear execution time. We hope that our approach can be used to discover not only repeating patterns on a music object but also repeating sequences on the DNAs and protein in the near future.

Important Links:

Go Back