This Article Full Text (PDF) All Versions of this Article: 0165551506064401v1 32/5/387    most recent References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Park, S. Articles by Kim, S.-W. Search for Related Content Social Bookmarking                         What's this?

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

Department of Computer Science, Yonsei University, Korea

Sang-Wook Kim

School of Information and Communications, Hanyang University, Korea

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.

Key Words: time-series databases • subsequence matching • time warping

This version was published on October 1, 2006

Journal of Information Science, Vol. 32, No. 5, 387-399 (2006)
DOI: 10.1177/0165551506064401


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?