Linear time for discovering non-trivial repeating patterns in music databases

A repeating pattern is commonly used in analyzing the repeated part of music data and looking for themes. Most of the repeating patterns are key melodies and are easy to familiarize and remember for people. Therefore, we can use the themes or the repeating patterns to construct indices that can speed up music retrieval. Non-trivial repeating patterns exclude those patterns which are all contained in other longer patterns, such that they can reduce the redundancy of the repeating patterns and save the index space. Most existing algorithms are time consuming for finding non-trivial repeating patterns. In this paper, we propose an approach for efficiently discovering nontrivial repeating patterns in linear time.