HybridFTW를 사용한 효율적인 k-NN 검색 = Efficient k-NN Search Using HybridFTW

국문 초록 (Abstract)

시계열 데이터를 대상으로 한 유사 검색에서 동적 타임 워핑(dynamic time warping: DTW) 거리를 효율적으로 계산하기 위해 많은 연구가 수행되었다. DTW 거리는 유사 검색에서 높은 정확도를 제공하지만, 계산이 복잡하여 대용량 데이터베이스에 적용하기 힘든 문제점이 있다. 이러한 DTW 거리의 효율적 계산 방법으로 FastDTW와 FTW가 제안되었고, 최근 이 두 방법의 장점을 취한 HybridFTW가 제안되었다. HybridFTW는 FastDTW의 허용 범위 제한을 통한 빠른 계산의 장점과 FTW의 미리 버림의 장점을 조합한 하이브리드 접근법이다. 본 논문에서는 우선 FTW와 FastDTW의 장점을 각각 분석하고, 이들의 장점을 취한 HybridFTW의 개념을 설명한다. 그런 다음, HybridFTW를 k-NN 검색에 사용하기 위한 주요 절차를 다섯 단계로 나누어 설명한다. 그리고, 이들 다섯 단계를 사용하여 HybridFTW 기반의 k-NN알고리즘을 새롭게 제안하고, 그 정확성을 정리로서 제시하고 증명한다. 마지막으로, 실제 실험을 통해 제안한 알고리즘이 기존의 FastDTW와 FTW를 기반한 알고리즘보다 최대 20배까지 성능을 향상시킴을 보인다.

다국어 초록 (Multilingual Abstract)

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.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. HybridFTW의 개념
• 4. HybridFTW 기반 k-NN 검색 알고리즘
• 5. 성능평가
• 6. 결론
• References

참고문헌 (Reference)

1 D. J. Berndt, "Using Dynamic Time Warping to Find Patterns in Time Series" 359-370, 1994

2 S. Salvador, "Toward Accurate Dynamic Time Warping in Linear Time and Space" 11 (11): 561-580, 2007

3 N. Beckmann, "The R*-tree: an efficient and robust access method for points and rectangles" 322-331, 1990

4 E. Keogh, "Supporting Exact Indexing of Arbitrarily Rotated Shapes and Periodic Time Series under Euclidean and Warping Distance Measures" 18 (18): 611-630, 2009

5 E. Keogh, "Scaling up Dynamic Time Warping for Datamining Applications" 285-289, 2000

6 W.-S. Han, "Ranked Subsequence Matching in Time-Series Databases" 406-417, 2007

7 Y.-S. Moon, "Publishing Time-Series Data under Preservation of Privacy and Distance Orders" 17-31, 2010

8 J.-G. Lee, "Maximizing the Early Abandon Effect in Time- Series Distance Computation" 573-583, 2011

9 Y. Cai, "Indexing Spatio-temporal Trajectories with Chebyshev Polynomials" 599-610, 2004

10 이민우, "HybridFTW: 범위 질의에서 동적 타임 워핑 거리의 하이브리드 계산" 한국정보과학회 40 (40): 251-262, 2013

11 B.-K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms" 385-394, 2000

12 C. Faloutsos, "Fast Subsequence Matching in Time-Series Databases" 419-429, 1994

13 A. Mueen, "Fast Approximate Correlation for Massive Time-Series Data" 171-182, 2010

14 Y. Sakurai, "FTW: Fast Similarity Search under the Time Warping Distance" 326-337, 2005

15 E. Keogh, "Exact Indexing of Dynamic Time Warping" 406-417, 2002

16 L. Junkui, "Early Abandon to Accelerate Exact Dynamic Time Warping" 6 (6): 144-152, 2009

17 H. Sakoe, "Dynamic Programming Algorithm Optimization for Spoken Word Recognition" 26 (26): 43-49, 1978

18 E. Keogh, "Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases" 3 (3): 263-286, 2001

19 W.-S. Han, "A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union" 457-468, 2011