Subsequence matching in time-series databases is an important problem in data mining and has attracted a lot of research interest. It is a problem of finding the data sequences containing subsequences similar to a given query sequence and of finding the offsets of these subsequences in the original data sequences.
In this dissertation, we first propose a new subsequence matching method, Dual Match}, which exploits duality in constructing windows and significantly improves performance. Dual Match divides data sequences into disjoint windows and the query sequence into sliding windows, and thus, is a dual approach of the one by Faloutsos et al. (FRM in short), which divides data sequences into sliding windows and the query sequence into disjoint windows. We formally prove that our dual approach is correct, i.e., it incurs no false dismissal. We also prove that, given the minimum query length, there is a maximum bound of the window size to guarantee correctness of Dual Match and discuss the effect of the window size on performance. FRM causes a lot of false alarms (i.e., candidates that do not qualify) due to lack of point-filtering effect by storing minimum bounding rectangles (MBRs) rather than individual points representing windows to save storage space for the index. Using MBRs only causes false alarms by not allowing point-to-point comparison (which we call the point-filtering effect}) for checking the distances. Dual Match solves this problem by directly storing points without incurring excessive storage overhead.
Experimental results show that, in most cases, Dual Match provides large improvement both in false alarms and in performance over FRM given the same amount of storage space. In particular, for low selectivities (less than $10^{-4}$), Dual Match drastically reduces the number of candidates-down to as little as $\frac{1}{8800}$ of that for FRM-reduces the number of page accesses by up to 26.9 times, and improves performance up to 430-fold. On the other hand, for high selectivities (more than $10^{-2}$), it shows a very minor degradation (less than 29%) by all three measures. For selectivities in between ($10^{-4}~10^{-2}$), Dual Match shows performance slightly better than that of FRM. Dual Match also provides excellent performance in index creation. Experimental results show that it is 4.10~25.6 times faster than FRM in building indexes of approximately same sizes. The main reason for this improvement is that it requires far smaller number of transformations, which are a major part of the CPU overhead, than FRM does.
Next, we generalize the method of constructing windows. By this generalization, we can explain both FRM and Dual Match as special cases of a common framework. Based on the generalization, we propose a new subsequence matching method, General Match. Dual Match improves performance significantly over FRM by exploiting the point filtering effect. However, it has the problem of having a smaller allowable window size-half that of FRM-given the minimum query length. A smaller window increases false alarms. We call this window size effect. General Match, an improvement of Dual Match, offers advantages of both methods: it can reduce the window size effect by using large windows like FRM and, at the same time, can exploit the point-filtering effect like Dual Match.
General Match divides data sequences into J-sliding windows (generalized sliding windows) and the query sequence into J-disjoint windows(generalized disjoint windows). We formally prove that our General Match is correct, i.e., it incurs no false dismissal. We also prove that, given the minimum query length, there is a maximum bound of the window size to guarantee correctness of General Match. We then propose a method of estimating the optimal value of J that minimizes the number of page accesses. Experimental results for real stock data show that, for low selectivities ($10^{-6}~10^{-4}$), General Match improves performance by 114% over Dual Match and by 998% over FRM on the average; for high selectivities ($10^{-3}~10^{-1}$), by 46% over Dual Match and by 65% over FRM.
Overall, these results indicate that our dual approach and its generalization provide a new paradigm in subsequence matching that improves performance significantly in various kinds of database applications. These results also provide an excellent theoretical basis for understanding the underlying mechanisms in subsequence matching and for formally analyzing the performance.
시계열 데이타에 대한 서브시퀀스 매칭은 데이타 마이닝의 중요한 문제의 하나로 최근까지 많은 연구가 이루어져 왔다. 서브시퀀스 매칭은 질의 시퀀스와 유사한 서브시퀀스를 가지는 데이터 시퀀스와 해당 서브시퀀스의 위치를 찾는 문제이다.
우선, 본 논문에서는 윈도우를 구성하는 방법의 이원성(duality)을 이용한 새로운 서브시퀀스 매칭 방법인 Dual Match를 제안하고, 이 방법이 서브시퀀스 매칭의 성능을 획기적으로 향상시킬 수 있음을 보인다. Dual Match는 데이타 시퀀스를 디스조인트 윈도우로 나누고 질의 시퀀스를 슬라이딩 윈도우로 나누는 방법을 사용하는데, 이는 Faloutsos 등(간단히 FRM이라 한다)이 사용한 데이타 시퀀스를 슬라이딩 윈도우로 나누고 질의 시퀀스를 디스조인트 윈도우로 나누는 방법의 이원적 접근법이다. 본 논문에서는 이원적 접근법의 정확성을 이론적으로 증명한다. 즉, Dual Match가 착오기각을 발생하지 않음을 증명한다. 또한, Dual Match의 정확성을 보장하기 위해서는 윈도우 크기의 한계가 있음을 보이고, 윈도우 크기와 성능과의 관계를 논의한다. FRM은 색인에 필요한 저장공간을 줄이기 위하여 윈도우가 변환된 개별 점 대신 최소 포함 사각형(MBR)만을 저장함으로 인하여 많은 착오해답(즉, 유사하지 않은 후보 서브시퀀스)을 발생시킨다. 오직 MBR만을 저장하게 되면 색인 검색 과정에서 점대점 비교(point-to-point comparison)의 수행(이를 sc 점 여과 효과라 한다)을 할 수 없기 때문이다. 제안하는 Dual Match는 FRM과 비슷한 크기의 저장공간으로 개별 점을 직접 저장함으로써 이 문제를 해결한다.
실험 결과, Dual Match는 많은 경우에 있어서 FRM에 비하여 후보 개수를 크게 줄이고 성능을 향상시켰다. 특히, 선택률이 낮은 경우($10^{-4}$ 이하)에는 후보 개수를 최대 8800배까지 줄이고, 페이지 액세스 횟수를 최대 26.9배까지 줄였으며, 성능을 최대 430배까지 향상시켰다. 선택률이 $10^{-4}~10^{-2}$인 경우에는 세 가지 실험 결과 모두 Dual Match가 FRM 보다 약간 더 우수한 것으로 나타났다. 단, 선택률이 높은 경우($10^{-2}$ 이상)에는 후보 개수와 페이지 액세스 횟수가 약간 늘고 성능이 약간 저하(29% 미만)되는 것으로 나타났다. 또한, Dual Match는 색인 생성에 있어서 매우 좋은 성능을 나타낸다. 실험 결과, 동일한 크기의 색인을 생성하는데 있어서 Dual Match는 FRM보다 4.10~25.6배 빠르게 색인을 구성하였다. 이는 색인 구성 시에 CPU 오버헤드의 많은 부분을 차지하는 저차원 변환의 횟수를 FRM에 비해 크게 줄일 수 있기 때문이다.
다음으로, Dual Match의 개념을 확장하여 윈도우 구성법을 일반화한다. 이러한 일반화에 따라, FRM과 Dual Match는 동일한 프레임워크 안에서 설명될 수 있다. 그리고, 이러한 윈도우 구성의 일반화에 기반하여, 새로운 서브시퀀스 매칭 방법인 General Match를 제안한다. Dual Match는 점 여과 효과를 발휘하여 착오해답을 크게 줄이고 성능을 향상시킨다. 그러나, Dual Match는 주어진 최소 질의 시퀀스 길이에서 최대 윈도우 크기가 FRM의 1/2로 작은 문제가 있다. 이는 윈도우 크기가 작을수록 착오해답이 증가하는 효과에 따른 문제로, 본 논문에서는 이를 sc 윈도우 크기 효과라 정의한다. General Match는 Dual Match를 더욱 개선한 방법으로서, 두 방법의 장점을 모두 취한 방법이다: General Match는 FRM과 같이 큰 윈도우를 사용하여 윈도우 크기 효과를 크게 발휘하는 동시에, Dual Match와 같이 점 여과 효과를 발휘한다. General Match는 슬라이딩 윈도우를 일반화한 J-슬라이딩 윈도우로 데이타 시퀀스를 나누고, 디스조인트 윈도우를 일반화한 J-디스조인트 윈도우로 질의 시퀀스를 나누는 방법을 사용한다. 본 논문에서는 General Match의 정확성, 즉, General Match가 착오기각이 발생하지 않음을 증명한다. 그리고, 주어진 최소 질의 시퀀스 길이에 대해 General Match가 바르게 동작하기 위한 최대 윈도우 크기가 있음을 증명한다. 또한, 페이지 액세스 횟수를 최소로 하는 J 값의 결정 방법을 제안한다. 실제 주식 데이타에 대한 실험 결과, General Match는 낮은 선택률 범위($10^{-6}~10^{-4}$)에서 Dual Match에 비해 평균 114%, FRM에 비해 평균 998% 성능을 향상시켰으며, 높은 선택률 범위($10^{-3}~10^{-1}$)에서도 Dual Match에 비해 평균 46%, FRM에 비해 평균 65% 성능을 향상시켰다.
이러한 결과는 제안한 이원적 접근법과 이의 일반화가 다양한 데이터베이스 응용들에서 사용되는 서브시퀀스 매칭의 성능을 크게 향상시킬 수 있는 획기적인 연구 결과임을 보여주고 있다. 또한, 본 논문의 연구 결과는 서브시퀀스 매칭에 대한 기본 메카니즘의 이해와 서브시퀀스 매칭의 성능을 체계적으로 분석하기 위한 이론적 기반을 제공해주고 있다.
