Fast Constrained Dynamic Time Warping for Similarity Measure of Time Series Data

Abstract

In this paper, we propose an efficient algorithm for reducing the computational complexity of dynamic time warping (DTW) for obtaining similarity measures between time series. The DTW technique exhibits superior classification accuracy compared to other algorithms but has a limitation of high computational complexity. To reduce the computational complexity of standard DTW, constrained DTW and fast DTW techniques have been proposed. The constrained DTW technique reduces the computational complexity of standard DTW by only considering limited alignments and prevent excessive alignments between two time series, which can reduce the overall classification accuracy. However, since the searching window for limited alignments is fixed, the computational complexity is still high when the length of time series is long. In contrast, fast DTW has a lower classification accuracy than the constrained DTW technique. However, fast DTW estimates the optimal alignment while considering only the alignments within an adaptive window; as two time series increase in length, the fast DTW technique more strongly reduces the computational complexity. Therefore, we propose a fast constrained DTW approach that applies the optimal alignment estimation of fast DTW within the limited alignments of constrained DTW. As the proposed fast constrained DTW operates within a fixed window area of the constrained DTW, which prevents excessive alignments, it has a classification accuracy similar to that of the constrained DTW. Also, in the fast constrained DTW, when the length of the time series is long, a low computational complexity is maintained by the influence of the adaptive window of the fast DTW. Experimental results on 19 UCR time series datasets show that the proposed fast constrained DTW method achieves computational complexity reductions of approximately 52.2% and 22.3% compared to the existing fast DTW and constrained DTW, while maintaining almost the same classification accuracy as the constrained DTW.

Keywords

• Computational complexity
• dynamic time warping
• similarity measure
• time series data