Compacting music signatures for efficient music retrieval

ABSTRACT

Music information retrieval is becoming very important with the ever-increasing growth of music content in digital libraries, peer-to-peer systems and the internet. While it is easy to quantize music into a discrete string representation, retrieval by content requires (approximate) sub-string matching, which is hard.

In this paper, we present a novel system, called MUSIG, that uses compact MUsic SIGnatures for efficient contentbased music retrieval. The signature is computed as follows: (a) each music file is split into a set of (overlapping) segments; (b) similar segments are clustered together; the number of clusters corresponds to the number of dimensions; (c) for each music file, the number of its segments that fall into a cluster determines the key value in that dimension.

Most index structures for multimedia are only able to provide an initial filtering and return a set of candidate answers that must be further examined. For MUSIG, we have also designed a scoring function that permits a ranked answer set to be generated directly based only on the signatures. Our experimental results show that this scheme retains a high degree of accuracy while being very efficient.

REFERENCES

• 1: Download karaoke files and players. In http://www.schok.co.uk/kb/downloads.htm, 2005.
• 2: Bin Cui , Ling Liu , Calton Pu , Jialie Shen , Kian-Lee Tan, QueST: querying music databases by acoustic and textual features, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291465]
• 3: Bin Cui , Jialie Shen , Gao Cong , Heng Tao Shen , Cui Yu, Exploring composite acoustic features for efficient music similarity query, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180725]
• 4: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: C. Francu and C. G. Nevill-Manning. Distance metrics and indexing strategies for a digital library of popular music. In Proc. International Conference on Multimedia and Expo (II), pages 889--, 2000.
• 6: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 7: J. Hartigan and M. Wong. A K-means clustering algorithm. In Applied Statistics, Volume. 28, pages 100--108, 1979.
• 8: Jia-Lien Hsu , Arbee L. P. Chen , Hung-Chen Chen , Ning-Han Liu, The effectiveness study of various music information retrieval approaches, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584862]
• 9: Jyh-Shing Roger Jang , Hong-Ru Lee, Hierarchical filtering method for content-based music retrieval via acoustic input, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500201]
• 10: Jyh-Shing Roger Jang , Hong-Ru Lee , Jiang-Chun Chen, Super MBox: an efficient/effective content-based music retrieval system, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500270]
• 11: K. Jensen and T. H. Andersen. Real-time beat estimation using feature extraction. In Proc. the Computer Music Modeling and Retrieval Symposium, 2003.
• 12: Richard L. Kline , Ephraim P. Glinert, Approximate matching algorithms for music information retrieval using vocal input, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957042]
• 13: Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases, Proceedings of the 15th International Conference on Data Engineering, p.14, March 23-26, 1999
• 14: Chih-Chin Liu , Po-Jun Tsai, Content-based retrieval of MP3 music objects, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502670]
• 15: Ning-Han Liu , Yi-Hung Wu , Arbee L. P. Chen, Efficient K-NN search in polyphonic music databases using a lower bounding mechanism, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California [doi>10.1145/973264.973291]
• 16: M. Marolt. On finding melodic lines in audio recordings. In Proc. 7th Int. Conference on Digital Audio Effects, 2004.
• 17: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 18: T. Nishimura, H. Hashiguchi, J. Takita, J. X. Zhang, M. Goto, and R. Oka. Music signal spotting retrieval by a humming query using start frame feature dependent continuous dynamic programming. In Proc. International Symposium on Music Information Retrieval, pages 301--307, 2001.
• 19: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 20: H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996 [doi>10.1109/69.536247]
• 21: Dacheng Tao , Hao Liu , Xiaoou Tang, K-BOX: a query-by-singing based music retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027639]
• 22: Rainer Typke , Remco C. Veltkamp , Frans Wiering, Searching notated polyphonic music using transportation distances, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027551]
• 23: G. Tzanetakis and P. Cook. Musical genre classification of audio signals. In IEEE Transactions on Speech and Audio Processing, pages 293--302, 2002.
• 24: Alexandra L. Uitdenbogerd , Justin Zobel, Manipulation of music for melody matching, Proceedings of the sixth ACM international conference on Multimedia, p.235-240, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290776]
• 25: Alexandra Uitdenbogerd , Justin Zobel, Melodic matching techniques for large music databases, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.57-66, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319470]
• 26: Alexandra L. Uitdenbogerd , Justin Zobel, Music ranking techniques evaluated, Proceedings of the twenty-fifth Australasian conference on Computer science, p.275-283, January 01, 2002, Melbourne, Victoria, Australia
• 27: Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, v.92 n.1, p.191-211, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90143-4]
• 28: E. Ukkonen. On-line construction of suffix trees. In Algorithmica, pages 14(3):249--260, 1995.
• 29: Cheng Yang, Efficient acoustic index for music retrieval with various degrees of similarity, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641125]
• 30: Yongwei Zhu , Mohan Kankanhalli, Music scale modeling for melody matching, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957091]
• 31: Yunyue Zhu , Dennis Shasha, Warping indexes with envelope transforms for query by humming, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872780]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models