TY  - JOUR
T1  - Improving the Upper Bound of the Dynamic Time Warping for Sparse and Long Time Sequences
AU  - Seo, Janghyuk 
AU  - Jung, Woohwan 
AU  - Shim, Kyuseok 
JO  - Journal of KIISE, JOK
PY  - 2019
DA  - 2019/1/14
DO  - 10.5626/JOK.2019.46.6.570
KW  - Dynamic Time Warping
KW  - time series
KW  - dynamic programming
KW  - data mining
AB  - 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.