Warping indexes with envelope transforms for query by humming

ABSTRACT

A Query by Humming system allows the user to find a song by humming part of the tune. No musical training is needed. Previous query by humming systems have not provided satisfactory results for various reasons. Some systems have low retrieval precision because they rely on melodic contour information from the hum tune, which in turn relies on the error-prone note segmentation process. Some systems yield better precision when matching the melody directly from audio, but they are slow because of their extensive use of Dynamic Time Warping (DTW). Our approach improves both the retrieval precision and speed compared to previous approaches. We treat music as a time series and exploit and improve well-developed techniques from time series databases to index the music for fast similarity queries. We improve on existing DTW indexes technique by introducing the concept of envelope transforms, which gives a general guideline for extending existing dimensionality reduction methods to DTW indexes. The net result is high scalability. We confirm our claims through extensive experiments.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: AKoff_Sound_Labs. Ak off music composer version 2.0, http://www.akoff.com/music-composer.html, 2000.
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Donald J. Berndt , James Clifford, Finding patterns in time series: a dynamic programming approach, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 5: Steven Blackburn , David DeRoure, A tool for content based navigation of music, Proceedings of the sixth ACM international conference on Multimedia, p.361-368, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290802]
• 6: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 7: 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
• 8: 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]
• 9: Dina Q. Goldin , Paris C. Kanellakis, On Similarity Queries for Time-Series Data: Constraint Specification and Implementation, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.137-153, September 19-22, 1995
• 10: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 11: 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]
• 12: E. Keogh and T. Folias. The UCR Time Series Data Mining Archive{http://www.cs.ucr.edu/ eamonn/tsdma/index.html}, Riverside CA. University of California - Computer Science and Engineering Department, 2002.
• 13: E. J. Keogh. Exact indexing of dynamic time warping. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20--23, 2002, Hong Kong, China, pages 406--417, 2002.
• 14: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 15: Eamonn Keogh , Shruti Kasetty, On the need for time series data mining benchmarks: a survey and empirical demonstration, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775062]
• 16: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 17: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 18: Naoko Kosugi , Yuichi Nishihara , Tetsuo Sakata , Masashi Yamamuro , Kazuhiko Kushima, A practical query-by-humming system for a large music database, Proceedings of the eighth ACM international conference on Multimedia, p.333-342, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.354520]
• 19: D. Mazzoni and R. B. Dannenberg. Melody matching directly from audio. In 2nd Annual International Symposium on Music Information Retrieval, Bloomington, Indiana, USA, 2001.
• 20: R. J. McNab, L. A. Smith, D. Bainbridge, and I. H. Witten. The new zealand digital library melody index. In D-Lib Magazine, 1997.
• 21: Yang-Sae Moon , Kyu-Young Whang , Wook-Shin Han, General match: a subsequence matching method in time-series databases based on generalized windows, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564735]
• 22: S. Park, W. W. Chu, J. Yoon, and C. Hsu. Fast retrieval of similar sub-sequences under time warping. In ICDE, pages 23--32, 2000.
• 23: I. Popivanov and R. J. Miller. Similarity search over time series data using wavelets. In ICDE, 2002.
• 24: J. Profita and T.G.Bidder. Perfect pitch. In American Journal of Medical Genetics, pages 763--771, 1988.
• 25: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 26: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 27: T. Tolonen and M. Karjalainen. A computationally efficient multi-pitch analysis model. IEEE Transactions on Speech and Audio Processing, 2000.
• 28: 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]
• 29: 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]
• 30: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, A comparison of DFT and DWT based similarity search in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.488-495, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354857]
• 31: 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]
• 32: Byoung-Kee Yi , Christos Faloutsos, Fast Time Sequence Indexing for Arbitrary Lp Norms, Proceedings of the 26th International Conference on Very Large Data Bases, p.385-394, September 10-14, 2000
• 33: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998
• 34: Yongwei Zhu , Mohan S. Kankanhalli , Changsheng Xu, Pitch Tracking and Melody Slope Matching for Song Retrieval, Proceedings of the Second IEEE Pacific Rim Conference on Multimedia: Advances in Multimedia Information Processing, p.530-537, October 24-26, 2001
• 35: Y. Zhu and D. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20--23, 2002, Hong Kong, China, pages 358--369, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.5 Sound and Music Computing

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

General Terms:
Algorithms, Design, Experimentation, Performance