Efficient K-NN search in polyphonic music databases using a lower bounding mechanism

ABSTRACT

Querying polyphonic music from a large data collection is an interesting and challenging topic. Recently, researchers attempt to provide efficient techniques for content-based retrieval in polyphonic music databases where queries can also be polyphonic. However, most of the techniques do not perform the approximate matching well. In this paper, we present a novel method to efficiently retrieve k music works that contain segments most similar to the user query based on the edit distance. A list-based index structure is first constructed using the feature of the polyphony. A set of candidate approximate answers is then generated for the user query. A lower bounding mechanism is proposed to prune these candidates such that the k answers can be obtained efficiently. The efficiency of the proposed method is evaluated by real data set and synthetic data set, reporting significant improvement over existing approaches in the response time yielded.

REFERENCES

• 1: M. Clausen, R. Engelbrecht, D. Meyer and J. Schmitz. Proms: A web-based tool for searching in polyphonic music. In Proceedings of the 1st International Symposium on Music Information Retrieval (ISMIR), 2000.
• 2: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 3: M. J. Dovey. A technique for "regular expression" style searching in polyphonic music. In Proceedings of the 2nd International Symposium on Music Information Retrieval (ISMIR), 2001.
• 4: Stephen Downie , Michael Nelson, Evaluation of a simple and effective music information retrieval method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.73-80, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345551]
• 5: 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]
• 6: A. Kornstadt. Themefinder: A Web-Based Melodic Search Tool. Computing in Musicology 11, MIT Press, 1998.
• 7: K. Lemström and S. Perttu. SEMEX -- An Efficient Music Retrieval Prototype. In Proceedings of the 1st International Symposium on Music Information Retrieval (ISMIR), 2000.
• 8: C. C. Liu, J. L. Hsu and A. L. P. Chen. An Approximate String Matching Algorithm for Content-based Music Data Retrieval. In Proceedings of International Conferences on Multimedia Computing and Systems (ICMCS), 1999.
• 9: R. J. MacNab, L. A. Smith, D. Bainbridge and I. H. Witten. The New Zealand Digital Library MELodyinDEX. Digital Library Magazine, May 1997.
• 10: 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]
• 11: MIDI Manufaturers Association, Los Angeles, California. The Complete Detailed MIDI 1.0 Specification, 1996.
• 12: Chihcheng Hsu, Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases, Proceedings of the 16th International Conference on Data Engineering, p.23, February 28-March 03, 2000
• 13: J. Pickens. A Survey of Feature Selection Techniques for Music Information Retrieval. In Proceedings of the 2nd International Symposium on Music Information Retrieval (ISMIR), 2001.
• 14: Jeremy Pickens , Tim Crawford, Harmonic models for polyphonic music retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584863]
• 15: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 16: Alexandra Uitdenbgerd , 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]
• 17: G. Wiggins, E. Miranda, A. Smaill and M. Harris. A framework for the evaluation of music representation systems, Computer Music Journal, 17(3): 31--42, 1997.
• 18: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

General Terms:
Algorithms, Management, Performance

Keywords:
indexing methods, lower bounded edit distance, polyphonic music information retrieval, search process