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

시계열 데이터 분석에서 널리 이용되는 거리 측도 중 하나인 동적 시간 워핑(Dynamic Time Warping, DTW)은 시계열 데이터의 길이가 길어질수록 시간이 오래 걸리는 단점이 존재한다. 이를 극복하기 위해 최근에 런-길이 부호화라는 압축 방법을 이용하여 DTW를 빠른 시간 내에 근사하는 알고리즘들이 개발되었다. 하지만 기존의 방법들로 계산된 DTW의 상계값에는 불필요하게 더해지는 거리값이 존재한다. 본 논문은 시간복잡도를 유지하면서 런-길이 부호화를 통한 DTW 근사 알고리즘들을 개선하는 동적계획법(Dynamic programming) 기반의 알고리즘을 제시한다. 또한, 현실 세계의 데이터 및 인공 데이터를 활용한 실험을 통해 제안하는 방법의 효용성을 보인다.