Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Time series data is usually stored and processed in the form of discrete trajectories of multidimensional measurement points. In order to compare the measurements of a query trajectory to a set of stored trajectories, one needs to calculate similarity between two trajectories. In this paper an efficient algorithm for calculating the similarity is presented for a set of trajectories containing one increasing measurement dimension, for example time series data. An even more efficient version of the algorithm suitable for situations where all dimensions are increasing, such as many spatio-temporal data sets, is also presented. Furthermore, the similarity measurement technique nearly fulfills the requirements of a metric space, which is a clear improvement to the currently used procedure. The performance of the algorithm is validated first by using data measured from a hot strip mill and then by using synthetically generated trajectories. The new algorithm outperforms the currently used procedure by several orders of magnitude, depending on the context of usage.

REFERENCES

• 1: 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
• 2: 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 [doi>10.1016/j.ic.2004.07.001]
• 3: 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 [doi>10.1016/S0306-4379(03)00037-1]
• 4: [4] P. Laurinen and J. Roning. An adaptive neural network model for predicting the post roughing mill temperature of steel slabs in the reheating furnace. Journal of Materials Processing Technology, 168(3):423-430, October 2005.
• 5: 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 [doi>10.1016/S0164-1212(03)00078-5]
• 6: 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 [doi>10.1145/585147.585158]
• 7: 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 [doi>10.1109/69.877502]
• 8: 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]
• 9: Yutaka Yanagisawa , Jun-ichi Akahani , Tetsuji Satoh, Shape-Based Similarity Query for Trajectory of Mobile Objects, Proceedings of the 4th International Conference on Mobile Data Management, p.63-77, January 21-24, 2003
• 10: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design, Measurement

Keywords:
algorithm, data mining, database, trajectory similarity