Indexing multi-dimensional time-series with support for multiple distance measures

ABSTRACT

Although most time-series data mining research has concentrated on providing solutions for a single distance function, in this work we motivate the need for a single index structure that can support multiple distance measures. Our specific area of interest is the efficient retrieval and analysis of trajectory similarities. Trajectory datasets are very common in environmental applications, mobility experiments, video surveillance and are especially important for the discovery of certain biological patterns. Our primary similarity measure is based on the Longest Common Subsequence (LCSS) model, that offers enhanced robustness, particularly for noisy data, which are encountered very often in real world applications. However, our index is able to accommodate other distance measures as well, including the ubiquitous Euclidean distance, and the increasingly popular Dynamic Time Warping (DTW). While other researchers have advocated one or other of these similarity measures, a major contribution of our work is the ability to support all these measures without the need to restructure the index. Our framework guarantees no false dismissals and can also be tailored to provide much faster response time at the expense of slightly reduced precision/recall. The experimental results demonstrate that our index can help speed-up the computation of expensive similarity measures such as the LCSS and the DTW.

REFERENCES

• 1: J. Aach and G. Church. Aligning gene expression time series with time warping algorithms. In Bioinformatics, Volume 17, pages 495--508, 2001.
• 2: Okan Arikan , D. A. Forsyth, Interactive motion generation from examples, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 3: Ziv Bar-Joseph , Georg Gerber , David K. Gifford , Tommi S. Jaakkola , Itamar Simon, A new approach to analyzing gene expression time series data, Proceedings of the sixth annual international conference on Computational biology, p.39-48, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565202]
• 4: D. Berndt and J. Clifford. Using Dynamic Time Warping to Find Patterns in Time Series. In Proc. of KDD Workshop, 1994.
• 5: M. Betke, J. Gips, and P. Fleming. The camera mouse: Visual tracking of body features to provide computer access for people with severe disabilities. In IEEE Transactions on Neural Systems and Rehabilitation Engineering, Vol. 10, No. 1, 2002.
• 6: 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
• 7: D. Gavrila and L. Davis. Towards 3-d model-based tracking and recognition of human movement: a multi-view approach. In Int. Workshop on Face and Gesture Recognition.
• 8: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient Indexing of Spatiotemporal Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.251-268, March 25-27, 2002
• 9: Tamer Kahveci , Ambuj K. Singh , Aliekber Gürel, Similarity Searching for Multi-Attribute Sequences, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.175, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029718]
• 10: E. Keogh. Exact indexing of dynamic time warping. In Proc. of VLDB, 2002.
• 11: 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 [doi>10.1145/775047.775062]
• 12: 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
• 13: Zsolt Miklós Kovács-Vajna, A Fingerprint Verification System Based on Triangular Matching and Dynamic Time Warping, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.11, p.1266-1276, November 2000 [doi>10.1109/34.888711]
• 14: Similarity Search for Multidimensional Data Sequences, Proceedings of the 16th International Conference on Data Engineering, p.599, February 28-March 03, 2000
• 15: Chihcheng Hsu, Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases, Proceedings of the 16th International Conference on Data Engineering, p.23, February 28-March 03, 2000
• 16: T. Rath and R. Manmatha. Word image matching using dynamic time warping. In Tec Report MM-38. Center for Intelligent Information Retrieval, University of Massachusetts Amherst, 2002.
• 17: Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, September 2000
• 18: Mitsuomi Shimada , Kuniaki Uehara, Discovering of Correlation from Multi-stream of Human Motion, Proceedings of the Third International Conference on Discovery Science, p.290-294, December 04-06, 2000
• 19: R. E. Valdes-Perez and C. A. Stone. Systematic detection of subtle spatio-temporal patterns in time-lapse imaging ii. particle migrations. In Bioimaging 6(2), pages 71--78, 1998.
• 20: M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In Proc. of ICDE, 2002.
• 21: 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
• 22: Y. Zhu and D. Shasha. Query by humming: a time series database approach. In Proc. of SIGMOD, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
dynamic time warping, longest common subsequence, trajectories