QueST: querying music databases by acoustic and textual features

ABSTRACT

With continued growth of music content available on the Internet, music information retrieval has attracted increasing attention. An important challenge for music searching is its ability to support both keyword and content based queries efficiently and with high precision. In this paper, we present a music query system - QueST (Query by acouStic and Textual features) to support both keyword and content based retrieval in large music databases. QueST has two distinct features. First, it provides new index schemes that can efficiently handle various queries within a uniform architecture. Concretely, we propose a hybrid structure consisting of Inverted file and Signature file to support keyword search. For content based query, we introduce the notion of similarity to capture various music semantics like melody and genre. We extract acoustic features from a music object, and map it to multiple high-dimension spaces with respect to the similarity notion using PCA and RBF neural network. Second, we design a result fusion scheme, called the Quick Threshold Algorithm, to speed up the processing of complex queries involving both textual and multiple acoustic features. Our experimental results show that QueST offers higher accuracy and efficiency compared to existing algorithms.

REFERENCES

• 1: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 2: A. Chen, M. Chang, J. chen, J. L. Hsu, C. H. Hsu, and S. Huak. Query by music segments: an efficient approach for song retrieval. The Proc. ICME, 2000.
• 3: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 4: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 5: Christos Faloutsos, Signature files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 7: Asif Ghias , Jonathan Logan , David Chamberlin , Brian C. Smith, Query by humming: musical information retrieval in an audio database, Proceedings of the third ACM international conference on Multimedia, p.231-236, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215273]
• 8: Simon Haykin, Neural Networks: A Comprehensive Foundation (3rd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2007
• 9: 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]
• 10: I. T. Jolliffe. Principle Component Analysis. Springer-Verlag, 1986.
• 11: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860449]
• 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: Tao Li , Mitsunori Ogihara , Qi Li, A comparative study on content-based music genre classification, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860487]
• 14: 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
• 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: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 17: G. Peters, C. Anthony, and M. Schwartz. Song search and retrieval by tapping. The American Association for Artificial Intelligence, 2005.
• 18: Jialie Shen , John Shepherd , Anne H.H. Ngu, Integrating heterogeneous reatures for efficient content based music retrieval, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031200]
• 19: 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]
• 20: 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]
• 21: G. Tzanetakis and P. Cook. Musical genre classification of audio signals. In IEEE Transactions on Speech and Audio Processing, pages 293--302, 2002.
• 22: 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
• 23: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 24: Rong Yan , Jun Yang , Alexander G. Hauptmann, Learning query-class dependent weights in automatic video retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027661]
• 25: 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]
• 26: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 27: 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]
• 28: Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998 [doi>10.1145/296854.277632]

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.5 ARTS AND HUMANITIES

General Terms:
Algorithms, Experimentation, Performance

Keywords:
acoustic feature, music, search, similarity notion, textual feature