臺灣博碩士論文加值系統

在多媒體資料庫中如何有效率的管理音樂資料，近年來已獲得了高度的關注。現在大部分的研究工作，多利用音樂資料的特性萃取，例如：旋律、節拍、和弦等等，來建立索引，以加速音樂資料的搜尋。已有許多的研究報告指出，這些音樂資料特性可以轉換為字串或數值形式，再各別發展出有效率的索引架構，以幫助音樂資料的擷取。而這些研究報告中，多數只針對音樂資料之單一特徵索引所設計，而目前已被發表少數的多特徵索引技術，若不是處理查詢沒有彈性，就是必須佔用相當大的記憶體空間，限制了多特徵索引的擴充能力與實用性。在此篇研究報告中，我們將提出一兩階層的音樂索引架構，以改善索引對記憶體的使用量以及索引搜尋的效率，同時我們的索引架構也更具擴充性，適用於兩個特徵以上之音樂資料多特徵索引。我們並經由實驗分析證實，所提出的方法，確實可以大幅降低音樂資料多特徵索引所需大量的記憶體空間，並減少時間增加索引效率，讓多特徵索引的應用，更為實用可行。

The management of large collections of music data in a multimedia database has received much attention in the past few years. In the most of current works, the researchers extract the features, such as melodies, rhythms and chords, from the music data and develop indices that will help to retrieve the relevant music quickly. Several reports have pointed out that these features of music can be transformed and represented in the forms of music feature strings or numeric values such that the indices can be created for music retrievals. However, there is only a small number of existing approaches introduced multi-feature index structures for music queries while most of others are for developing single feature indices. The existing music multi-feature index structures are memory consuming and lack of scalability. In this thesis, we will propose a two-tier music index structure which is an efficient and scalable approach for multi-feature music indexing. Our experimental results show that the new approach outperforms existing multi-feature index schemes.

摘要.......................................................................................................................................... 1
Abstract ................................................................................................................................... 2
Outline..................................................................................................................................... 4
Table......................................................................................................................................... 5
Figure....................................................................................................................................... 6
1.Introduction ......................................................................................................................... 7
2.Indexing For Music Data Retrieval ............................................................................... 9
2.1 String Indexing for Music Data ........................................................... 9
2.2 Numeric Indexing for Music Data ..................................................... 10
3.Existing Multi-Feature Indexing for Music Data..................................................... 12
3.1 Grid-Twin Suffix Trees ...................................................................... 12
3.2 Multi-Feature Numeric Index ............................................................ 15
3.3 Discussions......................................................................................... 16
4.Two-Tier Multi-Feature Indexing for Music Data................................................... 18
4.1 Construction of Two-Tier Multi-Feature Index ................................. 18
4.2 An Example for Constructing the Two-Tier Multi-Feature Index..... 23
4.3 Searching in Two-Tier Multi-Feature Index ...................................... 27
5.Performance Study........................................................................................................... 28
5.1 The Effect of Number of Symbols for Each Music Feature .............. 29
5.2 The Effect of Database Size............................................................... 30
5.3 The Effect of Query Length ............................................................... 31
5.4 The Effect of Number of Music Features .......................................... 32
6.Conclusion ......................................................................................................................... 35
Reference.............................................................................................................................. 36

Table
Table 1. The coordinates for suffixes .................................................................. 24
Table 2. Parameters for experiment..................................................................... 29

Figure
Figure 1. An example of suffix tree for music string - “ababc”.......................... 10
Figure 2. Construction of the Twin Suffix Tree [14]........................................... 13
Figure 3. An example of the Grid-Twin Suffix Trees [14].................................. 14
Figure 4. A 2-feature tree for music data............................................................. 20
Figure 5. Bit array in non-leaf node of 2-feature suffix trees ............................. 21
Figure 6. Bit arrays in non-leaf nodes of 3-feature suffix trees .......................... 22
Figure 7. A perspective of Two-Tier Multi-Feature Index .................................. 22
Figure 8. Two-Tier 2-Feature Index structures ................................................... 23
Figure 9. Two-Tier 3-Feature Index structures ................................................... 23
Figure 10. An example of constructing Two-Tier 2-Feature Index..................... 25
Figure 11. Inserting a new node .......................................................................... 25
Figure 12. Construction of the rhythm suffix tree (not all links are shown) ...... 26
Figure 13. An example of creating suffix tree with bit array.............................. 26
Figure 14. Memory needed vs. number of symbols for each music feature....... 30
Figure 15. Memory needed vs. database sizes .................................................... 31
Figure 16. Average response time vs. query length ............................................ 32
Figure 17. Memory needed vs. number of music features.................................. 33
Figure 18. Average response time vs. number of music features........................ 34

[1]S. Blackburn and D. DeRoure (1998), “A Tool for Content-based Navigation of Music,” In Proc. Of ACM Multimedia, Pages 361-368.
[2]James C.C. Chen and Arbee L.P. Chen (1998), “Query by Rhythm An Approach for Song Retrieval in Music Databases,” In Proc. Of Int’l Workshop on Research Issues in Data Engineering, Pages 139-146.
[3]Arbee L.P. Chen, M. Chang, J. Chen, J.L. Hsu, C.H. Hsu, and Spot Y.S. Hua (2000), “Query by Music Segments: An Efficient Approach for Song Retrieval,” In Proc. of IEEE Int’l Conf. on Multimedia and Expro.
[4]G. Davenport, T.A. Smith, and N. Pincever (1991), “Cinematic Primitives for Multimedia,” IEEE Computer Graphics & Applications, Pages 67-74, July.
[5]Y.F. Day, S. Pagtas, M. Iino, A. Khokhar, and A. Ghafoor (1995), “Object-Oriented Conceptual Modeling of Video Data” In Proc. Of IEEE Data Engineering, Pages 401-408.
[6]E.A. El-Kwae and M.R. Kabuka (2000), “Efficient Content-Based Indexing of Large Image Databases,” ACM Trans. On Information Systems, Vol. 18, No. 2, Pages 171-210, April.
[7]Shen-Tat Goh and Kian-Lee Tan (2000), “MOSAIC: A Fast Multi-Feature Image Retrieval System,” Data & Knowledge Engineering 33, Pages 219-239.
[8]A. Guttman (1984), “R-Tree A Dynamic Index Structure For Spatial Search,” Proceedings of the 1984 ACM SIGMOD international conference on Management of data, Pages 47-57.
[9]J.L. Hsu, C.C. Liu, and Arbee L.P. Chen (1998), “Efficient Repeating Pattern Finding in Music Databases,” In Proc. of ACM Int’l Conf. on Information and Knowledge Management.
[10]K.A. Hua, K. Vu, and J.H. Oh (1999), “SamMatch: A Flexible and Efficient Sampling-Based Image Retrieval Technique for Large Image Databases,” In Proc. of ACM Multimedia, Pages 225-234.
[11]H.V. Jagadish, N. Koudas, and D. Srivastava (2000), “On Effective Multi-Dimensional Indexing for Strings,” In Proc. of ACM SIGMOD, Pages 403-414, May.
[12]C. L. Krumhansl (1990), “Cognitive Foundations of Musical Pitch,” Oxford University Press, New York.
[13]Serkan Kiranyaz and Moncef Gabbouj (2007), Senior Member, “Hierarchical Cellular Tree: An Efficient Indexing Scheme for Content-Based Retrieval on Multimedia Databases,” IEEE Transactions on Multimedia, Vol. 9, No.1, Pages 102-119, January.
[14]W. Lee and A.L.P. Chen (2000), “Efficient Multi-Feature Index Structures for Music Data Retrieval,” In Proc. Of SPIE Conf. on Storage and Retrieval for Image and Video Database.
[15]C.C. Liu and Arbee L.P. Chen (2002), “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 1, January/February.
[16]C.C. Liu, J.L. Hsu, and Arbee L.P. Chen (1999), “An Approximate String Matching Algorithm for Content-Based Music Data Retrieval,” In Proc. of IEEE Int’l Conf. on Multimedia Computing and Systems, Pages 451-456.
[17]Chia-Han Lin and Arbee L. P. Chen (2006), “Indexing and Matching Multiple-Attribute Strings for Efficient Multimedia Query Processing,” IEEE Transactions On Multimedia, Vol. 8, No. 2, April.
[18]C.C. Liu, J.L. Hsu, and Arbee L.P. Chen (1999), “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” In Proc. of IEEE Data Engineering, Pages 14-21.
[19]Yu-lung Lo and Shiou-jiuan Chen (2002), “The Numeric Indexing For Music Data,” Proceedings of the IEEE 22nd Int’l Conference on Distributed Computing Systems (ICDCS’2002) Workshops – the 4th Int’l Workshop on Multimedia Network Systems and Applications (MNSA’2002), Vienna, Austria, Pages 258-263, July.
[20]Yu-lung Lo and Shiou-jiuan Chen (2002), “Numeric Indexing Approach for Music Database Retrieval,” Journal of Chaoyang University of Technology, ISSN 1026-244X, Vol. 2, Pages 141-163, June.
[21]Yu-lung Lo and Shiou-jiuan Chen (2003), “Multi-feature Indexing For Music Data,” IEEE 23nd International Conference on Distributed Computing Systems (ICDCS’2003) Workshops – the 5th International Workshop on Multimedia Network Systems and Applications (MNSA’2003), Providence, Rhode Island, USA, Pages 654-659, May 19-22.
[22]Yu-lung Lo, Ho-cheng Yu, and Mei-chin Fan (2001), “Efficient Non-trivial Repeating Pattern Discovering in Music Databses,” Tamsui Oxford Journal of Mathematical Sciences, Vol. 17, No. 2, Pages 163-187, Nov..
[23]Yu-lung Lo and Wen-Lin Lee (2004), “Linear Time for Discovering Non-trivial Repeating Patterns in Music Databases,” the 2004 IEEE International Conference on Mulitmedia and Expro (ICME), Taipei, Taiwan, June 27-30.
[24]Yu-lung Lo, Wen-Lin Lee and Lin-hunag Chang (2008), “True Suffix Tree Approach for Discovering Non-trivial Repeating Patterns in a Music Object,” Journal of Multimedia Tools and Applications, Springer, Vol. 37, No. 2, Pages 169-187, April.
[25]E. McCreight (1976), “A Space-Economical Suffix Tree Construction Algorithm,” Journal of Association for Computing Machinery, Pages 262-272.
[26]J.H. Oh and K.A. Hua (2000), “Efficient and Cost-Effective Techniques for Browsing and Indexing Large Video Databases,” In Proc. of ACM DIGMOD, Pages 415-426.
[27]S.W. Smoliar and H.J. Zhang (1994), “Content-Based Video Indexing and Retrieval,” IEEE Multimedia Magazine, Pages 62-72.
[28]Tomonari Sonoda, Toshiya Ikenaga, Kana Shimizu and Yoichi Muraoka (2002), “The Design Method of A Melody Retrieval System on Parallelized Computers,” Proceedings Second International Conference on Web Delivering of Music, Pages 66-73.
[29]Bjorn Schuller, Gerhard Rigoll and Manfred Lang (2004), “Multimodal Music Retrieval for Large Databases,” IEEE International Conference on Multimedia and Expo (ICME), Vol. 2, Pages 755-758, June.
[30]Y.H. Tseng (1999), “Content-Based Retrieval for Music Collections,” In Proc. of ACM SIGIR’99, Pages 176-182.
[31]Michael Tang, YIP Chi Lap, and Ben Kao (2000), “Selection of Melody Lines for Music Databases,” IEEE Multimedia, Pages 243-248.
[32]Tsung-Han Tsai and Jui-Hung Hung (2006), “Content-Based Retrieval of MP3 Songs for One Singer Using Quantization Tree Indexing and Melody-Line Tracking Method,” ICASSP 2006 Proceedings, Pages 505-508, May.
[33]A.L. Uitdenbogerd and J. Zobel (1999), “Melodic Matching Techniques for Large Music Databases,” In Proc. of ACM Multimedia, Pages 57-66.
[34]E. Ukkonen (1995), “On-Line Construction of Suffix Tree,” Algorithmica, Vol. 14, Pages 249-260.
[35]Ya-Dong Wu, Yang Li and Bao-Long Liu (2003), “A New Method for Approximate Melody Matching,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, Vol. 5, Pages 2687-2691, Nov. 2-5.
[36]P. Weiner (1973), “Linear Pattern Matching Algorithms,” in Proc. Of IEEE Ann. Symp. On Switching and Automata Theory, Pages 1-11.
[37]Ruiduo Yang and M. S. Brown (2004), “Music Database Query With Video By Synesthesia Observation,” IEEE International Conference on Multimedia and Expo(ICME), Vol. 1, Pages 305-308, June.