시계열 거리 계산에서 미리 버림 효과의 최대화 (Maximizing the Early Abandon Effect in Time Series Distance Computation)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 27권 / 2호 / 55 ~ 68페이지
· 저자명 : 이정곤, 김상필, 문양세, 김진호

초록

최근 대용량의 시계열 데이터 처리 연구가 활발하게 진행되고 있다. 이러한 시계열 데이터 처리에서 주된 연구 분야인 유사 시퀀스 매칭은 주어진 질의 시계열과 유사한 데이터 시계열을 찾는 방법이다. 본 논문에서는 유사 시퀀스 매칭의 유사 척도로 유클리디안 거리을 다루며, 기존의 미리 버림 효과를 최대화하는 방안을제시한다. 미리 버림이란, 유클리디안 거리 계산 과정 중 중간 거리 값이 사용자가 정한 허용치보다 크면 나머지 거리 계산 과정을 생략하는 방법이다. 본 논문에서는 거리 계산의 시작 오프셋(위치)을 달리 함으로써 미리 버림 효과를 최대화하고 이를 통해 성능을 향상시키는 방안을 제시한다. 첫째, 질의 시계열의 최대값 엔트리를 시작 오프셋으로 하는 최대값 오프셋 기법을 제안한다. 이는 최대값 부근에서 질의와 데이터 시계열의 거리 차이가 클 것이라는 직관에 기반한다. 둘째, 최대값 오프셋 기법을 개선하여 최대값 오프셋에서 왼쪽 및 오른쪽의 양방향으로 거리를 계산해 가는 최대값 오프셋 양방향 기법을 제안한다. 이는 최대값 부근에서 발생하는 거리 차이를 가급적 많이 활용하고자 하는 직관에 기반한다. 마지막으로 실험을 통해 제안한 방법이 기존 방법에 비해 성능을 크게 향상시킨 것을 보인다.

영어초록

In recent years, there have been many efforts on exploiting a large time‐series database, and their major research topic is similar sequence matching that identifies data sequences similar to a query sequence. In this paper, we address the problem of maximizing the early abandon effect in computing the Euclidean distances for similar sequence matching. The early abandon improves the matching performance by stopping the computation process immediately after the intermediate distance exceeds a user‐specified threshold value. We observe that the starting offset highly influences the early abandon effect, and we thus try to select the starting offset so as to maximize the early abandon effect. We first propose MaxOffset that uses the maximum entry of a query sequence as its starting offset. As an extension of MaxOffset, we then propose BiDirection that considers both directions of the maximum entry, i.e., left‐side adjacent entries as well as right‐side adjacent entries. The intuition behind these algorithms is that a large portion of the actual distance might be accumulated around maximum entries. We empirically showcase the superiority of the proposed algorithms.

참고자료

· 없음