Time series similarity measures (tutorial PM-2)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Time series similarity measures (tutorial PM-2)

Full text

Pdf (1.42 MB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Boston, Massachusetts, United States

Pages: 243 - 307

Year of Publication: 2000

ISBN:1-58113-305-7

Authors

Dimitrios Gunopulos	UC, Riverside
Gautam Das	Microsoft Research

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
AAAI : Am Assoc for Artifical Intelligence
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 51, Downloads (12 Months): 378, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/349093.349108 What is a DOI?

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	Andreas Aming, Rakesh Agrawal, Prabhnkar Raghavan: A Linear Method for Deviation Detection in Large Databases. KDD 1996: 164-169.
	2	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
	3	Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
	4	Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
	5	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
	6	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
	7	Donald J. Bemdt, James Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. KDD Workshop 1994.
	8	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
	9	Béla Bollobás , Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Time-series similarity problems and well-separated geometric sets, Proceedings of the thirteenth annual symposium on Computational geometry, p.454-456, June 04-06, 1997, Nice, France [doi>10.1145/262839.263080]
	10	Tolga Bozkaya , Meral Ozsoyoglu, Indexing large metric spaces for similarity search queries, ACM Transactions on Database Systems (TODS), v.24 n.3, p.361-404, Sept. 1999 [doi>10.1145/328939.328959]
	11	Tolga Bozkaya , Nasser Yazdani , Meral Özsoyoğlu, Matching and indexing sequences of different lengths, Proceedings of the sixth international conference on Information and knowledge management, p.128-135, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266880]
	12	Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
	13	Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
	14	Chan K, Fu W. "Efficient time series matching by wavelets", ICDE 1999.
	15	Kelvin Kam Wing Chu , Man Hon Wong, Fast time-series searching with scaling and shifting, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-248, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304000]
	16	C.-W. Chung, S.-L. Lee, S.-J. Chun, D.-H. Kim, J.-H. Lee. Similarity Search for Multidimensional Data Sequences, ICDE 2000.
	17	Gautam Das , Rudolf Fleischer , Leszek Gasieniec , Dimitrios Gunopulos , Juha Kärkkäinen, Episode Matching, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.12-27, June 30-July 02, 1997
	18	Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Finding Similar Time Series, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.88-100, June 24-27, 1997
	19	Gautam Das, King-lp Lin, Heikki Mannila, Gopul Renganathan, Padhraic Smyth: Rule Discovery from Time Series. KDD 1998: 16-22.
	20	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
	21	Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
	22	Christos Faloutsos, Searching Multimedia Databases by Content, Kluwer Academic Publishers, Norwell, MA, 1996
	23	C. Faloutsos , H. Jagadish , A. Mendelzon , T. Milo, A Signature Technique for Similarity-Based Queries, Proceedings of the Compression and Complexity of Sequences 1997, p.2, June 11-13, 1997
	24	Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	25	Xianping Ge , Padhraic Smyth, Deformable Markov model templates for time-series pattern matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.81-90, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347109]
	26	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
	27	Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
	28	Steven L. Horowitz , Theodosios Pavlidis, Picture Segmentation by a Tree Traversal Algorithm, Journal of the ACM (JACM), v.23 n.2, p.368-388, April 1976 [doi>10.1145/321941.321956]
	29	Efficient Mining of Partial Periodic Patterns in Time Series Database, Proceedings of the 15th International Conference on Data Engineering, p.106, March 23-26, 1999
	30	Imager Wavelet Library. www.cs.uhe.catnest/imager/contribations/bobl/wvlt/top.html.
	31	P. Indyk, M. Gavrilov, R. Motwani, and D. Angelov, Mining Stock Market Data: Cluster Discovery. SIGKDD 2000.
	32	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	33	Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
	34	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	35	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	36	H. V. Jagadish , Alberto O. Mendelzon , Tova Milo, Similarity-based queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.36-45, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212444]
	37	H. V. Jagadish , Nick Koudas , S. Muthukrishnan, Mining Deviants in a Time Series Database, Proceedings of the 25th International Conference on Very Large Data Bases, p.102-113, September 07-10, 1999
	38	W.B. Johnson and J. Lindenstrauss, "Extensions of Lipshitz mapping into Hilher t space", Contemporary Mathematics, 26(1984), 189-206.
	39	K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
	40	Kaufman, Rousseauw: "Finding Groups in Dat: an Introduction to Cluster Analysis" John Wiley and Sons, 1995.
	41	Eamolm J. Keogh, Michael J. Pazzani: An Enhanced Representation of Time Series Which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. KDD 1998: 239-243.
	42	Eamonn J. Keogh , Michael J. Pazzani, An Indexing Scheme for Fast Similarity Search in Large Time Series Databases, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.56, July 28-30, 1999 [doi>10.1109/SSDM.1999.787621]
	43	Eamonn J. Keogh, Padbraic Smyth: A Probabilistic Approach to Fast Pattern Matching in Time Series Databases. KDD 1997: 24-30.
	44	Eamonn Keogh, Kaushik Chakrabarti, Michael Pazzani and Sharad Mehrotra, "Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases", Submitted for publication.
	45	E. Keogh, Fast similarity search in the presence of longitudinal scaling in time series databases, Proceedings of the 9th International Conference on Tools with Artificial Intelligence, p.578, November 03-08, 1997
	46	Keogh, E. (1997). A fast and robust method for pattern matching in tirm series database. In WUSS 1997.
	47	Eamonn J. Keogh , Michael J. Pazzani, Scaling up dynamic time warping for datamining applications, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.285-289, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347153]
	48	Eamonn J. Keogh , Michael J. Pazzani, A Simple Dimensionality Reduction Technique for Fast Similarity Search in Large Time Series Databases, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.122-133, April 18-20, 2000
	49	Eamonn J. Keogh , Michael J. Pazzani, Scaling up Dynamic Time Warping to Massive Dataset, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.1-11, September 15-18, 1999
	50	Eamonn J. Keogh , Michael J. Pazzani, Relevance feedback retrieval of time series data, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.183-190, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312676]
	51	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
	52	Vikrant Kobla, David S. Doermann, King-Ip Lin, Christos Faloutsos: Compressed-Domain Video Indexing Techniques Using DCT and Morion Vector Information in MPEG Video. Storage and Retrieval for Image and Video Databases (SPIE) 1997: 200-211.
	53	King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
	54	Alexandros Nanopoulos , Yannis Manolopoulos, Indexing Time-Series Databases for Inverse Queries, Proceedings of the 9th International Conference on Database and Expert Systems Applications, p.551-560, August 24-28, 1998
	55	S. Park, W. Chu, J. Yoon, C. Hsu, Efficient Similarity Searches for Time-Warped Subsequeuces in Sequence Databases, ICDE 2000.
	56	C.-S. Pemg, H. Wang, S. R. Zhang, D. Stutt Parker Landmarks: a New Model for Similarity-based Pattern Querying in Time Series Databases, ICDE 2000.
	57	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
	58	D. Rafiei and Alberto Mendelzon, "Efficient Retrieval of Similar Time Sequences Using DFT' FODO '98 Conference, Kobe, Japan, November 1998.
	59	On Similarity-Based Queries for Time Series Data, Proceedings of the 15th International Conference on Data Engineering, p.410, March 23-26, 1999
	60	Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
	61	Dennis Sbasha. FinTime - a financial time series benchmark, http:llwww.cs.nyu.edulcslfacultylshasha/fmtime.html
	62	Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal, High-Dimensional Similarity Joins, Proceedings of the Thirteenth International Conference on Data Engineering, p.301-311, April 07-11, 1997
	63	Zbigniew R. Struzik , Arno Siebes, The Haar Wavelet Transform in the Time Series Similarity Paradigm, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.12-22, September 15-18, 1999
	64	Alexander Thomasian , Vittorio Castelli , Chung-Sheng Li, Clustering and singular value decomposition for approximate indexing in high dimensional spaces, Proceedings of the seventh international conference on Information and knowledge management, p.201-207, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288658]
	65	Jason Tsong-Li Wang , Xiong Wang , King-Ip Lin , Dennis Shasha , Bruce A. Shapiro , Kaizhong Zhang, Evaluating a class of distance-mapping algorithms for data mining and clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.307-311, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312264]
	66	White paper: Data Mining Best Practice Papers (Sampling, Fraud Detection). SAS Institute.
	67	White, Jain "Algorithms and Strategies for Similarity Retrieval" Tech Report VCL-96-101, Visual Computing Laboratory, UC Dais, 1996.
	68	Christel Wisotzki , Fritz Wysotzki, Prototype, Nearest Neighbor and Hybrid Algorithms for Time Series Classification (Extended Abstract), Proceedings of the 8th European Conference on Machine Learning, p.364-367, April 25-27, 1995
	69	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
	70	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
	71	Yazdani, N, Bozkaya, T. and Ozsoyoglu, Z.M., "Similarity Search for Sequences of Different Lengths: Matching and Indexing", (submitted for publication), 1998.
	72	Nasser Yazdani , Z. Meral Özsoyoglu, Sequence Matching of Images, Proceedings of the Eighth International Conference on Scientific and Statistical Database Management, p.53-62, June 18-20, 1996 [doi>10.1109/SSDM.1996.505915]

CITED BY 3

	Like Gao , Min Wang , X. Sean Wang , Sriram Padmanabhan, A learning-based approach to estimate statistics of operators in continuous queries: a case study, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California
	Yanchang Zhao , Shichao Zhang, Generalized Dimension-Reduction Framework for Recent-Biased Time Series Analysis, IEEE Transactions on Knowledge and Data Engineering, v.18 n.2, p.231-244, February 2006
	Hui Wang, All common subsequences, Proceedings of the 20th international joint conference on Artifical intelligence, p.635-640, January 06-12, 2007, Hyderabad, India