Extensions and relationships of some existing lower-bound functions for dynamic time warping

摘要

Dynamic time warping (DTW) is a state-of-the-art time series similarity measure method, which warps time axes to match the same shape between two time series with different lengths. However, its quadratic time and space complexity is an obstacle to its applications in the large time series data mining. To address this problem, some lower-bound functions for DTW, fast methods to approximately measure the distance between time series, are used to prune the dissimilar objects from time series database so as to retain the candidates for further measuring their similarity with DTW. So far, the existing lower-bound functions for DTW have been widely accepted for time series similarity search and indexing. In this paper, we propose the extensions of two existing lower-bound functions and discuss the relationships among them. The extensions are improved with high tightness and without much time cost. At the same time, we theoretically prove that these extensions satisfy lower-bound requirement and are better than their old versions respectively. The experimental results demonstrate that in most cases the quality of the proposed extensions of lower-bound functions for DTW outperforms the original versions except for a slightly higher time cost.