Fast time-series searching with scaling and shifting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast time-series searching with scaling and shifting

Full text

Pdf (1.25 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Philadelphia, Pennsylvania, United States

Pages: 237 - 248

Year of Publication: 1999

ISBN:1-58113-062-7

Authors

Kelvin Kam Wing Chu	Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, China
Man Hon Wong	Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, China

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 66, Citation Count: 39

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/303976.304000 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	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	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
	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	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]
	5	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
	6	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
	7	Hagit Shatkay , Stanley B. Zdonik, Approximate Queries and Representations for Large Data Sequences, Proceedings of the Twelfth International Conference on Data Engineering, p.536-545, February 26-March 01, 1996
	8	Chung-Sheng Li , Philip S. Yu , Vittorio Castelli, HierarchyScan: A Hierarchical Similarity Search Algorithm for Databases of Long Sequences, Proceedings of the Twelfth International Conference on Data Engineering, p.546-553, February 26-March 01, 1996
	9	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]
	10	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
	11	S. K. Lain and M. H. Wong. A Fast Signature Algorithm for Sequence Data Searching. In The Third International Workshop on Next Generation Information Technologies and Systems, pages 172-181, 1997.
	12	Sze Kin Lam , Man Hon Wong, A fast projection algorithm for sequence data searching, Data & Knowledge Engineering, v.28 n.3, p.321-339, Dec. 15, 1998 [doi>10.1016/S0169-023X(98)00023-8]
	13	K.W. Chu, S.K. Lam, and M.H. Wong. An Efficient Hash-based Algorithm for Sequence Data Searching. The Computer Journal, 41:402-415, 1998.
	14	Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
	15	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]
	16	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
	17	K. Shim, R. Srikant, and R. Agrawal. A Fast Algorithm for high-dimensional Similarity Joins. Technical report, IBM Almaden Research Center, 1996.
	18	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
	19	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
	20	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
	21	H. F. Davis and A. D. Snider. Introduction to Vector Analysis. Win. C. Brown Publishers, 1995.
	22	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
	23	Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
	24	J. B. Fraleigh and R. A. Beauregard. Linear Algebra. Addison Wesley, 1995.
	25	Alan Watt, 3d Computer Graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
	26	Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States

CITED BY 39

	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
	Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002
	Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, ACM SIGMOD Record, v.30 n.2, p.151-162, June 2001
	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
	Eamonn Keogh , Selina Chu , Michael Pazzani, Ensemble-index: a new approach to indexing large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.117-125, August 26-29, 2001, San Francisco, California
	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
	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
	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
	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
	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
	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
	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
	Polly Wan Po Man , Man Hon Wong, Efficient and robust feature extraction and pattern matching of time series by a lattice structure, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	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
	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
	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
	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
	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
	Sang-Wook Kim , Byeong-Soo Jeong, Performance bottleneck in time-series subsequence matching, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Durga Toshniwal , Ramesh C. Joshi, Finding similarity in time series data by method of time weighted moments, Proceedings of the sixteenth Australasian database conference, p.155-164, January 01, 2005, Newcastle, Australia
	Michail Vlachos , George Kollios , Dimitrios Gunopulos, Elastic Translation Invariant Matching of Trajectories, Machine Learning, v.58 n.2-3, p.301-334, February 2005
	Man-Soon Kim , Sang-Wook Kim , Miyoung Shin, Optimization of subsequence matching under time warping in time-series databases, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	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
	Hansheng Lei , Venu Govindaraju, Matching and retrieving sequential patterns using regression, Web Intelligence and Agent System, v.3 n.4, p.261-270, January 2005
	Alon Efrat , Quanfu Fan , Suresh Venkatasubramanian, Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves, Journal of Mathematical Imaging and Vision, v.27 n.3, p.203-216, April 2007
	Christos Theoharatos , Apostolos Ifantis , Nikolaos A. Laskaris , George Economou, Charting of geoelectric potential signal dynamics via geometrical techniques and its possible relation to significant earthquakes in Western Greece, Computers & Geosciences, v.34 n.6, p.625-634, June, 2008
	Matthew S. Allen , John Brevik , Rich Wolski, Comparing network bandwidth time-series, Proceedings of the first international conference on Networks for grid applications, October 17-19, 2007, Lyon, France
	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
	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
	Esa Alhoniemi, Simplified time series representations for efficient analysis of industrial process data, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.17 n.2, p.103-114, April 2003
	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
	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
	Tak-chung Fu , Fu-lai Chung , Robert Luk , Chak-man Ng, Representing financial time series based on data point importance, Engineering Applications of Artificial Intelligence, v.21 n.2, p.277-300, March, 2008
	Yang-Sae Moon , Jinho Kim, Efficient moving average transform-based subsequence matching algorithms in time-series databases, Information Sciences: an International Journal, v.177 n.23, p.5415-5431, December, 2007
	eljko Jagnjić , Nikola Bogunović , Ivanka Pieta , Franjo Jović, Time series classification based on qualitative space fragmentation, Advanced Engineering Informatics, v.23 n.1, p.116-129, January, 2009
	Yang-Sae Moon , Jinho Kim, Fast Normalization-Transformed Subsequence Matching in Time-Series Databases, IEICE - Transactions on Information and Systems, v.E90-D n.12, p.2007-2018, December 2007
	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