시계열 데이터를 대상으로 한 유사 검색에서 동적 타임 워핑(dynamic time warping: DTW) 거리를 효율적으로 계산하기 위해 많은 연구가 수행되었다. DTW 거리는 유사 검색에서 높은 정확도를 제공하지만, 계산이 복잡하여 대용량 데이터베이스에 적용하기 힘든 문제점이 있다. 이러한 DTW 거리의 효율적 계산 방법으로 FastDTW와 FTW가 제안되었고, 최근 이 두 방법의 장점을 취한 HybridFTW가 제안되었다. HybridFTW는 FastDTW의 허용 범위 제한을 통한 빠른 계산의 장점과 FTW의 미리 버림의 장점을 조합한 하이브리드 접근법이다. 본 논문에서는 우선 FTW와 FastDTW의 장점을 각각 분석하고, 이들의 장점을 취한 HybridFTW의 개념을 설명한다. 그런 다음, HybridFTW를 k-NN 검색에 사용하기 위한 주요 절차를 다섯 단계로 나누어 설명한다. 그리고, 이들 다섯 단계를 사용하여 HybridFTW 기반의 k-NN 알고리즘을 새롭게 제안하고, 그 정확성을 정리로서 제시하고 증명한다. 마지막으로, 실제 실험을 통해 제안한 알고리즘이 기존의 FastDTW와 FTW를 기반한 알고리즘보다 최대 20배까지 성능을 향상시킴을 보인다.
There have been many research efforts on computing the DTW(dynamic time warping) distance efficiently in similarity search on time-series databases. The DTW distance is known to offer the high accuracy in similarity search, but it has a critical problem in supporting the large database due to its high computation complexity. For the fast computation of the DTW distance, FastDTW and FTW have been proposed recently, and HybridFTW has also been proposed to adopt both of their advantages. HybridFTW is a hybrid approach that combines the advantage of FastDTW, which provides the fast computation through the limitation of allowable ranges, and the advantage of FTW, which exploits the early abandon effect. In this paper, we first analyze the computation procedure of FastDTW and FTW in detail and present the concept of HybridFTW by taking both of their advantages. After then, we propose a HybridFTW-based k-NN algorithm. For this, we first explain five major steps to implement the HybridFTW-based k-NN search in detail. We next propose a formal k-NN algorithm exploiting HybridFTW and prove its correctness through a formal theorem. Experimental results for real and synthetic data sets show that the proposed k-NN algorithm improves the search performance by up to 20 times over k-NN algorithms based on FastDTW and FTW.
