Optimization of subsequence matching under time warping in time-series databases

ABSTRACT

This paper discusses effective processing of subsequence matching under time warping in time-series databases. Time warping is a transformation that enables finding of sequences with similar patterns even when they are of different lengths. Through a preliminary experiment, we first point out that Naive-Scan, a basic method for processing of subsequence matching under time warping, has its performance bottleneck in the CPU processing step. For optimizing this step, in this paper, we propose a novel method that eliminates all possible redundant calculations. It is verified that this method is not only an optimal one for processing Naive-Scan, but also does not incur any false dismissals. Our experimental results showed that the proposed method can make great improvement in performance of subsequence matching under time warping. Especially, Naive-Scan, which has been known to show the worst performance, performs much better than LB-Scan as well as ST-Filter in all the cases by employing the proposed method for CPU processing. This result is interesting and valuable in that the performance inversion among Naive-Scan, LB-Scan, and ST-Filter has occurred by optimizing the CPU processing step, which is their common performance bottleneck.

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: 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
• 3: 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
• 4: 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 [doi>10.1145/303976.304000]
• 5: 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
• 6: 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
• 7: 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]
• 8: 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 [doi>10.1145/354756.354856]
• 9: Loh, W. K., Kim, S. W., and Whang, K. Y. Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases, IEICE Trans. on Information and Systems, E84-D, 1, (Mar. 2001), 76--86.
• 10: 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
• 11: 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 [doi>10.1145/502585.502629]
• 12: Park, S. H. private communication, 2003.
• 13: On Similarity-Based Queries for Time Series Data, Proceedings of the 15th International Conference on Data Engineering, p.410, March 23-26, 1999
• 14: 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
• 15: Kim, M. S., Kim, S. W., and Shin, M. Y. Subsequence Matching Under Time-Warping in Time-Series Databases: Observation, Optimization, and Performance Results, Unpublished Manuscript, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
subsequence matching, time warping, time-series databases