HybridFTW: 범위 질의에서 동적 타임 워핑 거리의 하이브리드 계산 (HybridFTW: A Hybrid Approach to Computing of Dynamic Time Warping Distances in Range Queries)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 40권 / 4호 / 251 ~ 262페이지
· 저자명 : 이민우, 김상필, 문양세, 김진호, 이상민

초록

본 논문에서는 시계열 대상의 유사 검색에서 동적 타임 워핑(DTW) 거리를 계산하는 효율적인 방법을 제안한다. DTW 거리는 유사 검색에서 높은 정확도를 제공하지만, 계산이 복잡하여 대용량 데이터베이스 적용이 힘든 문제점이 있다. 최근 이러한 DTW 거리의 효율적 계산 방법으로 FastDTW와 FTW가 제안되었다. 그러나, FastDTW는 계산 도중 거리 값이 허용치보다 큰 경우에도 계속 거리 계산이 이루어지는 단점이 있고, FTW는 허용치가 상대적으로 크게 주어지는 경우에 유사하지 않은 많은 데이터 시퀀스를 빨리 전지(pruning)하지 못하는 단점이 있다. 본 논문에서는 이 두 방법의 장점을 취하여 DTW 거리 계산 성능을 향상시키는 하이브리드 계산법인 HybridFTW을 제안한다. HybridFTW는 FastDTW의 허용 범위 제한을 통한 빠른 계산의 장점과 FTW의 미리 버림의 장점을 조합함으로써 DTW 거리 계산의 성능을 크게 향상시킨다. 이를 위해, 본 논문에서는 우선 기존 FTW와 FastDTW의 동작 절차를 자세히 분석하고, 이들 방법의 장점을 도출한다. 그리고, 이들 장점을 취한 HybridFTW의 개념을 제시하고, HybridFTW를 이루는 세 가지 단계와 각 단계의 동작 절차를 정형적으로 설명한다. 또한, HybridFTW를 사용한 범위 검색(range search) 알고리즘을 제시하고, 이 알고리즘의 정확성을 정리로 증명한다. 실제 실험 결과, HybridFTW는 FastDTW에 비해 최대 4.5배, FTW에 비해 최대 2.0배까지 성능을 향상시킨 것으로 나타났다.

영어초록

In this paper, we propose an efficient approach that computes the dynamic time warping (DTW) distance in time-series similarity search. The DTW distance is known to offer the high accuracy in similarity search, but it has a difficult problem in supporting the large database due to its high computation complexity. Recently, FastDTW and FTW have been proposed for the efficient computation of the DTW distance. These two methods, however, have the following disadvantages: FastDTW continues the complex computation until the final DTW distance is obtained even if the intermediate distance exceeds the given tolerance; FTW may not prune many dissimilar data sequences at an early stage if the given tolerance is relatively large. In this paper, we propose a hybrid approach, called HybridFTW, which adopts advantages of both methods. HybridFTW improves the performance significantly by combining 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. For this, we first analyze the computation procedure of FastDTW and FTW in detail and derive their advantages clearly. We then present the concept of HybridFTW by taking their both advantages, describe three steps of HybridFTW, and formally explain the detailed computing procedure of each step. We also propose a range search algorithm that exploits HybridFTW and prove its correctness through a formal theorem. Experimental results on real and simulation data sets show that the proposed HybridFTW improves the search performance by up to 4.5 times over FastDTW and by up to 2.0 times over FTW.

참고자료

· 없음