타임 워핑을 지원하는 효율적인 서브시퀀스 매칭 기법

• 영문명: A Subsequence Matching Technique that Supports Time Warping Efficiently
• 발행기관: 강원대학교 산업기술연구소
• 저자명: 박상현(Park Sang Hyun) 김상욱(Kim Sang Wook) 조준서(Cho June Suh) 이헌길(Lee Hoen Gil)
• 간행물 정보: 『산업기술연구』vol.21, 169~181쪽, 전체 13쪽
• 주제분류: 공학 > 공학일반
• 파일형태: PDF
• 발행일자: 2001.09.30

영문 초록

This paper discusses an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In earlier work, we suggested an efficient method for whole matching under time warping. This method constructs a multidimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality. In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multi-dimensional index using a feature vector as indexing attributes. For query precessing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verily the superiority of our method, we perform extensive experiments. The results reseal that our method achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.

목차

Abstract

1. 서론

2. 용어 정의

3. 관련 연구

4. 제안하는 기법

5. 성능 분석

6. 결론

참고문헌

키워드

시퀀스 데이터베이스 타임워핑 지원 서브시퀀스 검색 sequence database subsequence matching with time warping