Improving the Upper Bound of the Dynamic Time Warping for Sparse and Long Time Sequences

Janghyuk Seo, Woohwan Jung, Kyuseok Shim

http://doi.org/10.5626/JOK.2019.46.6.570

Dynamic Time Warping (DTW), a distance measure widely used in time series analysis, is associated with the shortcoming of long execution time with long time sequences. To alleviate the problem, several algorithms which use a compression technique called run-length encoding and compute approximate DTW distances were recently proposed. However, the computation of the upper bounds by such algorithms consists of adding unnecessary distance values. In this paper, we propose an approximation algorithm which improves the state of the art for computing approximate DTW distances while keeping the time complexity unchanged. Experimental results with both synthetic and real-life data confirm the effectiveness of our proposed algorithm.