臺灣博碩士論文加值系統

在本篇論文中我們首先探討內涵式音樂資訊查詢的技術，包括：音樂物件表示法（representation）、相似度衡量（similarity measure）、以及索引和查詢處理。在音樂物件的表示法，我們介紹三種編碼方法（coding scheme）、包括：chord、mubol和music segment，和其相似度衡量的計算式。針對索引和查詢處理的技術，我們歸納suffix tree、n-gram和augmented suffix tree等方法，並進一步做定性的分析和討論。
音樂資訊查詢的各種技術，我們規劃並執行Ultima project，建立一個測試平台（platform）來評估。在這開放式的平台，我們針對各個索引及查詢處理的方法，執行一系列的實驗。特別針對方法的效率（efficiency）和效能（effectiveness），根據定性的討論和定量的實驗數據，整理了關於音樂資訊查詢技術的分析研究報告。
內涵式音樂資訊查詢處理的技術，可以應用在查詢（searching）、分類（classification）、與推薦（recommendation）等方面，其中，我們也深入探討音樂資料的特徵擷取（feature extraction）的問題。在音樂物件中，一段重複出現的音符，我們定義為「重覆樣型（repeating pattern）」。重覆樣型是音樂物件中的一項重要特徵。例如，樂曲中的「主題」就是重覆樣型。針對如何在音樂物件中找出重覆樣型的問題，我們提出兩個方法。在第一個方法，我們設計correlative matrix的資料結構和演算法，能夠有效率地擷取音樂物件中的重覆樣型。在第二個方法，我們定義string-join的方法和RP-tree的資料結構，也能夠有效率地擷取重覆樣型。同時，我們也做實作這兩個方法，並就效率和效能的方面來做分析、比較。
更進一步的，從擷取重覆樣型的問題，延伸到擷取「相似重覆樣型（approximate repeating pattern）」。我們介紹兩個在序列資料（sequence data）中擷取相似重覆樣型的應用。根據三種相似類型（包括：longer_length、shorter_length和equal_length），我們明確地定義了相似重覆樣型的問題。其中，針對longer_length這類型問題，我們利用cut和pattern_join的方法、提出一演算法來解決這問題。另外，特別針對長的重覆樣型（long pattern），我們利用generalized_pattern_join的方法，能更有效率在序列資料中擷取長的重覆樣型。同樣的，我們也以實作來驗證這演算法的效率。

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.

Abstracti
Acknowledgementiii
Contentsiv
List of Figuresvii
List of Tablesxi
1. Introduction1
1.1. Related Work of Musical Information Retrieval3
1.2. Related Work of Finding Patterns from Sequence Data5
2. Various Techniques for Content-based Music Information Retrieval7
2.1. The Representation of Music Objects7
2.1.1) Chord7
2.1.2) Mubol8
2.1.3) Music Segment9
2.1.4) An Extension12
2.2. Indexing13
2.2.1) Suffix Tree-based Indexing13
2.2.2) (N-gram+Tree)-based Indexing14
2.2.3) Augmented Suffix Tree-based Indexing16
2.3. Query Processing18
2.3.1) Exact Matching18
2.3.2) Template-based Matching20
2.3.3) Thresholding-based Matching21
2.4. Discussion25
2.4.1) Comparison of Representation Methods26
2.4.2) Comparison of Indexing and Query Processing27
2.4.3) Intrinsic Difficulties28
3. The Ultima Project31
3.1. System Design, Implementation, and Issues31
3.1.1) Data Set33
3.1.2) Query Set Generation34
3.1.3) Efficiency and Effectiveness Study34
3.2. Description of the Approaches35
3.2.1) The 1D-List Approach35
3.3. The Efficiency Study36
3.3.1) Index Construction36
3.3.2) Exact Query Processing38
3.3.3) Summary of the Experiment Results44
4. Discovering Non-trivial Repeating Patterns47
4.1. Music Features and Repeating Patterns47
4.1.1) Music Features47
4.1.2) Non-trivial Repeating Patterns49
4.2. The Correlative-Matrix Approach50
4.2.1) Approach Overview50
4.2.2) Algorithms for the Correlative-Matrix Approach54
4.3. The String-Join Approach56
4.3.1) Approach Overview56
4.3.2) Algorithms for the String-Join Approach57
4.4. Performance Evaluation and Semantic Analysis63
4.4.1) Experiment Set-up63
4.4.2) Performance Analysis65
4.4.3) Semantics Analysis69
5. Finding Approximate Repeating Patterns73
5.1. Applications73
5.1.1) Application 1: Feature Extraction from Music Data73
5.1.2) Application 2: Accessing Patterns from Web Logs74
5.2. Problem Formulation75
5.2.1) The Definitions75
5.2.2) The Problem78
5.3. Our Approach81
5.3.1) Basic Approach81
5.3.2) Refined Approach86
5.4. Performance Evaluation88
5.4.1) Experiment Set-up89
5.4.2) Performance Evaluation89
5.5. An Extension to Polyphonic Music Objects92
5.5.1) The Definition94
5.5.2) The Problem96
5.5.3) The Approach97
6. Conclusion99
6.1. Future Work100
References:103
Appendix A:109
Appendix B:111

[Adje97]Adjeroh, D. A. and K. C. Nwosu, “Multimedia Database Management: Requirements and Issues,” IEEE Multimedia Magazine, Vol. 4, No. 3, 1997, pages 21~23.
[Apos84]Apostolico, A., “The Myriad Virtues of Subwords Trees”, in A. Apostolico and Z. Galil (eds.), Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F: Computer and System Sciences, pages 97~107, Springer-Verlag, Berlin, Germany, 1984.
[Apos96]Apostolico, A. and F. Preparata, “Data Structures and Algorithms for the String Statistics Problem,” Algorithmica, 15:481~494, 1996.
[Apos97]Apostolico, A., and Z. Galil, Pattern Matching Algorithms, Oxford University Press, 1997.
[Bakh97]Bakhmutova, V., V. D. Gusev, and T. N. Titkova, “The Search for Adaptations in Song Melodies,” Computer Music Journal, Vol. 21, No. 1, pages 58~67, Spring 1997.
[Barl75]Barlow, H. and S. Morgenstern, A Dictionary of Musical Themes, Crown Publishers, Inc., New York, 1975.
[Baro92]Baroni, M., R. Dalmonte, and C. Jacoboni, “Theory and Analysis of European Melody,” in A. Marsden and A. Pople (eds.), Computer Representation and Models in Music, Academic Press, 1992.
[Bera98]Berra, P. B. and A. Ghafoor, “Data and Knowledge Management in Multimedia Systems: the Guest Editors’ Introduction to the Special Section,“ IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No. 6, pages 868~871, 1998.
[Bett98]Bettini, C., X. S. Wang, S. Jajodia, and J.-L. Lin, “Discovering Frequent Event Patterns with Multiple Granularities in Time Sequences,” IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No. 2, 1998.
[Blac98]Blackburn, S. and D. DeRoure, “A Tool for Content-Based Navigation of Music,” in Proceedings of the 6th ACM International Multimedia Conference, pages 361~368, 1998.
[Borg97]Borg, I. and P. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer-Verlag, New York, 1997.
[Burk93]Burke, J., The Illustrated Dictionary of Music, Warner Books and BLP Publishing Limited, 1993.
[Camb95]Cambouropoulos, E. and A. Smaill, “A Computational Theory for the Discovery of Parallel Melodic Passages,” in Proceedings of the XI Colloquio di Informatica Musicale, Bologna, Italy, 1995.
[Chen00]Chen, A. L. P., M. Chang, J. Chen, J. L. Hsu, C. H. Hsu, and S. Y. S. Hua, “Query by Music Segments: An Efficient Approach for Song Retrieval,” in Proceedings of IEEE International Conference on Multimedia and Expo (ICME’00), 2000.
[ChenJ98]Chen, J. C. C. and A. L. P. Chen, “Query by Rhythm: An Approach for Song Retrieval in Music Databases,” in Proceedings of 8th Intl. Workshop on Research Issues in Data Engineering, pages 139~146, 1998.
[ChenM84]Chen, M. T. and J. Seiferas, “Efficient and Elegant Subword-Tree Construction,” in A. Apostolico and Z. Galil (eds.), Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F: Computer and System Sciences, pages 97~107, Springer-Verlag, Berlin, Germany, 1984.
[Chou96]Chou, T. C., A. L. P. Chen, and C. C. Liu, “Music Databases: Indexing Techniques and Implementation,” in Proceedings of IEEE Intl. Workshop on Multimedia Data Base Management System, 1996.
[Clau00]Clausen, M., R. Engelbrecht, D. Mayer, and J. Smith,”PROMS: A Web-based Tool for Searching in Polyphonic Music,” in Proceedings of International Symposium on Music Information Retrieval (Music IR), 2000.
[Cox94]Cox, T. F. and M. A. A. Cox, Multidimensional Scaling, Chapman & Hall, 1994.
[Craw98]Crawford, T., C. S. Iliopoulos, and R. Raman, “String-Matching Techniques for Musical Similarity and Melodic Recognition,” in Hewlett, W. B. and E. Selfridge-Field (eds.), Melodic Similarity: Concepts, Procedures, and Applications (Computing in Musicology: 11), The MIT Press, 1998.
[Croc94]Crochemore, M. and W. Rytter, Text Algorithms, Oxford University Press, 1994.
[DeRo00]DeRoure, D. and S. Blackburn, “Content-based Navigation of Music using Melodic Pitch Contours,” Multimedia Systems, 8(3), Springer-Verlag, 2000, pages 190~200.
[Down00a]Downie, S., “Thinking about Formal MIR System Evaluation: Some Prompting Thoughts,” Available on http://www.lis.uiuc.edu/~jdownie/mir_papers/downie_mir_eval.html, 2000.
[Down00b]Downie, S. and M. Nelson, “Evaluation of a Simple and Effective Music Information Retrieval Method,” in Proceedings of ACM SIGIR, 2000, pages 73~80.
[Foot99]Foote, J., “An Overview of Audio Information Retrieval,” Multimedia Systems, Vol. 7, No. 1, pages 2~10, ACM Press & Springer-Verlag, 1999.
[Frak92]Frakes, W. B. and R. Baeza-Yates (eds.), Information Retrieval: Data Structures and Algorithms, Prentice-Hall, 1992.
[Ghia95]Ghias, A., H. Logan, D. Chamberlin, and B. C. Smith, “Query by Humming: Musical Information Retrieval in an Audio Database,” in Proceedings of Third ACM International Conference on Multimedia, 1995, pages 231~236.
[Gonn91]Gonnet, G. H. and R. Baeza-Yates, Handbook of Algorithms and Data Structures: in Pascal and C, Addison-Wesley Publishing Company, 1991.
[Gusf97]Gusfield, D., Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
[Han99]Han J., G. Dong, and Y. Yin, “Efficient Mining of Partial Periodic Patterns in Time Series Database,” in Proceedings of the 15th International Conference on Data Engineering, 1999.
[Hewl98]Hewlett, W. B. and E. Selfridge-Field (eds.), Melodic Similarity: Concepts, Procedures, and Applications (Computing in Musicology: 11), The MIT Press, 1998.
[Hsu]Hsu, J. L., C. C. Liu, and A. L. P. Chen, “Discovering Non-Trivial Repeating Patterns in Music Data,” IEEE Transactions on Multimedia (accepted).
[Hsu01]Hsu, J. L., and A. L. P. Chen, ”Building a Platform for Performance Study of Various Music Information Retrieval Approaches,” in Proceedings of International Symposium on Music Information Retrieval (ISMIR 2001), 2001.
[Hsu98]Hsu, J. L., C. C. Liu, and A. L. P. Chen, “Efficient Repeating Pattern Finding in Music Databases,” in Proceedings of Seventh International Conference on Information and Knowledge Management (CIKM''98), 1998.
[Jain88]Jain, A. K. and R. C. Dubes, Algorithms for Clustering Data, Prentice-Hall Inc., 1988.
[Jame85]James, M., Classification Algorithms, Wiley, New York, 1985.
[Jone74]Jones, G. T., Music Theory, Harper & Row, Publishers, New York, 1974.
[Krum90]Krumhansl, C. L., Cognitive Foundations of Musical Pitch, Oxford University Press, New York, 1990.
[Lee00]Lee, W. and A. L. P. Chen, “Efficient Multi-Feature Index Structures for Music Data Retrieval,” in Proceedings of SPIE Conference on Storage and Retrieval for Image and Video Databases, 2000.
[Lems00]Lemstrom, K. and S. Perttu, “SEMEX: An Efficient Music Retrieval Prototype,” in Proceedings of International Symposium on Music Information Retrieval (Music IR), 2000.
[Lems00b]Lemstrom, K., String Matching Techniques for Music Retrieval, The PhD Theses, Department of Computer Science, University of Helsinki, Finland, Series of Publications A: Report A-2000-04, 2000.
[Lerd83]Lerdahl, F. and R. Jackendoff, A Generative Theory of Tonal Music, The MIT Press, 1983.
[Liu01]Liu, C. C., J. L. Hsu, and A. L. P. Chen, “Efficient Near Neighbor Searching Using Multi-Indexes for Content-Based Multimedia Data Retrieval,” Multimedia Tools and Applications, Vol. 13, No. 3, 2001.
[Liu99a]Liu, C. C., J. L. Hsu, and A. L. P. Chen, “An Approximate String Matching Algorithm for Content-Based Music Data Retrieval,” in Proceedings of International Conference on Multimedia Computing and Systems (ICMCS’99), 1999.
[Liu99b]Liu, C. C., J. L. Hsu, and A. L. P. Chen, “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” in Proceedings of the 15th International Conference on Data Engineering (ICDE’99), 1999.
[Lohr95]Lohr, M. and T. C. Rakow, “Audio Support for an Object-Oriented Database-Management System,” ACM Multimedia Systems Journal, pp. 286~297, 1995.
[Lund85]Lundin, R. W., An Objective Psychology of Music, Robert E. Krieger Publishing Company, 1985.
[Mann95]Mannila H., H. Toivonen, and A. I. Verkamo, “Discovering Frequent Episode in Sequences,” in Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD-95), AAAI Press, 1995.
[Mann96]Mannila H. and H. Toivonen, “Discovering Generalized Episodes Using Minimal Occurrences,” in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), AAAI Press, 1996.
[McCr76]McCreight, E. M., “A Space Economical Suffix Tree Construction Algorithm,” J. Assoc. Comput. Mach., 23:262~272, 1976.
[McNa00]McNab, R. J., L. S. Smith, I. H. Witten, and C. L. Henderson, ”Tune Retrieval in the Multimedia Library,” Multimedia Tools and Applications, Vol. 10, No. 2/3, Kluwer Academic Publishers, 2000.
[MIDI]MIDI Manufacturers Association (MMA), MIDI 1.0 Specification, http://www.midi.org/.
[Narm90]Narmour, E., The Analysis and Cognition of Basic Melodic Structures, The University of Chicago Press, Chicago, 1990.
[Nwos97]Nwosu, K. C., B. Thuraisingham, and P. B. Berra, “Multimedia Database Systems: A New Frontier,” IEEE Multimedia Magazine, Vol. 4, No. 3, pages 21~23, 1997.
[Ozsu98]Ozsu, M. T. and S. Christodoulakis, “Introduction to the Special Issue on Multimedia Databases, “ The VLDB Journal, Vol. 7, No. 4, page 205, 1998.
[Pfei96]Pfeiffer, S., S. Fischer, and W. Effelsberg, “Automatic Audio Content Analysis,” in Proceedings of the Fourth ACM International Multimedia Conference, 1996, pages 21~30.
[Prat96]Prather, R. E., “Harmonic Analysis from the Computer Representation of a Musical Score,” Communication of the ACM, Vol. 39, No. 12, Dec. 1996, pages 119, (pages 239~255 of Virtual Extension Edition of CACM).
[Sadi88]Sadie, S., The Norton/Grove Concise Encyclopedia of Music, W. W. Norton & Company, 1988.
[Salt83]Salton, G. and M. McGill, Introduction to Modern Information Retrieval, MaGraw-Hill Book Company, 1983.
[Sank83]Sankoff, D. and J. B. Kruskal (eds.), Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, Addison-Wesley Publishing Company, 1983.
[Self98]Selfridge-Field, E., “Conceptual and Representational Issues in Melodic Comparison,” in Hewlett, W. B. and E. Selfridge-Field (eds.), Melodic Similarity: Concepts, Procedures, and Applications (Computing in Musicology: 11), The MIT Press, 1998.
[Stan80]Stanley, S., The New Grove Dictionary of Music and Musicians, Macmillan Publishers Limited, 1980.
[Sund91]Sundberg, J., A. Friberg, and L. Fryden, “Common Secrets of Musicians and Listeners: An Analysis-by-synthesis Study of Musical Performance,” in Representing Musical Structure, P. Howell, R. West and I. Cross (eds.), Academic Press, London, 1991.
[Taus97]Tauscher, L. and S. Greenberg, “Revisition Patterns in World Wide Web Navigation,” in ACM CHI’97.
[Tsen99]Tseng, Y. H., “Content-Based Retrieval for Music Collections,” ACM SIGIR, 1999.
[Thom85]Thomsett, M. C., Musical Terms, Symbols, and Theory: An Illustrated Dictionary, St James Press, 1985.
[Uitd98]Uitdenbogerd, A., and J. Zobel, “Manipulation of Music for Melody Matching,” in Proceedings of the 6th ACM International Multimedia Conference, pages 235~240, 1998.
[Uitd99]Uitdenbogerd, A., and J. Zobel, “Melodic Matching Techniques for Large Music Databases,” in Proceedings of the 7th ACM International Multimedia Conference, pages 57~66, 1999.
[Ukko95]Ukkonen, E., “On-Line Construction of Suffix Tree,” Algorithmica, 14:249~260, 1995.
[Wang97]Wang, K., “Discovering Patterns from Large and Dynamic Sequential Data,” Journal of Intelligent Information Systems, 9:33~56, Kluwer Academic Publishers, 1997.
[Wate95]Waterman, M. S., Introduction to Computational Biology: Maps, Sequences and Genomes, Chapman & Hall, 1995.
[Wein73]Weiner, P., “Linear Pattern Matching Algorithms,” in Proceedings of IEEE 14th Annual Symposium on Switching and Automata Theory, pages 1~11, 1973.
[Witt94]Witten, I. H., A. Moffat, T. C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, Van Nostrand Reinhold, International Thomson Publishing company. 1994.
[Wold96]Wold, E., T. Blum, D. Keislar, and J. Wheaton, “Content-based Classification, Search, and Retrieval of Audio,” IEEE Multimedia Magazine, Vol. 3, No. 3, Fall 1996, pages 27~36.
[Yana99]Yanase, T. and A. Takasu, “Phrase Based Feature Extraction for Musical Information Retrieval,” in Proceedings of IEEE Pacific Rim Conference on communications, Computers, and Signal Processing, 1999.
[Yip00]Yip, C. L. and B. Kao, “A Study on n-gram Indexing of Musical Features,” in Proceedings of IEEE International Conference on Multimedia and Expo, 2000, New York.
[Yosh99]Yoshitaka, A., and T. Ichikawa, “A Survey on Content-Based Retrieval for Multimedia Databases,” IEEE Transactions on Knowledge and Data Engineering, Vol. 11, No. 1, pages 81~93, 1999.