Exact Indexing of Time Series under Dynamic Time Warping

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.