Prefix-querying with an L 1 distance metric for time-series subsequence matching under time warping

Abstract

This paper discusses the way of processing time-series subsequence matching under time warping. Time warping enables sequences to be found with similar patterns even when they are of different lengths. Theprefix-querying method is the first index-based approach that efficiently performs time-series subsequence matching under time warping without false dismissals. This method employs theL distance metric as a base distance function so as to allow users to issue queries conveniently. In this paper, we extend the prefix-querying method for absorbingL ₁, which is the most widely used as a base distance function in time-series subsequence matching under time warping, instead ofL. We formally prove that the prefix-querying method with theL ₁ distance metric does not incur any false dismissals in the subsequence matching. To show its superiority, we conduct performance evaluation via a variety of experiments. The results reveal that our method achieves significant performance improvement over the previous methods, up to 10.7 times, with a data set containing real-world Korean stock data sequences, and up to 180 times with data sets containing a very large volume of synthetic data sequences.

Keywords

time-series databases subsequence matching time warping

Get full access to this article

View all access options for this article.

References

R. Agrawal , C. Faloutsos , and A. Swami ., Efficient similarity search in sequence databases . In: D.B. Lomet (ed.), Proceedings of the International Conference on Foundations of Data Organization and Algorithms (FODO) Chicago, October 1993 (Springer, London, 1993) 69–84 .

R. Agrawal et al., Fast similarity search in the presence of noise, scaling, and translation in time-series databases . In: U. Dayal et al. (eds), Proceedings of the International Conference on Very Large Data Bases (VLDB), Zurich, September 1995 (Morgan Kaufmann, San Francisco, 1995) 490–501 .

C. Chatfield , The Analysis of Time-Series: an Introduction ( Chapman and Hall, New York , 1984).

C. Faloutsos et al., Fast subsequence matching in time series databases . In: R.T. Snodgrass and M. Winslett (eds), Proceedings of the International Conference on Management of Data, ACM SIGMOD, Minneapolis, Minnesota, May 1994 (ACM Press, New York, 1994) 419–429 .

M.S. Chen et al., Data mining: an overview from database perspective , IEEE Transactions on Knowledge and Data Engineering 8(6) (1996) 866–883 .

D. Rafiei and A. Mendelzon , Similarity-based queries for time-series data . In: Proceedings of the International Conference on Management of Data, ACM SIGMOD, Tucson, Arizona, June 1997 (ACM Press, New York, 1997) 13–24 .

B.K. Yi and C. Faloutsos , Fast time sequence indexing for arbitrary Lp norms . In: A. El Abbadi et al. (eds), Proceedings of the International Conference on Very Large Data Bases, VLDB 2000 (Morgan Kaufmann, San Francisco, 2000) 385–394 .

K.P. Chan and A.W.C. Fu , Efficient time-series matching by wavelets . In: Proceedings of the International Conference on Data Engineering (ICDE), Sydney, March 1999(IEEE, Washington, DC, 1999) 126–133 .

K.K.W. Chu and M.H. Wong , Fast time-series searching with scaling and shifting . In: V. Vianu and C. Papadimitriou (eds), Proceedings of the ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems (PODS), Philadelphia, Pennsylvania, May 1999 (ACM Press, New York, 1999) 237–248 .

10.

D.Q. Goldin and P.C. Kanellakis , On similarity queries for time-series data: constraint specification and implementation . In: U. Montanari and F. Rossi (eds), Proceedings of the International Conference on Principles and Practice of Constraint Programming, Cassis, France, September 1995 (Springer, London, 1997) 137–153 .

11.

D. Rafiei , On similarity-based queries for time-series data . In: Proceedings of the International Conference on Data Engineering (ICDE), Sydney, Australia, March 1999(IEEE, Washington, DC, 1999) 410–417 .

12.

G. Das , D. Gunopulos and H. Mannila , Finding similar time-series . In: H.J. Komorowski and J. Zytkow (eds), Proceedings of the European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD) 1997(Springer, London, 1997) 88–100 .

13.

W.K. Loh , S.W. Kim and K.Y. Whang , Index interpolation: an approach for subsequence matching supporting normalization transform in time-series databases . In: A. Agah et al. (eds), Proceedings of the ACM International Conference on Information and Knowledge Management, ACM CIKM 2000 (ACM Press, New York, 2000) 480–487 .

14.

W.K. Loh , S.W. Kim and K.Y. Whang , Index interpolation: a subsequence matching algorithm supporting moving average transform of arbitrary order in time series databases, IEICE Transactions on Information and Systems, E84-D 1 (January, 2001) 76–86.

15.

D.J. Berndt and J. Clifford , Finding patterns in time series: a dynamic programming approach. In: U.M. Fayyad et al. (eds), Advances in Knowledge Discovery and Data Mining ( AAAI/MIT Press, Menlo Park , 1996) 229–248.

16.

E. Keogh , Exact indexing of dynamic time warping . In: Proceedings of the International Conference on Very Large Data Bases (VLDB) 2002 (Morgan Kaufmann, San Francisco, 2002) 406–417 .

17.

S.W. Kim , S.H. Park and W.W. Chu , An index-based approach for similarity search supporting time warping in large sequence databases . In: Proceedings of the International Conference on Data Engineering, IEEE ICDE 2001 (IEEE, Washington, DC, 2001) 1607–1614 .

18.

S.H. Park et al., Efficient searches for similar subsequences of difference lengths in sequence databases . In: Proceedings of the International Conference on Data Engineering, IEEE ICDE 2000 (IEEE, Washington, DC, 2000) 23–32 .

19.

S.H. Park , S.W. Kim , J.S. Cho and S. Padmanabhan , Prefix-querying: an approach for effective subsequence matching under time warping in sequence databases . In: H. Paques et al. (eds), Proceedings of the ACM International Conference on Information and Knowledge Management,ACM CIKM 2001 (ACM Press, New York, 2001) 255–262 .

20.

B.K. Yi , H.V. Jagadish and C. Faloutsos , Efficient retrieval of similar time sequences under time warping . In: Proceedings of the International Conference on Data Engineering, IEEE ICDE 1998 (IEEE, Washington, DC, 1998) 201–208 .

21.

S.W. Kim , S.H. Park and W.W. Chu , Efficient processing of similarity search under time-warping in sequence databases: an index-based approach , Information Systems 29(5) (2004) 405–420 .

22.

L. Rabiner and H.H. Juang , Fundamentals of Speech Recognition ( Prentice Hall, Englewood Cliffs , 1993).

23.

S.W. Kim , S.W. Kim and M.Y. Shin , Optimization of subsequence matching under time warping in time-series databases. In: ACM Symposium on Applied Computing, April 2005 ( ACM Press, New York , 2005) 581–586.

24.

C. Faloutsos , Private Communication (2001).

25.

G.A. Stephen , String Searching Algorithms ( World Scientific Publishing, Singapore , 1994).