Man Soon Kim , Sang Wook Kim

The KIPS Transactions:PartD, Vol. 11, No. 7, pp. 1385-1398, Dec. 2004
10.3745/KIPSTD.2004.11.7.1385,   PDF Download:

Abstract

This paper discusses an 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 the performance bottleneck of Naive-Scan, a basic method for processing of subsequence matching under time warping, is on the CPU processing step. Then, we propose a novel method that optimizes the CPU processing step of Naive-Scan. The proposed method maximizes the CPU performance by eliminating all the redundant calculations occurring in computing the time warping distance between the query sequence and data subsequences. We formally prove the proposed method does not incur false dismissals and also is the optimal one for processing Naive-Scan. Also, we discuss the ways to apply the proposed method to the post-processing step of LB-Scan and ST-Filter, the previous methods for processing of subsequence matching under time warping. Then, we quantitatively verify the performance improvement errects obtained by the proposed method via extensive experiments. The result shows that the performance of all the three previous methods improves by employing the proposed method. Especially, Naive-Scan, which is known to show the worst performance, performs much better than LB-Scan as well as ST-Filter in all cases when it employs the proposed method for CPU processing. This result is so meaningful in that the performance inversion among Naive-Scan, LB-Scan, and ST-Filter has occurred by optimizing the CPU processing step, which is their performance bottleneck.

Statistics
Cite this article