Journal of KIISE:Computing Practices and Letters (한국정보과학회논문지:컴퓨팅의 실제 및 레터)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Range Subsequence Matching under Dynamic Time Warping

DTW 거리를 지원하는 범위 서브시퀀스 매칭

  • 한욱신 (경북대학교 컴퓨터공학과) ;
  • 이진수 (경북대학교 컴퓨터공학과) ;
  • 문양세 (강원대학교 컴퓨터과학과)
  • Published : 2008.08.15
Download PDF
⟨ Previous Next ⟩

Abstract

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.

본 논문에서는 동적 타임 워핑(DTW) 거리를 사용하는 범위 서브시퀀스 질의 처리 방법을 제안한다. 본 논문에서는 제안하는 방법은 데이타 시퀀스를 디스조인트 윈도우로 분할하고, 질의 시퀀스를 슬라이딩 윈도우로 분할하는 방법을 사용하는 DualMatch의 범위 서브시퀀스 질의 처리 방법을 이용한다. DualMatch는 유클리디언 거리 하에서 동작하는 것으로 알려져 있다. 그러나, 유클리디언 거리는 견고하지 못한 유사 모델이기 때문에 DualMatch는 반드시 DTW 거리를 지원해야 한다. 본 논문에서는 제안하는 방법의 정확성을 입증하기 위해서 중요한 정리를 유도하고, 이에 근거한 알고리즘을 제안한다. 광범위한 실험을 통해 본 논문에서 제안하는 방법이 순차 스캔 알고리즘 보다 효율적으로 동작함을 보였다.

Keywords

References

  1. Keogh, E., "A Decade of Progress in Indexing and Mining Large Time Series Databases," In VLDB, Tutorial, 2006
  2. Rafiei, D. et al., "Querying Time Series Data Based on Similarity," IEEE TKDE, Vol.12, No.5, 2000
  3. Berndt, D. and Clifford, J., "Finding Patterns in Time Series: a Dynamic Programming Approach," AAAI/MIT, 1996
  4. Sakoe, H. and Chiba, S., "Dynamic Programming Algorithm Optimization for Spoken Word Recognition," IEEE ASSP, 1978
  5. Zhu, Y. and Shasha, D., "Warping Indexes with Envelope Transforms for Query by Humming," In SIGMOD, 2003
  6. Rabiner, L and Juang, B., Fundamentals of Speech Recognition, Englewood Cliffs, N. J., 1993
  7. Bartolini, I., Ciaccia, P., and Patella, M., "WARP: Accurate Retrieval of Shapes Using Phase of Fourier Descriptors and Time Warping Distance," IEEE PAMI, pp. 142-147, 2005 https://doi.org/10.1109/TPAMI.2005.21
  8. Moon, Y.-S., Whang, K.-Y., and Loh, W.-K., "Duality-Based Subsequence Matching in Time- Series Databases," In ICDE, pp. 263-272, 2001
  9. Lee, J., Han W.-S., and Moon Y.-S., "Range Search under Dynamic Time Warping," In APIS, pp. 67-70, 2007
  10. Itakura, F., "Minimum Prediction Residual Principle Applied to Speech Recognition," IEEE Trans. on ASSP, Vol. ASSP-23, No.1, pp. 67-72, 1975
  11. Keogh, E., "Exact indexing of dynamic time warping," In VLDB, pp 406-417, 2002
  12. Yi, B.-K. and Faloutsos, C., "Fast Time Sequence Indexing for Arbitrary Lp Norms," In VLDB, pp. 385-394, 2000
  13. Agrawal, R., Faloutsos, C., and Swami, A., "Efficient Similarity Search in Sequence Databases," In FODO, 1993
  14. Beckmann, N. et al., "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles," In SIGMOD, pp. 322-331, 1990
  15. Berchtold, S., Bohm, C., and Kriegel, H.-P., "The Pyramid-Technique: Towards Breaking the Curse of Dimensionality," In SIGMOD, pp. 142-153, 1998 https://doi.org/10.1145/276305.276318
  16. Weber, R. et al., "A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces," In VLDB, pp. 194- 205, pp. 194-205, Aug. 1998
  17. Moon, Y.-S., Whang, K.-Y., and Han, W.-S., "General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows," In SIGMOD, 2002
  18. Faloutsos, C. et al., "Fast Subsequence Matching in Time-Series Databases," In SIGMOD, 1994
  19. Han, W.-S. et al., "Ranked subsequence matching in time-series databases," In VLDB, pages 423-434 2007
  20. Sobell, M. O., Practical Guide to Linux Commands, Editors, and Shell Programming, Prentice Hall, 2005