시계열 데이터베이스에서 타임 워핑 하의 서브시퀀스 매칭 : 관찰, 최적화, 성능 결과
Subsequence Matching Under Time Warping in Time-Series Databases : Observation, Optimization, and Performance Results
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 시계열 데이터베이스에서 타임 워핑 하의 서브시퀀스 매칭을 효과적으로 처리하는 방안에 관하여 논의한다. 타임 워핑은 시퀀스의 길이가 서로 다른 경우에도 유사한 패턴을 갖는 시퀀스들을 찾을 수 있도록 해 준다. 먼저, 사전 실험을 통하여 기존의 기본적인 처리 방식인 Naive-Scan의 성능 병목이 CPU 처리 과정에 있음을 지적하고, Naive-Scan의 CPU 처리 과정을 최적화하는 새로운 기법을 제안한다. 제안된 기법은 질의 시퀀스와 서브시퀀스들간의 타임 워핑 거리들을 계산하는 과정에서 발생하는 중복 작업들을 사전에 제거함으로써 CPU 처리 성능을 극대화한다. 제안된 기법이 착오 기각을 발생시키지 않음과 Naive-Scan을 처리하기 위한 최적의 기법임을 이론적으로 증명한다. 또한, 제안된 기법을 기존의 타임 워핑 하의 서브시퀀스 매칭 기법인 LB-Scan과 ST-Filter의 후처리 단계에 적용하는 방안에 관하여 논의한다. 다양한 실험을 통한 성능 평가에 의하여 제안된 최적화 기법이 가져오는 성능 개선 효과를 정량적으로 검증한다. 실험 결과에 의하면, 기존의 타임 워핑 하의 서브시퀀스 매칭을 위한 모든 기법들이 제안된 최적화 기법에 의하여 성능이 개선되는 것으로 나타났다. 특히, Naive-Scan은 최적화 기법의 적용 전에는 가장 떨어지는 성능을 보였으나, 최적화 기법의 적용 후에는 모든 경우에서 ST-Filter나 LB-Scan을 사용한 경우보다 더 좋은 성능을 보였다. 이것은 성능 병목인 CPU 처리 과정을 최적화함으로써 기존 기법들인 Naive-Scan, LB-Scan, ST-Filter 간의 처리 성능 상의 순위 역전 현상이 발생하였음을 보이는 매우 중요한 결과이다.
Abstract
This paper discusses an effective processing of subsequence matching under time warping in time-series databases. Time warping is a transformation that enables finding of sequences with similar patterns even when they are of different lengths. Through a preliminary experiment, we first point out that the performance bottleneck of Naive-Scan, a basic method for processing of subsequence matching under time warping, is on the CPU processing step. Then, we propose a novel method that optimizes the CPU processing step of Naive-Scan. The proposed method maximizes the CPU performance by eliminating all the redundant calculations occurring in computing the time warping distance between the query sequence and data subsequences. We formally prove the proposed method does not incur false dismissals and also is the optimal one for processing Naive-Scan. Also, we discuss the ways to apply the proposed method to the post-processing step of LB-Scan and ST-Filter, the previous methods for processing of subsequence matching under time warping. Then, we quantitatively verify the performance improvement effects obtained by the proposed method via extensive experiments. The result shows that the performance of all the three previous methods improves by employing the proposed method. Especially, Naive-Scan, which is known to show the worst performance, performs much better than LB-Scan as well as ST-Filter in all cases when it employs the proposed method for CPU processing. This result is so meaningful in that the performance inversion among Naive-Scan, LB-Scan, and ST-Filter has occurred by optimizing the CPU processing step, which is their performance bottleneck.
참고문헌 (22)
- R. Agrawal, "Efficient Similarity Search in Sequence Databases", pp.69-84 (1993)
- C. Chatfield, "The Analysis of Time-Series：An Introduction" (1984), Chapman and Hall
- R. Agrawal et al, "Fast Similarity Search in the Presence of NoiseScaling and Translation in Time-Series Databases", pp.490~501 (1995)
- C. Faloutsos, "Fast Subsequence Matching in Time-series Databases", pp.419-429 (1994)
- M. SChen, "Data Mining：An Overview from Database Perspective", 8(6), pp.866~883 (1996)
- D. Rafiei, "Similarity-Based Queries for Time-Series Data", pp.13~24 (1997), acm sigmod
- B. K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms", pp.385~394 (2000)
- K. P. Chan, "Efficient Time Series Matching by Wavelets", pp.126~133 (1999)
- K. K. W. Chu, "Fast Time-Series Searching with Scaling and Shifting", pp.237~248 (1999), acm pods
- D. Q. Goldin, "On Similarity Queries for Time-Series Data：Constraint Specification and Implementation", cp, pp.137~153 (1995)
- D. Rafiei, "On Similarity-Based Queries for Time Series Data", pp.410~417 (1999)
- G. Das, "Finding Similar Time Series", pp.88~100 (1997)
- W. K. Loh, "Index Interpolation：An Approach for Subsequence Matching Supporting Normalization Transform in Time-Series Databases", pp.480~487 (2000), acm cikm
- W. K. Loh,, "Index Interpolation：A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases", Vol.E84-D(no.1), pp.76~86 (2001)
- D. J. Berndt, "Finding Patterns in Time Series：A Dynamic Programming Approach", pp.229~248 (1996)
- B. K. Yi, "Efficient Retrieval of Similar Time Sequences Under Time Warping", pp.201~208 (1998)
- S. H. Park et al, "Efficient Searches for Similar Subsequences of Difference Lengths in Sequence Databases", pp.23~32 (2000)
- S. W. Kim, "An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases", pp.607~614 (2001)
- S. H. Park, "Prefix-Querying：An Approach for Effective Subsequence Matching Under Time Warping in Sequence Databases", pp.255~262 (2001)
- L. Rabiner, "Fundamentals of Speech Recognition" (1993), Prentice Hall
- Y. S. Moon, "Duality- Based Subsequence Matching in Time-Series Databases", pp.263~272 (2001)
- Y. S. Moon, "A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows" (2002)