인덱스 보간법에 기반한 효율적인 서브시퀀스 매칭 기법 = An Efficient Subsequence Matching Method Based on Index Interpolation

다국어 초록 (Multilingual Abstract)

Subsequence matching is one of the most important operations in the field of data mining. The existing subsequence matching algorithms use only one index, and their performance gets worse as the difference between the length of a query sequence and the site of windows, which are subsequences of a same length extracted from data sequences to construct the index, increases. In this paper, we propose a new subsequence matching method based on index interpolation to overcome such a problem. An index interpolation method constructs two or more indexes, and performs search ing by selecting the most appropriate index among them according to the given query sequence length. In this paper, we first examine the performance trend with the difference between the query sequence length and the window size through preliminary experiments, and formulate a search cost model that reflects the distribution of query sequence lengths in the view point of the physical database design. Next, we propose a new subsequence matching method based on the index interpolation to improve search performance. We also present an algorithm based on the search cost formula mentioned above to construct optimal indexes to get better search performance. Finally, we verify the superiority of the proposed method through a series of experiments using real and synthesized data sets.

국문 초록 (Abstract)

서브시퀀스 매칭은 데이터 마이닝 분야에서 중요한 연산 중의 하나이다. 기존의 서브시퀀스 매칭 알고리즘들은 하나의 인덱스만을 사용하여 검색을 수행하며, 인덱스를 생성하기 위하여 데이터 시퀀스로부터 추출한 윈도우의 크기와 질의 시퀀스의 길이 간의 차이가 커질수록 검색 성능이 급격히 저하된다. 본 논문에서는 이러한 문제점을 해결하기 위하여 인덱스 보간법에 기반한 새로운 서브시퀀스 매칭 기법을 제안한다. 인덱스 보간법이란 하나 이상의 인덱스를 구축하고 주어진 질의 시퀀스의 길이에 따라 적절한 인덱스를 선택하여 검색을 수행하는 기법이다. 본 논문에서는 먼저 사전 실험을 통하여 서브시퀀스 매칭을 수행하는 데에 있어 질의 시퀀스 길이와 윈도우 크기 간의 차이로 인한 성능의 변화를 관찰하고, 이 관찰을 통하여 물리적 데이터베이스 설계 관점에서 질의 시퀀스의 길이 분포에 따른 검색 비용 공식을 산출한다. 다음에, 윈도우 크기 효과에 의한 성능 저하를 개선하기 위해 인덱스 보간법에 기반한 새로운 검색 기법을 제안한다. 또한, 검색 비용 공식에 기반하여 제안된 검색 기법의 성능을 최적화할 수 있도록 다수의 인덱스를 구성하는 알고리즘을 제시한다. 마지막으로, 실제 데이터와 합성 데이터를 이용한 여러 가지 실험을 통하여 제안된 기법의 우수성을 검증한다.

참고문헌 (Reference)

• 1 C. Chatfield, "The Analysis of Time-Series An Introduction" Chapman and Hall 1984.
• 2 D. Rafiei, "Similarity-based Queries for Time-Series Data" acm sigmod (acm sigmod): 1997-, 06
• 3 D. Rafiei, "On Similarity-Based Queries for Time Series Data" ieee icde (ieee icde): 1999-, mar.
• 4 D. Q. Goldin, "On Similarity Queries for Time-Series Data In" 137-153, 1995.
• 5 K. K. W. Chu, "Fast Time-Series Searching with Scaling and Shifting" acm pods (acm pods): 1999-, 05
• 6 C. Faloutsos et al, "Fast Subsequence Matching in Time-series Databases" acm sigmod (acm sigmod): 1994-, 05
• 7 R. Agrawal et al, "Fast Similarity Search in the Presence of Noise and Translation in Time-Series Database" 490-501, 1995.
• 8 K. P. Chan, "Efficient Time Series Matching by Wavelets" ieee icde (ieee icde): 1999-, mar.
• 9 R. Agrawal et al, "Efficient Similarity Search in Sequence DataBases" fodo (fodo): 1993-, oct.
• 10 Y. S. Moon et al, "Duality-Based Subsequence Matching in Time-Series Databases" ieee icde (ieee icde): 2001-, apr.
• 11 N. Beckmann et al, "An efficient and Robust Access Method for Points and Rectangles" 322-331, 1990.
• 12 M. S. Chen et al, "An Overview from Database Perspective" 8 (8): 866-883, 1996.
• 13 W. K. Loh et al, "A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases" 9 (9): 5-28 2004,
• 14 W. K. Loh et al, "A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases" e84-d (e84-d): 76-86, 2001.
• 15 R. Weber et al, "A Quantitative Analysis and Performance Study for Similarity Search Methods on High-Dimensional Spaces" pp.194-2051998.