시계열 데이터베이스에서 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭 A Single Index Approach for Subsequence Matching that Supports Normalization Transform in Time-Series Databases원문보기
정규화 변환은 시계열 시퀀스를 구성하는 엔트리들의 전체적인 패턴을 분석하는데 매우 유용하다. 본 논문에서는 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭 방법을 제안한다. 기존의 정규화 변환 지원 서브시퀀스 매칭 방법은 다양한 길이의 질의 시퀀스를 지원하기 위하여 여러 개의 색인을 생성해야 하고, 이에 따라 색인 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생한다. 본 논문에서는 하나의 색인을 사용하면서도 다양한 길이의 질의 시퀀스에 대한 정규화 변환을 지원하는 효율적인 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 정규화 변환을 일반화한 포함-정규화 변환(inclusion-normalization transform) 개념을 제시한다. 포함 정규화 변환이란 색인에 저장할 윈도우에 대해서 해당 윈도우를 포함하는 서브시퀀스의 평균과 표준편차로 정규화하는 것으로서, 기본적인 정규화 변환을 윈도우 및 서브시퀀스 개념을 사용하여 확장한 것이다. 다음으로, 포함-정규화 변환을 기존 서브시퀀스 매칭 연구에 적용하기 위한 이론적 근거를 정리로서 제시하고 증명한다. 그리고, 이 방안을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 $2.5{\sim}2.8$배까지 성능을 향상 시킨 것으로 나타났다. 본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 정규화 변환 이외의 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있는 좋은 연구결과라 사료된다.
정규화 변환은 시계열 시퀀스를 구성하는 엔트리들의 전체적인 패턴을 분석하는데 매우 유용하다. 본 논문에서는 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭 방법을 제안한다. 기존의 정규화 변환 지원 서브시퀀스 매칭 방법은 다양한 길이의 질의 시퀀스를 지원하기 위하여 여러 개의 색인을 생성해야 하고, 이에 따라 색인 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생한다. 본 논문에서는 하나의 색인을 사용하면서도 다양한 길이의 질의 시퀀스에 대한 정규화 변환을 지원하는 효율적인 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 정규화 변환을 일반화한 포함-정규화 변환(inclusion-normalization transform) 개념을 제시한다. 포함 정규화 변환이란 색인에 저장할 윈도우에 대해서 해당 윈도우를 포함하는 서브시퀀스의 평균과 표준편차로 정규화하는 것으로서, 기본적인 정규화 변환을 윈도우 및 서브시퀀스 개념을 사용하여 확장한 것이다. 다음으로, 포함-정규화 변환을 기존 서브시퀀스 매칭 연구에 적용하기 위한 이론적 근거를 정리로서 제시하고 증명한다. 그리고, 이 방안을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 $2.5{\sim}2.8$배까지 성능을 향상 시킨 것으로 나타났다. 본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 정규화 변환 이외의 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있는 좋은 연구결과라 사료된다.
Normalization transform is very useful for finding the overall trend of the time-series data since it enables finding sequences with similar fluctuation patterns. The previous subsequence matching method with normalization transform, however, would incur index overhead both in storage space and in u...
Normalization transform is very useful for finding the overall trend of the time-series data since it enables finding sequences with similar fluctuation patterns. The previous subsequence matching method with normalization transform, however, would incur index overhead both in storage space and in update maintenance since it should build multiple indexes for supporting arbitrary length of query sequences. To solve this problem, we propose a single index approach for the normalization transformed subsequence matching that supports arbitrary length of query sequences. For the single index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. The inclusion-normalization transform normalizes a window by using the mean and the standard deviation of a subsequence that includes the window. Next, we formally prove correctness of the proposed method that uses the inclusion-normalization transform for the normalization transformed subsequence matching. We then propose subsequence matching and index building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to $2.5{\sim}2.8$ times over the previous method. Our approach has an additional advantage of being generalized to support many sorts of other transforms as well as normalization transform. Therefore, we believe our work will be widely used in many sorts of transform-based subsequence matching methods.
Normalization transform is very useful for finding the overall trend of the time-series data since it enables finding sequences with similar fluctuation patterns. The previous subsequence matching method with normalization transform, however, would incur index overhead both in storage space and in update maintenance since it should build multiple indexes for supporting arbitrary length of query sequences. To solve this problem, we propose a single index approach for the normalization transformed subsequence matching that supports arbitrary length of query sequences. For the single index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. The inclusion-normalization transform normalizes a window by using the mean and the standard deviation of a subsequence that includes the window. Next, we formally prove correctness of the proposed method that uses the inclusion-normalization transform for the normalization transformed subsequence matching. We then propose subsequence matching and index building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to $2.5{\sim}2.8$ times over the previous method. Our approach has an additional advantage of being generalized to support many sorts of other transforms as well as normalization transform. Therefore, we believe our work will be widely used in many sorts of transform-based subsequence matching methods.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
즉, 데이터 시퀀스 S를 나눈 윈도우 S[a:切에 대해서, S[a:b]를 포함하는 모든 가능한 서브시퀀스 S[订]를 사용하여 정규화 변환하고 관리 하는 과정이 필요하다. 따라서, 본 논문에서는 윈도우가 주 어졌을 때, 해당 윈도우를 포함하는 서브시퀀스로 정규화하는 포함-정규화 변환을 정의하고, 이를 사용하여 정규화 변 환 서브시퀀스 매칭을 수행하는 방법을 제안한다.
본 논문에서는 서브시퀀스 매칭에서 정규화 변환을 지원하는 유사 시퀀스 모델[9]을 다룬다. 즉, 질의 시퀀스 Q와 데이터 서브시퀀스 S[订]의 거리를 비교하는 것이 아니라, 이들 을 정규화 변환한 이후의 두 시퀀스 Q와 范31의 거리를 비교하여, 변환된 두 시퀀스가 b매치하는지의 여부를 판단 하는 유사 시퀀스 모델을 다룬다.
서브시퀀스 매칭은 전체 매칭을 일반화한 것으로, 보다 많은 응용 분야를 가진 다[6, 8-11, 16], 그리고, 유클리디안 거리 함수가 갖는 문제점을 보완하기 위하여, 정규화(normalization)!, 15], 이동 평균(moving average)[8, 15], 쉬프팅 및 스케일링(shifting & scaling)[2, 5, 14], 타임 워핑 (time warping)[7, 13, 17] 등의 많은 변환 기법이 사용되었다. 본 논문에서는 이 중 정규 화 변환을 지원하는 유사 시퀀스 매칭 문제를 다룬다. 정규 화 변환(normalization transform)■$: 시퀀스 엔트리들의 평 균과 표준편차를 구한 후, 각 엔트리에서 평균을 빼고 표준 편차로 나누는 변환이다.
본 논문에서는 하나의 색인을 사용하면서도 다양한 길이 의 질의 시퀀스에 대한 정규화 변환 서브시퀀스 매칭을 효 율적으로 수행하는 새로운 접근법을 제안한다. 이를 위해 우선, 윈도우 S[a:切에 대해서, S[a-b] 자체의 평균과 표준편 차가 아닌 £[a:b]를 포함하는 서브시퀀스 S[;:j](( < a < b < “의 평균과 표준편차로 정규화하는 포함-정규화 변환 (inclusion-normalization transform) 개념을 제시한다.
본 논문에서는 하나의 색인을 사용하여 정규화 변환 서브 시퀀스 매칭을 효율적으로 수행하는 새로운 접근법을 제안 하였다. 기존의 정규화 변환 서브시퀀스 매칭은 여러 색인 의 생성에 따른 색인 공간의 오버헤드와 색인 관리의 오버 헤드가 발생하는 문제점이 있다.
또한, 질의 시퀀스 길이가 윈도우 크기 보다 큰 일부 경우에 대해서는 색인을 사용하 지 못하고 순차 스캔을 해야 하는 경우도 발생한다. 이를 해결하기 위하여, 본 논문에서 우선 정규화 변환을 일반화 하여 포함-정규화 변환 개념을 제안하였다. 그리고, 포함-정 규화 변환을 사용하면, 하나의 색인을 사용해서도 다양한 길이의 질의 시퀀스에 대해 효율적인 정규화 변환 서브시퀀 스 매칭을 수행할 수 있음을 보였다.
가설 설정
[정리 1] 데이터 시퀀스 S의 서브시퀀스 SI上/]를 정규화 변환한 即侦]와 질의 시퀀스 Q를 정규화 변환한 Q가 e-매치한다면, 적어도 하나 이상의 0의 k 번째 디스조인트 윈도우 砂 와 : j] 에 포함된 슬라이딩 윈도우 S|, ;)1[i + (/c-l)-<o:i + Jr-ffl-l] 7} e/而-매치한다. 여기에서, isksp 이고, p = W〃(Q)/이 이다.
제안 방법
다음으로, 유사 시퀀스 매칭 알고리즘에서는 질의 시퀀스를 데이터 시퀀스와 동일한 방법으로 戶차원 점으로 변환하고, 변환한 점과 허용치 E을 사용하여 범위 질의 (range query)를 구성한다. 그리고, 범위 질의로 R*-트리를 검색하여, E-매치 하는 모든 점들을 찾아 후보(candidate, 질의 시퀀스와 "매 치할 가능성이 높은 데이터 시퀀스) 집합을 구한다. 이렇게 후보 집합을 구하면 착오기각dismissal, 유사 시퀀스 이나 착오로 인해 기각되는 데이터 시퀀스)은 발생하지 않지 만, 시퀀스 길이 〃대신/개의 특성만을 사용함으로 인하여 착 오해답Sz/se alarm, 후보이나 실제로는 질의 시퀀스와 广매 치하지 않는 데이터 시퀀스)이 발생할 수 있다.
따라서, S[a:切를 정규화 변환한 시퀀스 员顽와 S[爾]를 认%勺1)와 次糸:力)를 사용하여 포함-정규화 변환 한 시퀀스 S间[0:b] 는 유사한 값을 가질 것이다. 결과적으 로, 윈도우 S[a:切를 여러 서브시퀀스 S[灯]들로 포함-정규화 변환한 윈도우 S回][0: 用들은 유사한 엔트리들을 가질 것이 고, 본 논문에서는 이러한 성질을 사용하여 새로운 정규화 변환 서브시퀀스 매칭 방법을 제안한다.
셋째, 포함-정규화 변환을 기존 서 브시퀀스 매칭 방법인 FRM에 적용하는 방안의 이론적 근 거를 정리로서 제시하고 증명하였다. 넷째, 이 방안을 구현 하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제안하였다. 마지막으로, 실험을 통해 제안한 방 법의 우수성을 입증하였다.
다음으로, 포함-정규화 변환을 서브시퀀스 매칭의 기존 연구인 Faloutsos 등의 연구[2](간략히, FRM이라 한다)에 적용한 새로운 정규화 변환 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 포함-정규화 변환의 개념을 사용하 면, FRM에서 사용되었던 정리들을 그대로 활용하여 정규화 변환 서브시퀀스 매칭을 수행할 수 있음을 보인다.
이 실험에서는, 최소 질의 시퀀스 길이로 256을 사용하여, 두 방법 모두 윈도우 크기는 최소 질의 시퀀스 길이와 같은 256으로 설정하였고, 가능한 질의 시퀀스 길이는 256, 512, 768, 1024의 네 가지를 사용하였다. 두 번째 실험에서는, 여러 색인을 사용하는 색인 보간법 측면에서 두 가지 방법을 비교하였다. 이를 위해, 윈도우 크기 256, 512, 1024에 대해서 색인을 구성하고, 이들 길이를 포함하여 384, 640, 768, 896에 대해 질의 시퀀스를 구성하고 성능 실험을 수행하였다.
첫째, 기존 정규화 변환 서브시퀀스 매칭의 문제점을 분석하였다. 둘째, 정규화 변환을 일반화하여 포함-정규화 변환 개념을 정형적으로 정의하였다. 셋째, 포함-정규화 변환을 기존 서 브시퀀스 매칭 방법인 FRM에 적용하는 방안의 이론적 근 거를 정리로서 제시하고 증명하였다.
특히, 데이터 시퀀스를 나눈 각각의 윈도우에 포함-정규화 변환을 적용하는 FRM 기반의 새로운 접근법이 정규화 변환 서브 시퀀스 매칭을 정확하게 수행함을 정리로서 제시하고 증명 한다. 또한, FRM 기반의 정규화 변환 서브시퀀스 매칭을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 Loh 등의 기존 방법 [9]에 비해 최대 2.
FRM에서는 데이터 시퀀스를 나눈 슬라이딩 윈도우를 하나의 점으로 매핑하는 방법을 사용하였다. 반면어), 제안하는 방법에서는 각 윈도우를 하나의 점 이 아닌 여러 개의 점을 포함하는 MBR로 매핑시킨다. 즉, 데이터 시퀀스를 나눈 윈도우를 직접 정규화 변환하는 대신, 해당 윈도우를 포함하는 여러 서브시퀀스를 사용하여 여러 개의 윈도우로 포함-정규화 변환하고, 이들 윈도우를 저차 원 변환한 점들을 포함하는 MBR을 구성한다.
본 장에서는 단일 색인을 사용한 정규화 변환 서브시퀀스 매칭을 제안한다. 제4.
실험 결과로는 두 방법의 실제 수행 시간을 측정하였다. 질의 시퀀스는 데이터 시퀀스의 임의 위치(random offset)를 시작 엔트리로 하는 Z㎛(Q)의 서브시퀀스를 추출하여 사용 하였으며, 노이즈(noise) 효과를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다.
그런데, FRM-NT는 데이터 시퀀스를 슬라이딩 윈도우로 나누므로, 너무 많은 윈도우가 생성되는 문제가 있다. 이러한 문제점을 해결하기 위하여, FRM에서는 여러 개의 슬라 이딩 윈도우를 하나의 MBR에 포함시키는 방법을 사용하였 다[61 따라서, 제안하는 FRM-NT에서도 여러 개의 슬라이 딩 윈도우가 변환된 여러 개의 MBR을 하나의 MBR에 포함 시키는 방법을 사용한다. 즉, 연속된 여러 슬라이딩 윈도우 를 대표하는 MBR을 구성하고, 이 MBR의 첫 번째 및 마지 막 슬라이딩 윈도우 시작 위치와 함께 다차원 색인에 저장 하는 방법을 사용한다.
본 논문에서는 하나의 색인을 사용하면서도 다양한 길이 의 질의 시퀀스에 대한 정규화 변환 서브시퀀스 매칭을 효 율적으로 수행하는 새로운 접근법을 제안한다. 이를 위해 우선, 윈도우 S[a:切에 대해서, S[a-b] 자체의 평균과 표준편 차가 아닌 £[a:b]를 포함하는 서브시퀀스 S[;:j](( < a < b < “의 평균과 표준편차로 정규화하는 포함-정규화 변환 (inclusion-normalization transform) 개념을 제시한다. 그리 고, 이러한 포함-정규화 변환을 사용하여 다차원 색인을 구 성하면, 하나의 색인을 사용해서도 정규화 변환 서브시퀀스 매칭을 수행할 수 있음을 보인다.
두 번째 실험에서는, 여러 색인을 사용하는 색인 보간법 측면에서 두 가지 방법을 비교하였다. 이를 위해, 윈도우 크기 256, 512, 1024에 대해서 색인을 구성하고, 이들 길이를 포함하여 384, 640, 768, 896에 대해 질의 시퀀스를 구성하고 성능 실험을 수행하였다. 저차원 변환을 위한 특성 추출 함수로는 DFT(Discrete Fourier Transform) 변환[12]과 웨이블릿(Wavelet) 변환[4] 을 사용하였으며, 특성은 6개를 사용하였다[6, 11].
제안하는 정규화 변환 서브시퀀스 매칭에서는 데이터 시 퀀스를 나눈 각 윈도우를 다차원 색인의 하나의 MBR로 매 핑하는 방법을 사용한다. FRM에서는 데이터 시퀀스를 나눈 슬라이딩 윈도우를 하나의 점으로 매핑하는 방법을 사용하였다.
제안한 방법의 우수성을 입증하기 위하여 두 가지 종류의 데이터를 사용하여 실험을 수행하였다. 사용한 데이터는 하나의 긴 데이터 시퀀스로 구성된 것으로서, 이는 여러 개의 데이터 시퀀스로 구성된 경우와 동일한 효과를 가진다[6, 11], 첫 번째 데이터는 기존 연구[6, 11, 12]에서 사용한 실제 주식 데이터로서 약 33만개의 엔트리로 구성되어 있으며, 이를 STOCK-DATA라 한다.
본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 스케일링 및 쉬프팅, 이동 평균 등 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 즉, 기존의 방법들 이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도우에 대해서 확장 변환의 개념을 도입하여, 변환된 윈도우를 만들고 이를 서 브시퀀스 매칭에 활용한다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시 퀀스 매칭에 폭넓게 적용될 수 있을 것으로 사료된다.
Loh 등은 식 (5)를 사용하여, 정규화 변환된 질의 윈도우 0E] 가 정규화 변환된 데이터 윈도우 S[i: j] 와 砂 -매치할 때, 해당 데이터 윈도우를 포함하는 서브시퀀스를 후보로 삼는 방법을 사용하였다. 즉, 데이터 시퀀스를 나눈 윈도우를 정규화 변환하여 다차원 색인에 저장하고, 이 다차원 색인을 검색 할 때, 주어진 허용치 인 e 대신 * 을 사용하는 방법을 제안 하였다.
반면어), 제안하는 방법에서는 각 윈도우를 하나의 점 이 아닌 여러 개의 점을 포함하는 MBR로 매핑시킨다. 즉, 데이터 시퀀스를 나눈 윈도우를 직접 정규화 변환하는 대신, 해당 윈도우를 포함하는 여러 서브시퀀스를 사용하여 여러 개의 윈도우로 포함-정규화 변환하고, 이들 윈도우를 저차 원 변환한 점들을 포함하는 MBR을 구성한다. 결국, 하나의 윈도우는 하나의 점이 아닌 하나의 MBR로 변환되며, 이 MBR을 다차원 색인에 저장한다.
이러한 문제점을 해결하기 위하여, FRM에서는 여러 개의 슬라 이딩 윈도우를 하나의 MBR에 포함시키는 방법을 사용하였 다[61 따라서, 제안하는 FRM-NT에서도 여러 개의 슬라이 딩 윈도우가 변환된 여러 개의 MBR을 하나의 MBR에 포함 시키는 방법을 사용한다. 즉, 연속된 여러 슬라이딩 윈도우 를 대표하는 MBR을 구성하고, 이 MBR의 첫 번째 및 마지 막 슬라이딩 윈도우 시작 위치와 함께 다차원 색인에 저장 하는 방법을 사용한다. 그러나, 설명의 편의상, 본 논문에서는 (그림 4)의 알고리즘과 같이 각 슬라이딩 윈도우에 해당하는 MBR을 직접 저장하고 서브시퀀스 매칭을 수행하는 것으로 기술한다.
본 논문에서는 서브시퀀스 매칭에서 정규화 변환을 지원하는 유사 시퀀스 모델[9]을 다룬다. 즉, 질의 시퀀스 Q와 데이터 서브시퀀스 S[订]의 거리를 비교하는 것이 아니라, 이들 을 정규화 변환한 이후의 두 시퀀스 Q와 范31의 거리를 비교하여, 변환된 두 시퀀스가 b매치하는지의 여부를 판단 하는 유사 시퀀스 모델을 다룬다. 이와 같이 정규화 변환한 이후에 서브시퀀스 매칭을 수행하는 방법을 본 논문에서는 정규화 변환 서브시퀀스 ^11 (normalization transformed subsequence 〃iatc/u7?g) 이라 정의한다.
실험 결과로는 두 방법의 실제 수행 시간을 측정하였다. 질의 시퀀스는 데이터 시퀀스의 임의 위치(random offset)를 시작 엔트리로 하는 Z㎛(Q)의 서브시퀀스를 추출하여 사용 하였으며, 노이즈(noise) 효과를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다. 질의에 대한 선택률[6, 9]은 lb5으로 설정하였는데, 이는 대용량 시계열 데이터에서 일부 결과만을 선택하는 경우, 즉 선택률이 낮은 경우가 실용 적으로 의미를 가지기 때문이다[9, 11, 12],
다차원 색인으로는 두 방법 모두 R*-트리[3]를 사용하였으며, 데이터 페이지 및 색인 페이지의 크기는 4096 바이트를 사용하였다. 첫 번째 실험에서는, 공평한 비교를 위하여 두 방법 모두 하나의 색인을 생성하고 실험하였다. 이 실험에서는, 최소 질의 시퀀스 길이로 256을 사용하여, 두 방법 모두 윈도우 크기는 최소 질의 시퀀스 길이와 같은 256으로 설정하였고, 가능한 질의 시퀀스 길이는 256, 512, 768, 1024의 네 가지를 사용하였다.
본 논문의 공헌은 다음과 같이 요약할 수 있다. 첫째, 기존 정규화 변환 서브시퀀스 매칭의 문제점을 분석하였다. 둘째, 정규화 변환을 일반화하여 포함-정규화 변환 개념을 정형적으로 정의하였다.
대상 데이터
6 운 영체제이다. 다차원 색인으로는 두 방법 모두 R*-트리[3]를 사용하였으며, 데이터 페이지 및 색인 페이지의 크기는 4096 바이트를 사용하였다. 첫 번째 실험에서는, 공평한 비교를 위하여 두 방법 모두 하나의 색인을 생성하고 실험하였다.
사용한 데이터는 하나의 긴 데이터 시퀀스로 구성된 것으로서, 이는 여러 개의 데이터 시퀀스로 구성된 경우와 동일한 효과를 가진다[6, 11], 첫 번째 데이터는 기존 연구[6, 11, 12]에서 사용한 실제 주식 데이터로서 약 33만개의 엔트리로 구성되어 있으며, 이를 STOCK-DATA라 한다. 두 번째 데이터는 합성 데이터 (synthetic data)로서 데이터 시퀀스의 시작 엔트리를 1.5로 하고, 각 엔트리에 (-0.001, 0.001) 사이의 임의의 값 하나를 더하여 다음 엔트리를 구하는 방식으로 생성된 100만개의 랜 덤 워크 데이터(random walk data)이다. 이 데이터 역시 기존 연구[6, 11, 12]에서 사용한 것으로서 이를 WALK-DATA라 한다.
성능 평가는 제안한 FRM-NT와 Loh 등[9]의 기존 연구 (저자의 이름을 따서 간략히 LKW라 한다)를 대상으로 하였다. 실험을 수행한 하드웨어 플랫폼은 Intel Pentium IV
첫 번째 실험에서는, 공평한 비교를 위하여 두 방법 모두 하나의 색인을 생성하고 실험하였다. 이 실험에서는, 최소 질의 시퀀스 길이로 256을 사용하여, 두 방법 모두 윈도우 크기는 최소 질의 시퀀스 길이와 같은 256으로 설정하였고, 가능한 질의 시퀀스 길이는 256, 512, 768, 1024의 네 가지를 사용하였다. 두 번째 실험에서는, 여러 색인을 사용하는 색인 보간법 측면에서 두 가지 방법을 비교하였다.
이론/모형
이를 위해, 윈도우 크기 256, 512, 1024에 대해서 색인을 구성하고, 이들 길이를 포함하여 384, 640, 768, 896에 대해 질의 시퀀스를 구성하고 성능 실험을 수행하였다. 저차원 변환을 위한 특성 추출 함수로는 DFT(Discrete Fourier Transform) 변환[12]과 웨이블릿(Wavelet) 변환[4] 을 사용하였으며, 특성은 6개를 사용하였다[6, 11].
제안하는 정규화 변환 서브시퀀스 매칭 방법은 FRM의 서브시퀀스 매칭 방법에 포함-정규화 변환을 적용한 방법이 다(이를 간략히 FRM-NT(FRM that supports Normalization Transform)이라 한다)4). 제안하는 FRM-NT는 다음 정리 1에 기반하여 정규화 변환 서브시퀀스 매칭을 수행한다.
성능/효과
(그림 8) 단일 색인을 사용하고 DFT 변환을 사용한 경우의 실험 결과
결과적으로 볼 때, LKW는 특정 질의 시퀀스에 최적화한 방법인 반면, FRM-NT는 모든 질의 시퀀스 길이에 대해 골 고루 성능을 향상시킨 방법이라 할 수 있다
. 즉, LKW는 질 의 시퀀스 길이가 윈도우 크기와 동일한 경우에 가장 좋은 성능을 보이나, 질의 시퀀스 길이가 윈도우 크기보다 큰 경우에는 성능이 좋지 않은 결과를 보인다.
이를 해결하기 위하여, 본 논문에서 우선 정규화 변환을 일반화 하여 포함-정규화 변환 개념을 제안하였다. 그리고, 포함-정 규화 변환을 사용하면, 하나의 색인을 사용해서도 다양한 길이의 질의 시퀀스에 대해 효율적인 정규화 변환 서브시퀀 스 매칭을 수행할 수 있음을 보였다.
(그림 10)은 복수 개 색인을 사용하고 DFT 변환을 사용한 경우의 실험 결과이다. 그림을 보면, 질의 시퀀스의 길이 가 256, 512, 1024인 경우, 즉 다차원 색인이 생성된 경우에는 LKW가 FRM-NT보다 성능이 우수한 것으로 나타났다. 이는 앞서 실험 1)과 2)에서 설명한 바와 같이, LKW는 질 의 시퀀스 길이와 색인 구성에 사용된 윈도우 크기가 동일한 경우에 최적의 성능을 나타내기 때문이다.
넷째, 이 방안을 구현 하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제안하였다. 마지막으로, 실험을 통해 제안한 방 법의 우수성을 입증하였다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 2.
즉, LKW는 질 의 시퀀스 길이가 윈도우 크기와 동일한 경우에 가장 좋은 성능을 보이나, 질의 시퀀스 길이가 윈도우 크기보다 큰 경우에는 성능이 좋지 않은 결과를 보인다. 반면어】, FRM-NT 는 질의 시퀀스 길이가 윈도우 크기와 같은 경우에는 LKW 에 비해 성능이 떨어지나, 같지 않는 경우에도 LKW에 비해 비교적 우수한 성능을 보임을 알 수 있다. 실험결과를 요 약하면, FRM-NT는 LKW에 비해 STOCK-DATA의 경우 최대 2.
(그림 9)의 결과를 보면, (그림 8)과 마찬가지로, 질의 시퀀스의 길이가 256인 경우에는 LKW의 성능이 FRM-NT 보다 우수함을 알 수 있다. 반면에 질의 시퀀스 길이가 윈도우 크기보다 큰 경우에는 FRM-NT의 성능이 LKW보다 우수한 것으로 나타났다. 앞서 설명한 바와 같이, 이는 LKW의 경우 질의 시 퀀스 길이가 윈도우 크기와 같은 경우로 최적화된 반면에, FRM-NT는 다양한 길이를 고루 고려하기 때문이다.
이는 앞서 실험 1)과 2)에서 설명한 바와 같이, LKW는 질 의 시퀀스 길이와 색인 구성에 사용된 윈도우 크기가 동일한 경우에 최적의 성능을 나타내기 때문이다. 반면에, 질의 시퀀스 길이가 384, 640, 768, 896인 경우, 즉 다차원 색인이 생성되지 않은 경우에는 제안한 FRM-NT가 LKW보다 우수한 성능을 보임을 알 수 있다. 이는 FRM-NT의 경우 색 인이 생성된 길이뿐 아니라 모든 질의 시퀀스 길이에 대해서 골고루 성능을 향상시키기 때문이다.
본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 스케일링 및 쉬프팅, 이동 평균 등 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 즉, 기존의 방법들 이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도우에 대해서 확장 변환의 개념을 도입하여, 변환된 윈도우를 만들고 이를 서 브시퀀스 매칭에 활용한다.
둘째, 정규화 변환을 일반화하여 포함-정규화 변환 개념을 정형적으로 정의하였다. 셋째, 포함-정규화 변환을 기존 서 브시퀀스 매칭 방법인 FRM에 적용하는 방안의 이론적 근 거를 정리로서 제시하고 증명하였다. 넷째, 이 방안을 구현 하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제안하였다.
또한, FRM 기반의 정규화 변환 서브시퀀스 매칭을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 Loh 등의 기존 방법 [9]에 비해 최대 2. 5~2.
마지막으로, 실험을 통해 제안한 방 법의 우수성을 입증하였다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 2.5~2.8배까지 성능을 향상 시킨 것으로 나타났다.
이외 에도, 색인 검색 범위인 * 을 구할 때, 제곱근 내의 값이 음수가 되는 경우(3 -g、2(卽』<0), 색인을 사용하지 못하고 순차 스캔을 사용해야 하는 문제점이 있다. 실험 결과, 질의 시퀀스 길이가 윈도우 크기의 두 배 이상이 되면, 색인을 사용하지 못하고 순차 스캔을 해야 하는 경우가 종 종 발생하는 것으로 나타났다.
반면어】, FRM-NT 는 질의 시퀀스 길이가 윈도우 크기와 같은 경우에는 LKW 에 비해 성능이 떨어지나, 같지 않는 경우에도 LKW에 비해 비교적 우수한 성능을 보임을 알 수 있다. 실험결과를 요 약하면, FRM-NT는 LKW에 비해 STOCK-DATA의 경우 최대 2.8배, WALK-DATA의 경우 최대 1.4배까지 성능을 향상 시킨 것으로 나타났다.
앞서 설명한 바와 같이, 이는 LKW의 경우 질의 시 퀀스 길이가 윈도우 크기와 같은 경우로 최적화된 반면에, FRM-NT는 다양한 길이를 고루 고려하기 때문이다. 웨이블 릿 변환의 실험결과를 요약하면, STOCK-DATA 와 WALK-DATA에 있어서, FRM-NT는 LKW에 비해 수행 시간을 최대 2.5배 및 1.4배까지 각각 줄인 것으로 나타났다.
다음으로, 포함-정규화 변환을 서브시퀀스 매칭의 기존 연구인 Faloutsos 등의 연구[2](간략히, FRM이라 한다)에 적용한 새로운 정규화 변환 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 포함-정규화 변환의 개념을 사용하 면, FRM에서 사용되었던 정리들을 그대로 활용하여 정규화 변환 서브시퀀스 매칭을 수행할 수 있음을 보인다. 특히, 데이터 시퀀스를 나눈 각각의 윈도우에 포함-정규화 변환을 적용하는 FRM 기반의 새로운 접근법이 정규화 변환 서브 시퀀스 매칭을 정확하게 수행함을 정리로서 제시하고 증명 한다.
이는 FRM-NT의 경우 색 인이 생성된 길이뿐 아니라 모든 질의 시퀀스 길이에 대해서 골고루 성능을 향상시키기 때문이다. 이와 같이, 제안한 FRM-NT는 복수 개의 색인을 생성하는 환경에서도 LKW 와 유사하거나 우수한 성능을 보임을 알 수 있다. DFT 변 환 대신에 Wavelet 변환을 사용한 경우도 유사한 결과를 얻 었으며, 지면 관계상 자세한 내용은 생략한다.
결과적으로 볼 때, LKW는 특정 질의 시퀀스에 최적화한 방법인 반면, FRM-NT는 모든 질의 시퀀스 길이에 대해 골 고루 성능을 향상시킨 방법이라 할 수 있다. 즉, LKW는 질 의 시퀀스 길이가 윈도우 크기와 동일한 경우에 가장 좋은 성능을 보이나, 질의 시퀀스 길이가 윈도우 크기보다 큰 경우에는 성능이 좋지 않은 결과를 보인다. 반면어】, FRM-NT 는 질의 시퀀스 길이가 윈도우 크기와 같은 경우에는 LKW 에 비해 성능이 떨어지나, 같지 않는 경우에도 LKW에 비해 비교적 우수한 성능을 보임을 알 수 있다.
후속연구
즉, 기존의 방법들 이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도우에 대해서 확장 변환의 개념을 도입하여, 변환된 윈도우를 만들고 이를 서 브시퀀스 매칭에 활용한다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시 퀀스 매칭에 폭넓게 적용될 수 있을 것으로 사료된다.
참고문헌 (17)
Agrawal, R., Faloutsos, C., and Swami, A., 'Efficient Similarity Search in Sequence Databases,' In Proc. the 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, pp.69-84, Oct., 1993
Agrawal, R., Lin, K.-I., Sawhney, H. S., and Shim, K., 'Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases,' In Proc. the 21st Int'l Conf. on Very Large Data Bases, Zurich, Switzerland, pp.490-501, Sept., 1995
Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B., 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Atlantic City, New Jersey, pp.322-331, May, 1990
Chan, K.-P., Fu, A. W. C., and Yu, C. T., 'Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping,' IEEE Trans. on Knowledge and Data Engineering, Vol.15, No.3, pp.686-705, Jan./Feb., 2003
Chu, K. W. and Wong, M. H., 'Fast Time-Series Searching with Scaling and Shifting,' In Proc. the 15th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, pp.237-248, June, 1999
Faloutsos, C., Ranganathan, M., and Manolopoulos, Y., 'Fast Subsequence Matching in Time-Series Databases,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Minneapolis, Minnesota, pp.419-429, May, 1994
Kim, S.-W., Park, S, and Chu, W. W., 'Efficient Processing of Similarity Search Under Time Warping in Sequence Databases: An Index-based Approach,' Information Systems, Vol.29, No.5, pp.405-420, July 2004
Loh, W.-K., Kim, S-W., and Whang, K.-Y., 'Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases,' IEICE Transactions on Information and Systems, Vol.E84-D, No.1, pp.76-86, 2000
Loh, W.-K., Kim, S.-W., and Whang, K.-Y., 'A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases,' Data Mining and Knowledge Discovery, Vol.9, No.1, pp.5-28, July, 2004
Moon, Y.-S., Whang, K. Y., and Loh, W.-K., 'Duality-Based Subsequence Matching in Time-Series Databases,' In Proc. the 17th Int'l Conf. on Data Engineering (ICDE), IEEE, Heidelberg, Germany, pp.263-272, April, 2001
Moon, Y.-S., Whang, K. Y., and Han, W.-S., 'General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows,' In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, Madison, Wisconsin, pp.382-393, June, 2002
Oppenheim, A. V. and Schafer, R. W., Digital Signal Processing, Prentice-Hall, 1975
Park, S., Chu, W. W., Yoon, J., and Won, J., 'Similarity Search of Time-Warped Subsequences via a Suffix Tree,' Information Systems, Vol.28, No.7, pp.867-883, Oct., 2003
Rafiei, D., 'On Similarity-Based Queries for Time Series Data,' In Proc. the 15th Int'l Conf. on Data Engineering(ICDE), IEEE, Sydney, Australia, pp.410-417, Feb., 1999
Rafiei, D., and Mendelzon, A. O., 'Querying Time Series Data Based on Similarity,' IEEE Trans. on Knowledge and Data Engineering, Vol.12, No.5, pp.675-693, Sept./Oct., 2000
Wu, H., Salzberg, B., and Zhang, D., 'Online Event-driven Subsequence Matching Over Financial Data Streams,' In Proc. of Int'l Conf. on Management of Data, ACM SIGMOD, Paris, France, pp.23-34, June, 2004
Yi, B.-K., Jagadish, H. V., and Faloutsos, C., 'Efficient Retrieval of Similar Time Sequences Under Time Warping,' In Proc. the 14th Int'l Conf. on Data Engineering(ICDE), IEEE, Orlando, Florida, pp.201-208, Feb., 1998
※ AI-Helper는 부적절한 답변을 할 수 있습니다.