본 논문에서는 동적 타임 워핑(DTW) 거리를 사용하는 범위 서브시퀀스 질의 처리 방법을 제안한다. 본 논문에서는 제안하는 방법은 데이타 시퀀스를 디스조인트 윈도우로 분할하고, 질의 시퀀스를 슬라이딩 윈도우로 분할하는 방법을 사용하는 DualMatch의 범위 서브시퀀스 질의 처리 방법을 이용한다. DualMatch는 유클리디언 거리 하에서 동작하는 것으로 알려져 있다. 그러나, 유클리디언 거리는 견고하지 못한 유사 모델이기 때문에 DualMatch는 반드시 DTW 거리를 지원해야 한다. 본 논문에서는 제안하는 방법의 정확성을 입증하기 위해서 중요한 정리를 유도하고, 이에 근거한 알고리즘을 제안한다. 광범위한 실험을 통해 본 논문에서 제안하는 방법이 순차 스캔 알고리즘 보다 효율적으로 동작함을 보였다.
In this paper, we propose a range subsequence matching under dynamic time warping (DTW) distance. We exploit Dual Match, which divides data sequences into disjoint windows and the query sequence into sliding windows. However, Dual Match is known to work under Euclidean distance. We argue that Euclidean distance is a fragile distance, and thus, DTW should be supported by Dual Match. For this purpose, we derive a new important theorem showing the correctness of our approach and provide a detailed algorithm using the theorem. Extensive experimental results show that our range subsequence matching performs much better than the sequential scan algorithm.
