이원성 기반 시계열 서브시퀀스 매칭의 인덱스 검색을 위한 최적의 기법
An Optimal Way to Index Searching of Duality-Based Time-Series Subsequence Matching
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 시계열 데이터베이스에서 서브시퀀스 매칭을 효과적으로 처리하는 방안에 관하여 논의한다. 먼저, 본 논문에서는 서브시퀀스 매칭을 위한 기존 기법의 인덱스 검색에서 발생하는 성능상의 문제점들을 지적하고, 이들을 해결할 수 있는 새로운 방법을 제시한다. 제안된 기법은 서브시퀀스 매칭의 인덱스 검색 문제를 윈도우-조인이라는 일종의 공간 조인 문제로 새롭게 해석하는 것에서 출발한다. 윈도우-조인의 빠른 처리를 위하여 제안된 기법에서는 서브시퀀스 매칭을 시작할 때 질의 시퀀스를 위한 R*-트리를 주기억장치 내에 구성한다. 또한, 제안된 기법은 데이터 시퀀스들을 위한 디스크 상의 R*-트리와 질의 시퀀스를 위한 주기억장치 상의 R*-트리를 효과적으로 조인할 수 있는 새로운 알고리즘을 포함한다. 이 알고리즘은 데이터 시퀀스들을 위한 R*-트리 페이지들을 인덱스 단계의 착오 채택 없이 단 한번만 디스크로부터 액세스하므로 디스크 액세스 측면에서 최적의 기법임이 증명된다. 또한, 다양한 실험을 통한 성능 평가를 통하여 제안된 기법의 우수성을 정량적으로 규명한다.
Abstract
In this paper, we address efficient processing of subsequence matching in time-series databases. We first point out the performance problems occurring in the index searching of a prior method for subsequence matching. Then, we propose a new method that resolves these problems. Our method starts with viewing the index searching of subsequence matching from a new angle, thereby regarding it as a kind of a spatial-join called a window-join. For speeding up the window-join, our method builds an R*-tree in main memory for a query sequence at starting of subsequence matching. Our method also includes a novel algorithm for joining effectively one R*-tree in disk, which is for data sequences, and another R*-tree in main memory, which is for a query sequence. This algorithm accesses each R*-tree page built on data sequences exactly once without incurring any index-level false alarms. Therefore, in terms of the number of disk accesses, the proposed algorithm proves to be optimal. Also, performance evaluation through extensive experiments shows the superiority of our method quantitatively.
참고문헌 (13)
- R. Agrawal,C. Faloutsos, "Efficient Similarity Search in Sequence Databases", pp.69-84 (1993)
- N. Beckmann et al, "The R*-tree：An Efficient and Robust Access Method for Points and Rectangles", acm sigmod(322331), pp.1990~
- T. Brinkhoff, "Efficient Processing of Spatial Joins Using R-Trees", acm sigmod, pp.237~246 (1993)
- P. P. Chan, "Efficient Time-Series Matching By Wavelets", pp.126~133 (1999)
- C. Faloutsos,, "Fast Subsequence Matching in Time-series Databases", pp.419-429 (1994)
- Y.-W. Huang, "Spatial Joins Using R-trees：Breadth-First Traversal with Global Optimizations", pp.396~405 (1997)
- S. W. Kim, "An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases", pp.607~614 (2001)
- E. J. Keogh et al, "Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases", 419(429) (2001)
- W. K. Loh, "Index Interpolation ：An Approach for Subsequence Matching Supporting Normalization Transform in Time-Series Databases", pp.480~487 (2000)
- Y. S. Moon, "Duality-Based Subsequence Matching in Time-Series Databases", pp.263~272 (2001)
- D. Rafiei, "Similarity-Based Queries for Time-Series Data", pp.13~24 (1997)
- J. W. Song, "Spatial Join Processing Using Corner Transformation", 11(4), pp.688~695 (1999)
- B. K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms", pp.385~394 (2000)