Accurate and Fast Dynamic Time Warping

摘要

Dynamic time warping (DTW) is widely used to measure similarity between two time series by finding an optimal warping path. However, its quadratic time and space complexity are not suitable for large time series datasets. To overcome the issues, we propose a modified version of dynamic time warping, which not only retains the accuracy of DTW but also finds the optimal warping path faster. In the proposed method, a threshold value used to narrow the warping path scope can be preset automatically, thereby resulting in a new method without any parameters. The optimal warping path is found by a backward strategy with reduced scope which is opposite to the forward strategy of DTW. The experimental results demonstrate that besides the same accuracy, the proposed dynamic time warping is faster than DTW, which shows that our method is an improved version of the original one.