가상 윈도우 서브시퀀스 매칭 방법의 확장 알고리즘 (An Extended Subsequence Matching Method based on a Virtual Window)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 30권 / 1호 / 37 ~ 47페이지
· 저자명 : 임선영, 박영호

초록

시계열 데이터는 시간의 흐름에 따라 변하는 데이터의 값을 저장한 정보로, 최근 시계열 데이터에 대한 검색관심이 높아지고 있다. 시계열 데이터에서 원하는 구간을 검색하는 서브시퀀스 매칭 방법은 다양한 분야에 적용된다. 본 논문에서는 서브시퀀스 매칭을 효율적으로 하기 위하여 가상 윈도우를 생성하여 후보시퀀스의 개수를 줄여빠르게 검색하는 방법인 VWIM을 제안한다. VWIM은 후보시퀀스의 개수를 줄이기 위하여 기존의 방법들에서비교하지 못했던 부분을 가상 윈도우로 구축하여 비교하였다. 가상 윈도우를 통해 후보시퀀스의 개수를 줄여 데이터 시퀀스와 질의 시퀀스간의 거리 계산 비용을 줄임으로써 성능을 개선시켰다. 실험을 통해 기존의 방법들과 비교하여 VWIM의 후보시퀀스의 개수는 평균적으로 5배, 질의 처리 시간은 평균적으로 8배 향상됨을 보였다.

영어초록

A time series is a collection of real numbers which are sampled in a time interval. Thesubsequence matching is used in many applications in order to retrieve the data subsequenceswhich are similar to the query sequence. In this paper, we propose an efficient subsequencematching method, which is called Virtual Window-based Instance-level Match (VWIM), to reducethe number of candidate subsequences. VWIM constructs the virtual windows by combining theremaining part of data sequences, and compares the virtual windows of data subsequence with thequery subsequences. Experiment results show that VWIM reduces the number of candidatesubsequences and thus query processing time compared with the existing methods.

참고자료

· 없음