유사 시퀀스 매칭을 위한 하이브리드 저차원 변환 = Hybrid Lower-Dimensional Transformation for Similar Sequence Matching

국문 초록 (Abstract)

유사 시퀀스 매칭에서는 고차원인 시퀀스를 저차원의 점으로 변환하기 위하여 저차원 변환을 사용한다. 그런데, 이러한 저차원 변환은 시계열 데이터의 종류에 따라 인덱싱 성능에 있어서 큰 차이를 나타낸다. 즉, 어떤 저차원 변환을 선택하느냐가 유사 시퀀스 매칭의 인덱싱 성능에 큰 영향을 주게 된다. 이 문제를 해결하기 위하여, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 먼저, 하나의 시퀀스에 두 개 이상의 저차원 변환을 적용하는 하이브리드 저차원 변환의 개념을 제안하고, 변환된 시퀀스간의 거리를 계산하는 하이브리드 거리를 정의한다. 다음으로, 이러한 하이브리드 접근법 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정형적으로 증명한다. 또한, 제안한 하이브리드 접근법을 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다.

다국어 초록 (Multilingual Abstract)

We generally use lower-dimensional transformations to convert high-dimensional sequences into low-dimensional points in similar sequence matching. These traditional transformations, however, show different characteristics in indexing performance by the type of time-series data. It means that the selection of lower-dimensional transformations makes a significant influence on the indexing performance in similar sequence matching. To solve this problem, in this paper we propose a hybrid approach that integrates multiple transformations and uses them in a single multidimensional index. We first propose a new notion of hybrid lower-dimensional transformation that exploits different lower-dimensional transformations for a sequence. We next define the hybrid distance to compute the distance between the transformed sequences. We then formally prove that the hybrid approach performs the similar sequence matching correctly. We also present the index building and the similar sequence matching algorithms that use the hybrid approach. Experimental results for various time-series data sets show that our hybrid approach outperforms the single transformation-based approach. These results indicate that the hybrid approach can be widely used for various time-series data with different characteristics.

참고문헌 (Reference)

1 Lim, S.-H., "Using Multiple Indexes for Efficient Subsequence Matching in Time-Series Databases" 65-79, 2006

2 Beckmann, N., "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles" 322-331, 1990

3 Berchtold, S., "The Pyramid-Technique: Towards Breaking the Curse of Dimensionality" 142-153, 1998

4 Keogh, J., "Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases" 151-162, 2001

5 Keogh, E. J. et al., "LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures" 882-893, 2006

6 Hsieh, M. J., "Integrating DCT and DWT for Approximating Cube Streams" 179-186, 2005

7 Chan, K.-P., "Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping" 15 (15): 686-705, 2003

8 Moon, Y.-S., "General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows" 382-393, 2002

9 Yi, B.-K., "Fast Time Sequence Indexing for Arbitrary Lp Norms" 385-394, 2000

10 Faloutsos, C., "Fast Subsequence Matching in Time-Series Databases" 419-429, 1994

11 Keogh, E. J., "Ensemble-Index: A New Approach to Indexing Large Databases" 117-125, 2001

12 Agrawal, R., "Efficient Similarity Search in Sequence Databases" 69-84, 1993

13 Moon, Y.-S., "Duality-Based Subsequence Matching in Time-Series Databases" 263-272, 2001

14 Keogh, J., "Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases" 263-286, 2001

15 Gao, L., "Continually Evaluating Similarity-based Pattern Queries on a Streaming Time Series" 370-381, 2002

16 Moon, Y.-S, "An MBR-Safe Transform for High-Dimensional MBRs in Similar Sequence Matching" 79-90, 2007

17 Loh, W.-K., "A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases" 9 (9): 5-28, 2004

18 Moon, Y.-S., "A Single Index Approach for Time-Series Subsequence Matching that Supports Moving Average Transform of Arbitrary Order" 739-749, 2006