research-article

Benchmarking dynamic time warping for music retrieval

Authors:

Jefrey Lijffijt,

Panagiotis Papapetrou,

Jaakko Hollmén,

Vassilis AthitsosAuthors Info & Claims

PETRA '10: Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments

Article No.: 59, Pages 1 - 7

https://doi.org/10.1145/1839294.1839365

Published: 23 June 2010 Publication History

Abstract

We study the performance of three dynamic programming methods on music retrieval. The methods are designed for time series matching but can be directly applied to retrieval of music. Dynamic Time Warping (DTW) identifies an optimal alignment between two time series, and computes the matching cost corresponding to that alignment. Significant speed-ups can be achieved by constrained Dynamic Time Warping (cDTW), which narrows down the set of positions in one time series that can be matched with specific positions in the other time series. Both methods are designed for full sequence matching but can also be applied for subsequence matching, by using a sliding window over each database sequence to compute a matching score for each database subsequence. In addition, SPRING is a dynamic programming approach designed for subsequence matching, where the query is matched with a database subsequence without requiring the match length to be equal to the query length. SPRING has a lower computational cost than DTW and cDTW. Our database consists of a set of MIDI files taken from the web. Each MIDI file has been converted to a 2-dimensional time series, taking into account both note pitches and durations. We have used synthetic queries of fixed size and different noise levels. Surprisingly, when looking for the top-K best matches, all three approaches show similar behavior in terms of retrieval accuracy for small values of K. This suggests that for the specific application area, a computationally cheaper method, such as SPRING, is sufficient to retrieve the best top-K matches.

References

[1]

T. Argyros and C. Ermopoulos. Efficient subsequence matching in time series databases under time and amplitude transformations. In International Conference on Data Mining, pages 481--484, 2003.

Digital Library

[2]

V. Athitsos, P. Papapetrou, M. Potamias, G. Kollios, and D. Gunopulos. Approximate embedding-based subsequence matching of time series. In ACM SIGMOD, 2008.

Digital Library

[3]

D. Bainbridge. MELDEX: A Web-based Melodic Locator Service. Computing in Musicology, 11:223--229, 1998.

[4]

R. Bellman. The theory of dynamic programming. Bull. Amer. Math. Soc., 60(6):503--515, 1954.

[5]

L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In SPIRE'00: Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), pages 39--48.

Digital Library

[6]

B. Bollobás, G. Das, D. Gunopulos, and H. Mannila. Time-series similarity problems and well-separated geometric sets. In Proceedings of the thirteenth annual symposium on Computational geometry, pages 454--456. ACM New York, NY, USA, 1997.

Digital Library

[7]

K.-P. Chan and A. W.-C. Fu. Efficient time series matching by wavelets. In ICDE, pages 126--133, 1999.

Digital Library

[8]

L. Chen and R. T. Ng. On the marriage of lp-norms and edit distance. In VLDB, pages 792--803, 2004.

Digital Library

[9]

L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In SIGMOD Conference, pages 491--502, 2005.

Digital Library

[10]

R. Dannenberg and N. Hu. Understanding search performance in query-by-humming systems. In Proc. ISMIR, pages 232--237, 2004.

[11]

C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In ACM International Conference on Management of Data (SIGMOD), pages 419--429, 1994.

Digital Library

[12]

W. Gao, G. Fang, D. Zhao, and Y. Chen. Transition movement models for large vocabulary continuous sign language recognition. In Automatic Face and Gesture Recognition, pages 553--558, 2004.

Digital Library

[13]

Z. Ghahramani and M. I. Jordan. Factorial hidden markov models. Machine Learning, 29:245--275, 1997.

Digital Library

[14]

E. Keogh. Exact indexing of dynamic time warping. In International Conference on Very Large Data Bases, pages 406--417, 2002.

Digital Library

[15]

E. Keogh and M. Pazzani. Scaling up dynamic time warping for data mining applications. In Proc. of SIGKDD, 2000.

Digital Library

[16]

J. B. Kruskall and M. Liberman. The symmetric time warping algorithm: From continuous to discrete. In Time Warps. Addison-Wesley, 1983.

[17]

L. Latecki, V. Megalooikonomou, Q. Wang, R. Lakämper, C. Ratanamahatana, and E. Keogh. Elastic partial matching of time series. In PKDD, pages 577--584, 2005.

Digital Library

[18]

K. Lemström and E. Ukkonen. Including interval encoding into edit distance based music comparison and retrieval. In Proc. AISB, pages 53--60, 2000.

[19]

V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics, 10(8):707--710, 1966.

[20]

D. Mazzoni and R. Dannenberg. Melody matching directly from audio. In 2nd Annual International Symposium on Music Information Retrieval, pages 17--18, 2001.

[21]

Y. Moon, K. Whang, and W. Han. General match: a subsequence matching method in time-series databases based on generalized windows. In ACM International Conference on Management of Data (SIGMOD), pages 382--393, 2002.

Digital Library

[22]

Y. Moon, K. Whang, and W. Loh. Duality-based subsequence matching in time-series databases. In IEEE International Conference on Data Engineering (ICDE), pages 263--272, 2001.

Digital Library

[23]

P. Morguet and M. Lang. Spotting dynamic hand gestures in video image sequences using hidden Markov models. In IEEE International Conference on Image Processing, pages 193--197, 1998.

[24]

M. Morse and J. Patel. An efficient and accurate method for evaluating time series similarity. In SIGMOD Conference, pages 569--580, 2007.

Digital Library

[25]

R. Oka. Spotting method for classification of real world data. The Computer Journal, 41(8):559--565, July 1998.

[26]

B. Pardo, J. Shifrin, and W. Birmingham. Name that tune: A pilot study in finding a melody from a sung query. Journal of the American Society for Information Science and Technology, 55(4):283--300, 2004.

Digital Library

[27]

S. Park, W. W. Chu, J. Yoon, and J. Won. Similarity search of time-warped subsequences via a suffix tree. Information Systems, 28(7), 2003.

Digital Library

[28]

S. Park, S. Kim, and W. W. Chu. Segment-based approach for subsequence searches in sequence databases. In Symposium on Applied Computing, pages 248--252, 2001.

Digital Library

[29]

S. Pauws. Cubyhum: A fully operational query by humming system. In Proceedings of ISMIR, pages 187--196, 2002.

[30]

D. Rafiei and A. O. Mendelzon. Similarity-based queries for time series data. In ACM International Conference on Management of Data (SIGMOD), pages 13--25, 1997.

Digital Library

[31]

C. Ratanamahatana and E. J. Keogh. Three myths about dynamic time warping data mining. In SIAM International Data Mining Conference, 2005.

[32]

H. Sakoe and S. Chiba. In Transactions on ASSP, volume 26, pages 43--49.

[33]

Y. Sakurai, C. Faloutsos, and M. Yamamuro. Stream monitoring under the time warping distance. In IEEE International Conference on Data Engineering (ICDE), 2007.

[34]

Y. Sakurai, M. Yoshikawa, and C. Faloutsos. FTW: fast similarity search under the time warping distance. In Principles of Database Systems (PODS), pages 326--337, 2005.

Digital Library

[35]

J. Shifrin, B. Pardo, C. Meek, and W. Birmingham. HMM-based musical query retrieval. In Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, pages 295--300. ACM New York, NY, USA, 2002.

Digital Library

[36]

L. Smith, R. McNab, and I. Witten. Sequence-based melodic comparison: A dynamic programming approach. Computing in Musicology, 11:101--117, 1998.

[37]

A. Uitdenbogerd and J. Zobel. Melodic matching techniques for large music databases. In Proceedings of the seventh ACM international conference on Multimedia (Part 1), page 66. ACM, 1999.

Digital Library

[38]

E. Unal, E. Chew, P. Georgiou, and S. Narayanan. Challenging uncertainty in query by humming systems: a fingerprinting approach. IEEE Transactions on Audio Speech and Language Processing, 16(2):359, 2008.

Digital Library

[39]

M. Vlachos, D. Gunopulos, and G. Kollios. Discovering similar multidimensional trajectories. In ICDE, pages 673--684, 2002.

Digital Library

[40]

M. Vlachos, M. Hadjieleftheriou, D. Gunopulos, and E. Keogh. Indexing multi-dimensional time-series with support for multiple distance measures. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 216--225, 2003.

Digital Library

[41]

H. Wu, B. Salzberg, G. C. Sharp, S. B. Jiang, H. Shirato, and D. R. Kaeli. Subsequence matching on structured time series data. In ACM International Conference on Management of Data (SIGMOD), pages 682--693, 2005.

Digital Library

[42]

B.-K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In IEEE International Conference on Data Engineering, pages 201--208, 1998.

Digital Library

[43]

Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In ACM International Conference on Management of Data (SIGMOD), pages 181--192, 2003.

Digital Library

Cited By

Kumar ULegendre CZhao LChao B(2022)Dynamic Time Warping as an Alternative to Windowed Cross Correlation in Seismological ApplicationsSeismological Research Letters10.1785/022021028893:3(1909-1921)Online publication date: 28-Mar-2022
https://doi.org/10.1785/0220210288
Mannino MAbouzied AMandryk RHancock MPerry MCox A(2018)Expressive Time Series Querying with Hand-Drawn Scale-Free SketchesProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3173962(1-13)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3173962
Wijayasinghe IRanatunga IBalakrishnan NBugnariu NPopa D(2016)Human–Robot Gesture Analysis for Objective Assessment of Autism Spectrum DisorderInternational Journal of Social Robotics10.1007/s12369-016-0379-28:5(695-707)Online publication date: 11-Oct-2016
https://doi.org/10.1007/s12369-016-0379-2
Show More Cited By

Index Terms

Benchmarking dynamic time warping for music retrieval
1. Information systems
  1. Information systems applications

Recommendations

Flexible Dynamic Time Warping for Time Series Classification

Measuring the similarity or distance between two time series sequences is critical for the classification of a set of time series sequences. Given two time series sequences, X and Y , the dynamic time warping (DTW) algorithm can calculate the distance ...
Melody Information Retrieval System Using Dynamic Time Warping
CSIE '09: Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering - Volume 05

With the increasing popularity of music, there is an intensive need for an efficient and natural way of querying an audio database in order to retrieve the desired songs. This paper presents a system that accepts user input, usually a tune hummed or ...
Approximate embedding-based subsequence matching of time series
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

A method for approximate subsequence matching is introduced, that significantly improves the efficiency of subsequence matching in large time series data sets under the dynamic time warping (DTW) distance measure. Our method is called EBSM, shorthand ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

PETRA '10: Proceedings of the 3rd International Conference on PErvasive Technologies Related to Assistive Environments

June 2010

452 pages

ISBN:9781450300711

DOI:10.1145/1839294

Editors:
Fillia Makedon
University of Texas at Arlington
,
Ilias Maglogiannis
University of Central Greece, Greece
,
Sarantos Kapidakis
Ionian University, Greece

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Information and Intelligent Systems

Conference

PETRA '10

PETRA '10: The 3rd International Conference on PErvasive Technologies Related to Assistive Environments

June 23 - 25, 2010

Samos, Greece

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kumar ULegendre CZhao LChao B(2022)Dynamic Time Warping as an Alternative to Windowed Cross Correlation in Seismological ApplicationsSeismological Research Letters10.1785/022021028893:3(1909-1921)Online publication date: 28-Mar-2022
https://doi.org/10.1785/0220210288
Mannino MAbouzied AMandryk RHancock MPerry MCox A(2018)Expressive Time Series Querying with Hand-Drawn Scale-Free SketchesProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3173962(1-13)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3173962
Wijayasinghe IRanatunga IBalakrishnan NBugnariu NPopa D(2016)Human–Robot Gesture Analysis for Objective Assessment of Autism Spectrum DisorderInternational Journal of Social Robotics10.1007/s12369-016-0379-28:5(695-707)Online publication date: 11-Oct-2016
https://doi.org/10.1007/s12369-016-0379-2
Ranjani SKarthik KBora PAbdulkareem V(2015)Multi-band sum of spectrogram based audio fingerprinting of Indian film songs for multi-lingual song retrieval2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI)10.1109/ICACCI.2015.7275811(1414-1420)Online publication date: Aug-2015
https://doi.org/10.1109/ICACCI.2015.7275811
Sri Ranjani SAbdulkareem VKarthik KBora P(2015)Application of SHAZAM-Based Audio Fingerprinting for Multilingual Indian Song RetrievalAdvances in Communication and Computing10.1007/978-81-322-2464-8_6(81-92)Online publication date: 18-Jun-2015
https://doi.org/10.1007/978-81-322-2464-8_6
Yao GZheng YXiao LRuan LLi YZhang Z(2013)GPU-Accelerated Query by Humming Using Modified SPRING Algorithm2013 IEEE 13th International Conference on Data Mining Workshops10.1109/ICDMW.2013.104(654-663)Online publication date: Dec-2013
https://doi.org/10.1109/ICDMW.2013.104
Xiao LZheng YTang WYao GRuan L(2013)Parallelizing Dynamic Time Warping Algorithm Using Prefix Computations on GPU2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing10.1109/HPCC.and.EUC.2013.50(294-299)Online publication date: Nov-2013
https://doi.org/10.1109/HPCC.and.EUC.2013.50
Stasiak BPapiernik M(2013)Melody-Based Approaches in Music Retrieval and Recommendation SystemsMultimedia Services in Intelligent Environments10.1007/978-3-319-00375-7_9(125-153)Online publication date: 17-May-2013
https://doi.org/10.1007/978-3-319-00375-7_9
Boucheham B(2012)Efficient matching of very complex time seriesInternational Journal of Machine Learning and Cybernetics10.1007/s13042-012-0117-54:5(537-550)Online publication date: 6-Jul-2012
https://doi.org/10.1007/s13042-012-0117-5

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents