Approximate embedding-based subsequence matching of time series

ABSTRACT

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 for Embedding-Based Subsequence Matching. The key idea is to convert subsequence matching to vector matching using an embedding. This embedding maps each database time series into a sequence of vectors, so that every step of every time series in the database is mapped to a vector. The embedding is computed by applying full dynamic time warping between reference objects and each database time series. At runtime, given a query object, an embedding of that object is computed in the same manner, by running dynamic time warping between the reference objects and the query. Comparing the embedding of the query with the database vectors is used to efficiently identify relatively few areas of interest in the database sequences. Those areas of interest are then fully explored using the exact DTW-based subsequence matching algorithm. Experiments on a large, public time series data set produce speedups of over one order of magnitude compared to brute-force search, with very small losses (< 1%) in retrieval accuracy.

REFERENCES

• 1: J. Alon, V. Athitsos, and S. Sclaroff. Accurate and efficient gesture spotting via pruning and subgesture reasoning. In IEEE Workshop on Human Computer Interaction, pages 189--198, 2005.
• 2: Tassos Argyros , Charis Ermopoulos, Efficient Subsequence Matching in Time Series Databases Under Time and Amplitude Transformations, Proceedings of the Third IEEE International Conference on Data Mining, p.481, November 19-22, 2003
• 3: Vassilis Athitsos , Marios Hadjieleftheriou , George Kollios , Stan Sclaroff, Query-sensitive embeddings, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066238]
• 4: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 5: 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
• 6: Ömer Eğecioğlu , Hakan Ferhatosmanoğlu, Dimensionality reduction and similarity computation by inner product approximations, Proceedings of the ninth international conference on Information and knowledge management, p.219-226, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354822]
• 7: 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
• 8: 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
• 9: 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
• 10: 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
• 11: Wook-Shin Han , Jinsoo Lee , Yang-Sae Moon , Haifeng Jiang, Ranked subsequence matching in time-series databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 12: Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003 [doi>10.1109/TPAMI.2003.1195989]
• 13: Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces (Survey Article), ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003 [doi>10.1145/958942.958948]
• 14: Hristescu Gabriela , Farach Martin, Cluster-preserving Embedding of Proteins, Certer for Discrete Mathematics & Theoretical Computer Science, 1999
• 15: 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
• 16: 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
• 17: 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]
• 18: E. Keogh, X. Xi, L. Wei, and C. A. Ratanamahatana. The UCR time series classification/clustering homepage: www.cs.ucr.edu/~eamonn/time_series_data/, 2006.
• 19: Nick Koudas , Beng Chin Ooi , Heng Tao Shen , Anthony K. H. Tung, LDC: Enabling Search By Partial Distance In A Hyper-Dimensional Space, Proceedings of the 20th International Conference on Data Engineering, p.6, March 30-April 02, 2004
• 20: J. B. Kruskall and M. Liberman. The symmetric time warping algorithm: From continuous to discrete. In Time Warps. Addison-Wesley, 1983.
• 21: Hyeon-Kyu Lee , Jin H. Kim, An HMM-Based Threshold Model Approach for Gesture Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.10, p.961-973, October 1999 [doi>10.1109/34.799904]
• 22: Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002 [doi>10.1109/TKDE.2002.1019214]
• 23: 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 [doi>10.1145/564691.564735]
• 24: Yang-Sae Moon , Kyu-Young Whang , Woong-Kee Loh, Duality-Based Subsequence Matching in Time-Series Databases, Proceedings of the 17th International Conference on Data Engineering, p.263-272, April 02-06, 2001
• 25: 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.
• 26: R. Oka. Spotting method for classification of real world data. The Computer Journal, 41(8):559--565, July 1998.
• 27: 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 [doi>10.1016/S0306-4379(02)00102-3]
• 28: 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 [doi>10.1145/372202.372334]
• 29: 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
• 30: T. M. Rath and R. Manmatha. Word image matching using dynamic time warping. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 2, pages 521--527, 2003.
• 31: Y. Sakurai, C. Faloutsos, and M. Yamamuro. Stream monitoring under the time warping distance. In IEEE International Conference on Data Engineering (ICDE), 2007.
• 32: Yasushi Sakurai , Masatoshi Yoshikawa , Christos Faloutsos, FTW: fast similarity search under the time warping distance, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065210]
• 33: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 34: Yutao Shou , Nikos Mamoulis , David W. Cheung, Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations, Machine Learning, v.58 n.2-3, p.231-267, February 2005 [doi>10.1007/s10994-005-5828-3]
• 35: Ertem Tuncel , Hakan Ferhatosmanoglu , Kenneth Rose, VQ-index: an index structure for similarity searching in multimedia databases, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641117]
• 36: Jayendra Venkateswaran , Deepak Lachwani , Tamer Kahveci , Christopher Jermaine, Reference-based indexing of sequence databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 37: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, 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.956777]
• 38: X. Wang, J. T. L. Wang, K. I. Lin, D. Shasha, B. A. Shapiro, and K. Zhang. An index structure for data mining and clustering. Knowledge and Information Systems, 2(2):161--184, 2000.
• 39: Roger Weber , Klemens Böhm, Trading Quality for Time with Nearest Neighbor Search, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.21-35, March 27-31, 2000
• 40: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 41: D. A. White and R. Jain. Similarity indexing: Algorithms and performance. In Storage and Retrieval for Image and Video Databases (SPIE), pages 62--73, 1996.
• 42: 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 [doi>10.1145/1066157.1066235]
• 43: 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
• 44: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
dynamic time warping, embeddings, filter-and-refine retrieval, similarity indexing, subsequence matching, time series