타임 워핑 하의 효율적인 시계열 서브시퀀스 매칭을 위한 접두어 질의 기법의 확장
On Extending the Prefix-Querying Method for Efficient Time-Series Subsequence Matching Under Time Warping
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 타임 워핑 하의 시계열 서브시퀀스 매칭을 처리하는 방법에 대하여 논의한다. 타임 워핑은 시퀀스의 길이가 서로 다른 경우에도 유사한 패턴을 갖는 시퀀스들을 찾을 수 있도록 해 주는 변환이다. 접두어 질의 기법(prefix-querying method)는 착오 기각 없이 타임 워핑 하의 시계열 서브시퀀스 매칭을 처리하는 인덱스를 이용한 최초의 방식이다. 이 방법은 사용자가 질의를 편리하게 작성하도록 하기 위하여 기본 거리 함수로서 L∞를 사용한다. 본 논문에서는 L∞ 대신 타임 워핑 하의 시계열 서브시퀀스 매칭에서 기본 거리 함수로서 가장 널리 사용되는 L1을 적용할 수 있도록 접두어 질의를 확장한다. 또한, 제안된 기법으로 타임 워핑 하의 시계열 서브시퀀스 매칭을 수행하는 경우 착오 기각(false dismissal)이 발생하지 않음을 이론적으로 증명한다. 다양한 실험을 통한 성능 평가를 통하여 본 연구에서 제시하는 기법의 우수성을 검증한다. 실험 결과에 의하면, 제안된 기법은 가장 좋은 성능을 보이는 기존의 기법과 비교하여 매우 뛰어난 성능 개선 효과를 보이는 것으로 나타났다.
Abstract
This paper discusses the way of processing time-series subsequence matching under time warping. Time warping enables finding sequences with similar patterns even when they are of different lengths. The prefix-querying method is the first index-based approach that performs time-series subsequence matching under time warping without false dismissals. This method employs the L∞ as a base distance function for allowing users to issue queries conveniently. In this paper, we extend the prefix-querying method for absorbing L1, which is the most-widely used as a base distance function in time-series subsequence matching under time warping, instead of L∞. We also formally prove that the proposed method does not incur any false dismissals in the subsequence matching. To show the superiority of our method, we conduct performance evaluation via a variety of experiments. The results reveal that our method achieves significant performance improvement in orders of magnitude compared with previous methods.
참고문헌 (25)
- "Efficient Similarity Search in Sequence Databases", pp.69~84 (1993)
- "The Analysis of Time-Series:An Introduction, Third Edition" (1984), Chapman and Hall
- "Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases", pp.490~501 (1995)
- "Fast Subsequence Matching in Time-series Databases", pp.419~429 (1994)
- "Data Mining:An Overview from Database Perspective", 8(6), pp.866~883 (1996)
- "Similarity-Based Queries for Time-Series Data", pp.13~24 (1997)
- "Fast Time Sequence Indexing for Arbitrary Lp Norms", pp.385~394 (2000)
- "Efficient Time-Series Matching by Wavelets", pp.126~133 (1999)
- "Fast Time-Series Searching with Scaling and Shifting", pp.237~248 (1999)
- "On Similarity Queries for Time-Series Data:Constraint Specification and Implementation", pp.137~153 (1995)
- "On Similarity-Based Queries for Time Series Data", pp.410~417 (1999)
- "Finding Similar Time Series", pp.88~100 (1997)
- "Index Interpolation:An Approach for Subsequence Matching Supporting Normalization Transform in Time-Series Databases", pp.480~487 (2000)
- "Index Interpolation : A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases", e84-d(1), pp.76~86 (2001)
- "Finding Patterns in Time Series:A Dynamic Programming Approach", pp.229~248 (1996)
- "Efficient Retrieval of Similar Time Sequences Under Time Warping", pp.201~208 (1998)
- "Efficient Searches for Similar Subsequences of Difference Lengths in Sequence Databases", pp.23~32 (2000)
- "An Index- Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases", pp.607~614 (2001)
- "Prefix-Querying ACM : An Approach for Effective Subsequence Matching Under Time Warping in Sequence Databases", pp.255~262 (2001)
- "Fundamentals of Speech Recognition" (1993), Prentice Hall
- "Efficient Processing of Similarity Search Under Time-Warping in Sequence Databases:An Index- Based Approach", 29(5), pp.405~420 (2004)
- "private communication" (2001)
- "Optimization of Subsequence Matching Under Time Warping in Time-Series Databases", pp.581~586 (2005)
- "String Searching Algorithms" (1994), World Scientific Publishing
- "Exact Indexing of Dynamic Time Warping" (2002)