본 논문에서는 대형 시퀀스 데이타베이스에서 타임 워핑을 지원하는 유사 검색을 효과적으로 처리하는 방안에 관하여 논의한다 타임 워핑은 시퀀스의 길이가 서로 다른 경우에도 유사한 패턴을 갖는 시퀀스들을 찾을 수 있도록 해 준다. 타임 워핑 거리는 삼각형 부등식 성질을 만족하지 못하므로 기존의 기법들은 착오 기각(false dismissal) 없이 다차원인덱스를 사용할 수 없었다. 이러한 기법들은 전체 데이타베이스를 스캔해야 하므로 대형 데이타베이스에서는 심각한 성능 저하의 문제를 가진다. 서픽스 트리를 사용하는 또 다른 기법은 큰 트리로 인한 성능상의 문제를 갖는다 본 논문에서는 타임 워핑을 지원하는 효과적인 유사 검색 기법을 제안한다. 제안된 기법의 주요 목표는 착오 기각 없이 대형 데이타베이스에서도 좋은 검색 성능을 보장하는 것이다. 이러한 목표를 위하여 본 연구에서는 삼각형 부등식을 만족하는 타임 워핑 거리의 새로운 하한 거리 함수 $D_{tw-Ib}를 고안한다. D_{tw-Ib}$는 각 시퀀스로부터 타임 워핑과 무관한 4-터플 특성 벡터를 추출한 다. 제안된 기법에서는 이러한 4-터플 특성 벡터를 인덱싱 애트리뷰트로 사용하는 다차원 인덱스를 기반으로 유사 검색을 효율적으로 처리한다. 본 논문에서는 제안된 기법에서 착오 기각이 발생하지 않음을 증명한다. 또한, 제안된 기법의 우수성을 규명하기 위하여 다양한 실험을 수행한다. 실험 결과에 의하면 제안된 기법은 기존의 기법들과 비교하여 실제 S&P 500 주식 데이타에 대하여 43배, 대형 생성 데이타에 대하여 720배가지 의 성능 개선 효과를 가지는 것으로 나타났다.
This paper discusses an effective processing of similarity search that supports time warping in large sequence database. Time warping enables finding sequences with similar patterns even when they are of different length, Previous methods fail to employ multi-dimensional indexes without false dismissal since the time warping distance does not satisfy the triangular inequality. They have to scan all the database, thus suffer from serious performance degradation in large database. Another method that hires the suffix tree also shows poor performance due to the large tree size. In this paper we propose a new novel method for similarity search that supports time warping Our primary goal is to innovate on search performance in large database without false dismissal. to attain this goal ,we devise a new distance function $D_{tw-Ib}$ consistently underestimates the time warping distance and also satisfies the triangular inequality, $D_{tw-Ib}$ uses a 4-tuple feature vector extracted from each sequence and is invariant to time warping, For efficient processing, we employ a distance function, We prove that our method does not incur false dismissal. To verify the superiority of our method, we perform extensive experiments . The results reveal that our method achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.
