Exact Indexing of Time Series under Dynamic Time Warping
This work addresses a bottleneck in large-scale time series analysis by enabling faster and more accurate similarity searches, though it is incremental as it builds on existing lower bounding techniques.
The authors tackled the problem of efficient similarity search for time series under Dynamic Time Warping (DTW) by proposing a novel lower bounding distance LB_Keogh+ that handles unequal-length sequences with high tightness, resulting in an exact indexing method that achieves good pruning power in experiments on real-world datasets.
Dynamic time warping (DTW) is a robust similarity measure of time series. However, it does not satisfy triangular inequality and has high computational complexity, severely limiting its applications in similarity search on large-scale datasets. Usually, we resort to lower bounding distances to speed up similarity search under DTW. Unfortunately, there is still a lack of an effective lower bounding distance that can measure unequal-length time series and has desirable tightness. In the paper, we propose a novel lower bounding distance LB_Keogh+, which is a seamless combination of sequence extension and LB_Keogh. It can be used for unequal-length sequences and has low computational complexity. Besides, LB_Keogh+ can extend sequences to an arbitrary suitable length, without significantly reducing tightness. Next, based on LB_Keogh+, an exact index of time series under DTW is devised. Then, we introduce several theorems and complete the relevant proofs to guarantee no false dismissals in our similarity search. Finally, extensive experiments are conducted on real-world datasets. Experimental results indicate that our proposed method can perform similarity search of unequal-length sequences with high tightness and good pruning power.