Similarity-based queries for time series data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Similarity-based queries for time series data

Full text

Pdf (1.17 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1997 ACM SIGMOD international conference on Management of data table of contents

Tucson, Arizona, United States

Pages: 13 - 25

Year of Publication: 1997

ISBN:0-89791-911-4

Also published in ...

Authors

Davood Rafiei	Department of Computer Science, University of Toronto
Alberto Mendelzon	Department of Computer Science, University of Toronto

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 81, Citation Count: 70

Additional Information:

abstract 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/253260.253264 What is a DOI?

ABSTRACT

We study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as moving average and time warping. We present a query processing algorithm that uses the underlying R-tree index of a multidimensional data set to answer similarity queries efficiently. Our experiments show that the performance of this algorithm is competitive to that of processing ordinary (exact match) queries using the index, and much faster than sequential scanning. We relate our transformations to the general framework for similarity queries of Jagadish et al.

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.

	AFS93	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
	ALSS95	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
	APWZ95	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
	BKSS90	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
	EM69	R.D. Edwards and J. Magee. Technical analysis of stock trends. John Magee, Springfield, Massachsetts, 1969.
	FJMM95	C. Faloutsos, H. V. Jagadish, A. O. Mendelzon, and T. Milo. A signature technique for similarity-based queries, technical report 112530-951110-16TM, AT&T, Murray Hill, NJ, November 1995.
	FRM94	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
	GK95	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
	Gut84	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
	Jag91	H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
	JMM95	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]
	OS75	Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	RKV95	Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
	Rot93	William G. Roth. MIMSY: A system for analyzing time series data in the stock market domain. University of Wisconsin, Madison, 1993. Master Thesis.
	RS92	Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 23-27, 1992
	SK83	David Sankoff and Joseph B. Kruskal. Time Warps, String Edits, and Macromolecules: The Theory and Practice o.f Sequence Comparison. Addison-Wesley Publishing Company, 1983.

CITED BY 70

	Sanghyun Park , Sang-Wook Kim , Wesley W. Chu, Segment-based approach for subsequence searches in sequence databases, Proceedings of the 2001 ACM symposium on Applied computing, p.248-252, March 2001, Las Vegas, Nevada, United States
	Alex Nanopoulos , Rob Alcock , Yannis Manolopoulos, Feature-based classification of time-series data, Information processing and technology, Nova Science Publishers, Inc., Commack, NY, 2001
	Yunyao Qu , Changzhou Wang , Like Gao , X. Sean Wang, Supporting Movement Pattern Queries in User-Specified Scales, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.26-42, January 2003
	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
	Chung-Sheng Li , Philip S. Yu , Vittorio Castelli, MALM: a framework for mining sequence database at multiple abstraction levels, Proceedings of the seventh international conference on Information and knowledge management, p.267-272, November 02-07, 1998, Bethesda, Maryland, United States
	Xiaoming Jin , Yuchang Lu , Chunyi Shi, Similarity measure based on partial information of time series, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	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
	Like Gao , X. Sean Wang, Continually evaluating similarity-based pattern queries on a streaming time series, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Roy Villafane , Kien A. Hua , Duc Tran , Basab Maulik, Knowledge Discovery from Series of Interval Events, Journal of Intelligent Information Systems, v.15 n.1, p.71-89, July—Aug. 2000
	Yun-Wu Huang , Philip S. Yu, Adaptive query processing for time-series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.282-286, August 15-18, 1999, San Diego, California, United States
	Yunyao Qu , Changzhou Wang , X. Sean Wang, Supporting fast search in time series for movement patterns in multiple scales, Proceedings of the seventh international conference on Information and knowledge management, p.251-258, November 02-07, 1998, Bethesda, Maryland, United States
	Martin Gavrilov , Dragomir Anguelov , Piotr Indyk , Rajeev Motwani, Mining the stock market (extended abstract): which measure is best?, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.487-496, August 20-23, 2000, Boston, Massachusetts, United States
	Sanghyun Park , Sang-Wook Kim , June-Suh Cho , Sriram Padmanabhan, Prefix-querying: an approach for effective subsequence matching under time warping in sequence databases, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Rajeev Rastogi , Kyuseok Shim, Scalable algorithms for mining large databases, Tutorial notes of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-140, August 15-18, 1999, San Diego, California, United States
	Kamil Saraç , Ömer Eğecioǧlu , Amr El Abbadi, Iterated DFT based techniques for join size estimation, Proceedings of the seventh international conference on Information and knowledge management, p.348-355, November 02-07, 1998, Bethesda, Maryland, United States
	Dimitrios Gunopulos , Gautam Das, Time series similarity measures (tutorial PM-2), Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.243-307, August 20-23, 2000, Boston, Massachusetts, United States
	Nirvana Meratnia , Rolf A. de By, Aggregation and comparison of trajectories, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA
	Woong-Kee Loh , Sang-Wook Kim, A subsequence matching algorithm supporting moving average transform of arbitrary order in time-series databases using index interpolation, Proceedings of the 12th Australasian database conference, p.37-44, January 29-February 01, 2001, Queensland, Australia
	Sang-Wook Kim , Dae-Hyun Park , Heon-Gil Lee, Efficient processing of subsequence matching with the Euclidean metric in time-series databases, Information Processing Letters, v.90 n.5, p.253-260, 15 June 2004
	A. Prasad Sistla , Tao Hu , Vikas Chowdhry, Similarity based retrieval from sequence databases using automata as queries, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	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
	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
	Davood Rafiei , Alberto O. Mendelzon, Efficient retrieval of similar time series, Information organization and databases: foundations of data organization, Kluwer Academic Publishers, Norwell, MA, 2000
	Sweta Pittie , Hillol Kargupta , Byung-Hoon Park, Dependency detection in MobiMine: a systems perspective, Information Sciences—Informatics and Computer Science: An International Journal, v.155 n.3-4, p.227-243, 15 October 2003
	Sangjun Lee , Dongseop Kwon , Sukho Lee, Minimum distance queries for time series data, Journal of Systems and Software, v.69 n.1-2, p.105-113, 01 January 2004
	John F. Roddick , Myra Spiliopoulou, A Survey of Temporal Knowledge Discovery Paradigms and Methods, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.750-767, July 2002
	Tamer Kahveci , Ambuj K. Singh, Optimizing Similarity Search for Arbitrary Length Time Series Queries, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.418-433, April 2004
	Woong-Kee Loh , Sang-Wook Kim , Kyu-Young Whang, Index interpolation: an approach to subsequence matching supporting normalization transform in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.480-487, November 06-11, 2000, McLean, Virginia, United States
	Sanghyun Park , Wesley W. Chu , Jeehee Yoon , Jungim Won, Similarity search of time-warped subsequences via a suffix tree, Information Systems, v.28 n.7, p.867-883, 1 October 2003
	Philip (Flip) Korn , Nicholas Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast and Effective Retrieval of Medical Tumor Shapes, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.889-904, November 1998
	Sang-Wook Kim , Sanghyun Park , Wesley W. Chu, Efficient processing of similarity search under time warping in sequence databases: an index-based approach, Information Systems, v.29 n.5, p.405-420, July 2004
	Lilian Harada, Detection of complex temporal patterns over data streams, Information Systems, v.29 n.6, p.439-459, September 2004
	Anastassia Ailamaki , Christos Faloutos , Paul S. Fischbeck , Mitchell J. Small , Jeanne VanBriesen, An environmental sensor network to determine drinking water quality and security, ACM SIGMOD Record, v.32 n.4, December 2003
	Huanmei Wu , Betty Salzberg , Donghui Zhang, Online event-driven subsequence matching over financial data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Like Gao , Zhengrong Yao , X. Sean Wang, Evaluating continuous nearest neighbor queries for streaming time series via pre-fetching, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Sang-Wook Kim , Jeehee Yoon , Sanghyun Park , Tae-Hoon Kim, Shape-based retrieval of similar subsequences in time-series databases, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Dina Q. Goldin , Todd D. Millstein , Ayferi Kutlu, Bounded similarity querying for time-series data, Information and Computation, v.194 n.2, p.203-241, November 1, 2004
	Rui Zhang , Panos Kalnis , Beng Chin Ooi , Kian-Lee Tan, Generalized multidimensional data mapping and query processing, ACM Transactions on Database Systems (TODS), v.30 n.3, p.661-697, September 2005
	Davood Rafiei , Alberto O. Mendelzon, Querying Time Series Data Based on Similarity, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.675-693, September 2000
	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
	Franky Kin-Pong Chan , Ada Wai-chee Fu , Clement Yu, Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.686-705, March 2003
	Richard Cole , Dennis Shasha , Xiaojian Zhao, Fast window correlations over uncooperative time series, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Like Gao , Xiaoyang Sean Wang, Continuous Similarity-Based Queries on Streaming Time Series, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1320-1332, October 2005
	Huanmei Wu , Betty Salzberg , Gregory C Sharp , Steve B Jiang , Hiroki Shirato , David Kaeli, Subsequence matching on structured time series data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Mi Zhou , Man Hon Wong, A segment-wise time warping method for time scaling searching, Information Sciences—Informatics and Computer Science: An International Journal, v.173 n.1-3, p.227-254, 16 June 2005
	Chang-Ryong Kim , Chin-Wan Chung, XMage: an image retrieval method based on partial similarity, Information Processing and Management: an International Journal, v.42 n.2, p.484-502, March 2006
	Sang-Wook Kim , Jeehee Yoon , Sanghyun Park , Jung-Im Won, Shape-based retrieval in time-series databases, Journal of Systems and Software, v.79 n.2, p.191-203, February 2006
	Mi Zhou , Man-Hon Wong , Kam-Wing Chu, A geometrical solution to time series searching invariant to shifting and scaling, Knowledge and Information Systems, v.9 n.2, p.202-229, February 2006
	Paul W. H. Kwan , Junbin Gao, A multi-step strategy for approximate similarity search in image databases, Proceedings of the 17th Australasian Database Conference, p.139-147, January 16-19, 2006, Hobart, Australia
	Clifford K. F. So , George Baciu, Hypercube sweeping algorithm for subsequence motion matching in large motion databases, Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, June 14-April 17, 2006, Hong Kong, China
	T. V. Ashwin , Rahul Gupta , Sugata Ghosal, Adaptable similarity search using non-relevant information, Proceedings of the 28th international conference on Very Large Data Bases, p.47-58, August 20-23, 2002, Hong Kong, China
	Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China
	Richi Nayak , Paul te Braak, Temporal pattern matching for the prediction of stock prices, Proceedings of the 2nd international workshop on Integrating artificial intelligence and data mining, p.95-103, December 01-01, 2007, Gold Coast, Australia
	Sanghyun Park , Sang-Wook Kim, Prefix-querying with anL1 distance metric for time-series subsequence matching under time warping, Journal of Information Science, v.32 n.5, p.387-399, October 2006
	Hansheng Lei , Venu Govindaraju, Generalized regression model for sequence matching and clustering, Knowledge and Information Systems, v.12 n.1, p.77-94, May 2007
	Changzhou Wang , X. Sean Wang, Indexing very high-dimensional sparse and quasi-sparse vectors for similarity searches, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.4, p.344-361, April 2001
	Y. Ogras , Hakan Ferhatosmanoglu, Online summarization of dynamic time series data, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.84-98, January 2006
	Davood Rafiei , Alberto O. Mendelzon, Efficient retrieval of similar shapes, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.17-27, August 2002
	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
	Woong-Kee Loh , Sang-Wook Kim , Kyu-Young Whang, A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases, Data Mining and Knowledge Discovery, v.9 n.1, p.5-28, July 2004
	Vassilis Athitsos , Panagiotis Papapetrou , Michalis Potamias , George Kollios , Dimitrios Gunopulos, Approximate embedding-based subsequence matching of time series, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Jau-hong Kao , Jen-hui Chuang , Tsaipei Wang, Chromosome classification based on the band profile similarity along approximate medial axis, Pattern Recognition, v.41 n.1, p.77-89, January, 2008
	Seung-Hwan Lim , Heejin Park , Sang-Wook Kim, Using multiple indexes for efficient subsequence matching in time-series databases, Information Sciences: an International Journal, v.177 n.24, p.5691-5706, December, 2007
	Jong-Won Roh , Byoung-Kee Yi, Efficient indexing of interval time sequences, Information Processing Letters, v.109 n.1, p.1-12, December, 2008
	Reza Sherkat , Davood Rafiei, On efficiently searching trajectories and archival data for historical similarities, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	B. Aditya Prakash , Nicholas Valler , David Andersen , Michalis Faloutsos , Christos Faloutsos, BGP-lens: patterns and anomalies in internet routing updates, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Srikanth Kandula , Ratul Mahajan , Patrick Verkaik , Sharad Agarwal , Jitendra Padhye , Paramvir Bahl, Detailed diagnosis in enterprise networks, ACM SIGCOMM Computer Communication Review, v.39 n.4, October 2009
	Sorabh Gandhi , Suman Nath , Subhash Suri , Jie Liu, GAMPS: compressing multi sensor data by grouping and amplitude scaling, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Francesco Gullo , Giovanni Ponti , Andrea Tagarelli , Sergio Greco, A time series representation model for accurate and fast similarity detection, Pattern Recognition, v.42 n.11, p.2998-3014, November, 2009
	Panagiotis Papapetrou , Paul Doliotis , Vassilis Athitsos, Towards faster activity search using embedding-based subsequence matching, Proceedings of the 2nd International Conference on PErvsive Technologies Related to Assistive Environments, p.1-8, June 09-13, 2009, Corfu, Greece