Byoung Chol Chang , Sang Wook Kim , Jae Hyuk Cha

The KIPS Transactions:PartD, Vol. 13, No. 3, pp. 357-368, Jun. 2006
10.3745/KIPSTD.2006.13.3.357,   PDF Download:

Abstract

This paper discusses the way of processing time-series subsequence matching under time warping. Time warping enables finding sequences with similar patterns even when they are of different lengths. The prefix-querying method is the first index-based approach that performs time-series subsequence matching under time warping without false dismissals. This method employs the L∞ as a base distance function for allowing users to issue queries conveniently. In this paper, we extend the prefix-querying method for absorbing L1, which is the most-widely used as a base distance function in time-series subsequence matching under time warping, instead of L∞. We also formally prove that the proposed method does not incur any false dismissals in the subsequence matching. To show the superiority of our method, we conduct performance evaluation via a variety of experiments. The results reveal that our method achieves significant performance improvement in orders of magnitude compared with previous methods.

Statistics
Cite this article