Janghyuk Seo  Woohwan Jung  Kyuseok Shim

10.5626/JOK.2019.46.6.570

Dynamic time warping Time Series Dynamic programming Data Mining

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.