Querying and mining of time series data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Querying and mining of time series data: experimental comparison of representations and distance measures

Full text

Pdf (1.64 MB)

Source

Proceedings of the VLDB Endowment archive
Volume 1 , Issue 2 (August 2008) table of contents

SESSION: EXPERIMENTS AND ANALYSES table of contents

Pages 1542-1552

Year of Publication: 2008

ISSN:2150-8097

Authors

Hui Ding	Northwestern University, Evanston, IL
Goce Trajcevski	Northwestern University, Evanston, IL
Peter Scheuermann	Northwestern University, Evanston, IL
Xiaoyue Wang	University of California, Riverside, CA
Eamonn Keogh	University of California, Riverside, CA

Publisher

VLDB Endowment

Bibliometrics

Downloads (6 Weeks): 38, Downloads (12 Months): 271, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1454159.1454226 What is a DOI?

ABSTRACT

The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Additional Experiment Results for Representation and Similarity Measures of Time Series. http://www.ece.northwestern.edu/~hdi117/tsim.htm.
	2	R. T. Ng (2006), Note of Caution. http://www.cs.ubc.ca/~rng/psdepository/chebyReport2.pdf.
	3	H. André-Jönsson and D. Z. Badal. Using signature files for querying time-series data. In PKDD, 1997.
	4	J. Aßfalg, H.-P. Kriegel, P. Kröger, P. Kunath, A. Pryakhin, and M. Renz. Similarity search on time series based on threshold queries. In EDBT, 2006.
	5	D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In KDD Workshop, 1994.
	6	Yuhan Cai , Raymond Ng, Indexing spatio-temporal trajectories with Chebyshev polynomials, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007636]
	7	M. Cardle. Automated motion editing. In Technical Report, Computer Laboratory, University of Cambridge, UK, 2004.
	8	Lei Chen , Raymond Ng, On the marriage of Lp-norms and edit distance, Proceedings of the Thirtieth international conference on Very large data bases, p.792-803, August 31-September 03, 2004, Toronto, Canada
	9	Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
	10	Lei Chen , M. Tamer Öszu , Vincent Oria, Using multi-scale histograms to answer pattern existence and shape match queries, Proceedings of the 17th international conference on Scientific and statistical database management, p.217-226, June 27-29, 2005, Santa Barbara, CA
	11	Qiuxia Chen , Lei Chen , Xiang Lian , Yunhao Liu , Jeffrey Xu Yu, Indexable PLA for efficient similarity search, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	12	Y. Chen, M. A. Nascimento, B. C. Ooi, and A. K. H. Tung. SpADe: On Shape-based Pattern Detection in Streaming Time Series. In ICDE, 2007.
	13	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
	14	E. Frentzos, K. Gratsias, and Y. Theodoridis. Index-based most similar trajectory search. In ICDE, 2007.
	15	Pierre Geurts, Pattern Extraction for Time Series Classification, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.115-127, September 03-05, 2001
	16	P. Geurts. Contributions to Decision Tree Induction: bias/variance tradeoff and time series classification. PhD thesis, University of Lige, Belgium, May 2002.
	17	Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
	18	Ioannis Karydis , Alexandros Nanopoulos , Apostolos N. Papadopoulos , Yannis Manolopoulos, Evaluation of similarity searching methods for music data in P2P networks, International Journal of Business Intelligence and Data Mining, v.1 n.2, p.210-228, December 2005 [doi>10.1504/IJBIDM.2005.008363]
	19	Kyoji Kawagoe , Tomohiro Ueda, A Similarity Search Method of Time Series Data with Combination of Fourier and Wavelet Transforms, Proceedings of the Ninth International Symposium on Temporal Representation and Reasoning (TIME'02), p.86, July 07-09, 2002
	20	E. Keogh, X. Xi, L. Wei, and C. Ratanamahatana. The UCR Time Series dataset. In http://www.cs.ucr.edu/~eamonn/time_series_data/, 2006.
	21	Eamonn Keogh, Exact indexing of dynamic time warping, Proceedings of the 28th international conference on Very Large Data Bases, p.406-417, August 20-23, 2002, Hong Kong, China
	22	Eamonn Keogh, A decade of progress in indexing and mining large time series databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	23	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
	24	E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases. Knowl. Inf. Syst., 3(3), 2001.
	25	Eamonn Keogh , Shruti Kasetty, On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration, Data Mining and Knowledge Discovery, v.7 n.4, p.349-371, October 2003 [doi>10.1023/A:1024988512476]
	26	Eamonn Keogh , Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, v.7 n.3, p.358-386, March 2005 [doi>10.1007/s10115-004-0154-9]
	27	Sang-Wook Kim , Sanghyun Park , Wesley W. Chu, An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases, Proceedings of the 17th International Conference on Data Engineering, p.607-614, April 02-06, 2001
	28	R. Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In IJCAI, 1995.
	29	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
	30	Jessica Lin , Eamonn Keogh , Li Wei , Stefano Lonardi, Experiencing SAX: a novel symbolic representation of time series, Data Mining and Knowledge Discovery, v.15 n.2, p.107-144, October 2007 [doi>10.1007/s10618-007-0064-z]
	31	Michael D. Morse , Jignesh M. Patel, An efficient and accurate method for evaluating time series similarity, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247544]
	32	Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
	33	K. pong Chan and A. W.-C. Fu. Efficient Time Series Matching by Wavelets. In ICDE, 1999.
	34	I. Popivanov and R. J. Miller. Similarity Search Over Time-Series Data Using Wavelets. In ICDE, 2002.
	35	C. A. Ratanamahatana and E. J. Keogh. Three myths about dynamic time warping data mining. In SDM, 2005.
	36	Richard O. Duda and Peter E. Hart. Pattern Classification and Scene Analysis. John Wiley & Sons, 1973.
	37	Steven L. Salzberg, On Comparing Classifiers: Pitfalls toAvoid and a Recommended Approach, Data Mining and Knowledge Discovery, v.1 n.3, p.317-328, 1997 [doi>10.1023/A:1009752403260]
	38	Michael Steinbach , Pang-Ning Tan , Vipin Kumar , Steven Klooster , Christopher Potter, Discovery of climate indices using clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956801]
	39	Michail Vlachos , Dimitrios Gunopoulos , George Kollios, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
	40	Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing Multidimensional Time-Series, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.1-20, January 2006 [doi>10.1007/s00778-004-0144-2]
	41	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]
	42	Xiaopeng Xi , Eamonn Keogh , Christian Shelton , Li Wei , Chotirat Ann Ratanamahatana, Fast time series classification using numerosity reduction, Proceedings of the 23rd international conference on Machine learning, p.1033-1040, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143974]
	43	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
	44	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
	45	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]