Abstract
In this thesis, we first discuss the techniques used in content-based music information retrieval. The techniques include the methods to represent music objects, the similarity measures of music objects, and indexing and query processing for music object retrieval. To represent music objects, we introduce three coding schemes, i.e., chord, mubol, and music segment. Various similarity measures are then presented, followed by various index structures and the associated query processing algorithms. The index structures include suffix tree, n-gram, and augmented suffix tree. A qualitative comparison of these techniques is finally performed to show the intrinsic difficulty of the problem of content-based music information retrieval. We also initiate the Ultima project which aims to construct a platform for evaluating various approaches of music information retrieval. Three approaches with the corresponding tree-based, list-based, and (n-gram+tree)-based index structures are implemented. A series of experiments has been carried out. With the support of the experiment results, we compare the performance of index construction and query processing of the three approaches and give a summary for efficient content-based music information retrieval. The feature extraction problem for music objects is also studied to support content-based music information retrieval in searching, classification, recommendation, and so forth. A repeating pattern in music data is defined as a sequence of notes which appears more than once in a music object. The themes are a typical kind of repeating patterns. The themes and other non-trivial repeating patterns are important music features which can be used for both content-based retrieval of music data and music data analysis. We propose two approaches for fast discovering non-trivial repeating patterns in music objects. In the first approach, we develop a data structure called correlative matrix and its associated algorithms for extracting the repeating patterns. In the second approach, we introduce a string-join operation and a data structure called RP-tree for the same purpose. Experiments are performed to compare these two approaches with others. The results are also analyzed to show the efficiency and the effectiveness of our approaches. Further, we extend the problem of finding exact repeating patterns to the one of finding approximate repeating patterns. First, two applications are introduced to motivate our research of finding approximate repeating patterns from sequence data. An approximate repeating pattern is defined as a sequence of symbols which appears more than once under certain approximation types in a data sequence. We define three approximation types, i.e., longer_length, shorter_length, and equal_length. The problems of finding approximate repeating patterns with respect to the three types are specified. By applying the concept of ‘cut’ and ‘pattern_join’ operator, we develop a level-wise approach to solve the problem of finding approximate repeating patterns with respect to the type of longer_length approximation. In addition, we extend the pattern_join operator to the generalized_pattern_join operator for efficiently finding long patterns. The performance study shows that our approach is efficient and also scales well. We also refine our approach to extract repeating patterns from polyphonic music data.