선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 그리고, 이동평균 변환 서브 시퀀스 매칭을 처음 제안한 Loh 등[기의 방법은 기존 다차원 색인의 구조와 알고리즘을 변경해야 하는 문제 점과 여러 색인에 따른 저장 공간 및 색인 관리의 오버 헤드가 발생하는 문제점이 있다. 반면에, 본 논문에서는 하나의 색인을 사용하면서도, 임의 계수에 대한 이동평균 변환 서브시퀀스 매칭을 효율적으로 수행하는 방법을 제안한다. 이를 위하여, 우선 윈도우를 여러 계수로 구성된 계수 집합에 대해서 이동평균 변환하는 다계수 이동평균 변한(poly-order moving average transform) 개념을 제시한다.
- 본 논문에서는 단일 색인을 사용하는 이동평균 변환 서브시퀀스 매칭 방법을 제안한다. 기존의 서브시퀀스 매칭 알고리즘[2, 8]은 이동평균 변환 서브시퀀스 매칭에 그대로 적용될 수 없다[7].
- 본 논문에서는 이동평균 변환을 서브시퀀스 매칭에 적용하는 유사 시퀀스 모델[기을 다룬다. 즉, 질의 시퀀 스와 데이타 서브시퀀스의 거리를 비교하는 것이 아니라, 이들을 주어친 계수 依세 의해 徉이동평균 변환한 이후의 두 시퀀스를 비교하여, 변환된 두 시퀀스가 매 치하는지의 여부를 판단하는 유사 시퀀스 모델을 다룬 다.
- 서브시퀀스 매칭은 전체 매칭을 일반화한 것으로, 보다 많은 응용 분야를 가진다[2-4, 6-8丄 그리 고, 유클리디안 거리 함수가 갖는 문제점을 보완하기 위 하여, 이동평균(moving average)[7, 9], 쉬프팅 및 스케 일링(shifting & scaling)[10-12], 정규화(normalization) [6, 9], 타임 워핑(time warping)[13-15] 등의 다양한 변 환 기법이 사용되었다. 본 논문에서는 이들 변환 중에서 이동평균 변환을 지원하는 서브시퀀스 매칭 문제를 다 룬다.
- 본 논문에서는 하나의 색인을 사용하여 색인 저장 공 간 및 관리의 오버헤드를 줄이면서도 임의 계수의 이동 평균 변환을 지원하는 서브시퀀스 매칭 방법을 제안하였다. 기존의 유클리디안 거리 기반의 서브시퀀스 매칭 알고리즘[2, 8]이나 임의 계수의 이동평균 변환 지원 전체 매칭 알고리즘[9]은 이동평균 변환 서브시퀀스 매칭 에 그대로 적용될 수 없는 문제점이 있다.
- 또한 Loh 둥 [기의 이동평균 변환 서브시퀀스 매칭 방법은 기존 다차 원 색인의 구조와 알고리즘을 변경해야 하는 문제점과 여러 색인 생성에 따른 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생하는 문제점이 있다. 이러한 문제점을 해결하기 위하여, 본 논문에서 우선 이동평균 변 환을 일반화하여 다계수 이동평균 변환의 개념을 제안 하였다. 그리고, 이러한 다계수 이동평균 변환을 사용하 면, 하나의 색인을 사용해서도 임의 계수에 대한 이동평균 변환 서브시퀀스 매칭을 효율적으로 수행할 수 있음을 보였다, 여기에서, 다계수 이동평균 변환이란, 각 윈 도우를 특정 계수에 대해서 이동평균 변환하는 것이 아 니라, 여러 계수에 대해서 이동평균 변환하여 윈도우의 집합을 구성하는 변환으로서, 단일 계수의 이동평균 변 환의 정의를 여러 계수로 구성되는 집합에 대해서 확장 한 것이다.
- 임의 계수 이동평균 변환을 FRM과 DualMatch와 같은 기존 서브시퀀스 매칭 방법에 적용하기 위하여, 본 논문에서는 다음 정의 1과 같이 k-이동평균 변환의 개 념을 확장한다.
제안 방법
- 실험 결과로는 각 방법의 실제 수행 시간을 측정하였다. 질의 시퀀스는 데이타 시퀀스의 임의 위치(random offset)를 시작 엔트리로 하는 S"Q) + kT 의 서브시 퀀스를 추출하여 /c-이동평균 변환한 시퀀스로 하였으며, 노이즈(noise) 효과를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다. 질의에 대한 선택률은 모든 가능한 데이타 서브시퀀스 개수에 대한 질의 결과 얻은 유사 서브시퀀스 개수의 비율로서, 다음 식 (8)과 같이 정의된다.
- 보조정리 1에 따라, FRMe 질의 시퀀스를 나눈 디스 조인트 윈도우를 戶차원의 점으로 변환하고, 이 점과 "行으로 범위 질의를 구성한다. 그리고, R*-트리를 검색하여 &/J方-매치하는 MBR들을 찾아내고, 이들 MBR이 나타내는 서브시퀀스들로 후보집합을 구성한다. 마지막으로, 후처리 과정을 통하여 착오해답을 제거하고 유사 서브시퀀스만을 찾는다.
- 다음으로, 이동평균 변환의 개념을 확장하여 다계수 이동평균 변환의 개 념을 정형적으로 정의하였다. 그리고, 다계수 이동평균 변환을 기존 서브시퀀스 매칭에 적용하는 이론적 근거 를 정리로서 제시하고 증명하였다. 또한, 다계수 이동평균 변환을 기존 서브시퀀스 매칭인 FRM과 DualMatch 에 적용하여, 새로운 이동평균 변환 서브시퀀스 매칭 알 고리즘인 FRM-MAT와 DM-MAT를 각각 제시하였다.
- 먼저, 실험 1)에서는 질의 시퀀스 길이를 고정하고, 여러 선택률에 대해 이동평균 계수를 달리하 면서 실험을 수행하였다. 그리고, 실험 2)에서는 선택률 을 고정하고, 여러 질의 시퀀스 길이에 대해 이동평균 계수를 달리하면서 실험을 수행하였다. 마지막으로, 실험 3)에서는 다차원 색인을 저장하는 색인 공간 측면에서 각 방법의 장단점을 비교한다.
- 다음으로, 제안한 다계수 이동 평균 변환 개념을 사용하면, 데이타 시퀀스를 디스조인 트 윈도우로 나누는 방법을 사용하는 DualMatch도 이 동평균 서브시퀀스 매칭 방법으로 확장될 수 있음을 보 인다. 그리고, 이들 FRM 및 DualMatch에 다계수 이동 평균 변환을 적용한 색인 구성 알고리즘과 서브시퀀스 매칭 알고리즘을 각각 제시한다. 성능 평가 결과, 제안한 두 가지 서브시퀀스 매칭 방법은 선택률의 범위 및 질의 시퀀스의 길이에 관계없이 모든 경우에 있어서 순 차 스캔보다 성능을 크게 향상시킨 것으로 나타났다.
- 우선, DualMatch에서는 윈도우 구성의 이원성 (duality) 개념을 제시하고, 이원성에 기반하여 데이타 시퀀스를 디스조인트 윈도우로 나누고 질의 시퀀스를 슬라이딩 윈도우로 나누는 FRM의 이원적 접근법을 제 안하였다. 다음으로, GeneralMatch에서는 FRM과 Dual- Match에서 사용한 슬라이딩 윈도우와 디스조인트 윈도 우를 일반화한 J-슬라이딩 윈도우와 J-디스조인트 윈도 우 개념을 제시하고, 이들 일반화된 윈도우를 사용한 서 브시퀀스 매칭 방법을 제안하였다. 이들 서브시퀀스 매 칭 방법의 색인 구성 및 서브시퀀스 매칭 알고리즘은 윈도우 구성을 달리하는 것을 제외하고는 FRM의 알고 리즘과 유사하다.
- 우선, 기존 연구들을 이동평균 변환 서브시퀀스 매칭에 적용 할 때 나타나는 문제점을 분석하였다. 다음으로, 이동평균 변환의 개념을 확장하여 다계수 이동평균 변환의 개 념을 정형적으로 정의하였다. 그리고, 다계수 이동평균 변환을 기존 서브시퀀스 매칭에 적용하는 이론적 근거 를 정리로서 제시하고 증명하였다.
- 보조정리 1을 사용할 경우, 색인 검색 범위가 司、而 으로 줄어들어 효과적인 서브시퀀스 매칭을 수행 할 수 있다. 따라서, 본 논문에서는 보조정리 1을 k-이 동평균 변환에 적용한 다음의 보조정리 2를 제시한다. 보조정리 2.
- 이러한 문제점을 해결하기 위하여, FRM에서는 여러 개의 슬라이딩 윈도우를 하나의 MBR에 포함시키는 방법을 사용하였다[2]. 따라서, 제안하는 FRM-MAT에서도 여러 개의 슬라이딩 윈도우가 변환된 여러 개의 MBR을 하나의 MBR에 포함시키는 방법을 사용한다. 즉, 연속 된 여러 슬라이딩 윈도우를 대표하는 MBR을 구성하고, 이 MBR을 첫번째 슬라이딩 윈도우의 시작 위치 및 마 지막 슬라이딩 윈도우 시작 위치와 함께 다차원 색인에 저장하는 방법을 사용한다.
- 즉, 하나의 윈도우가 각각의 계수에 따라서 여러 개의 윈도우들로 구성되는 집합으로 변환된다. 따라서, 제안하는 방법에서는 이들 윈도우들을 포함하는 MBR을 저차원 변환하예) 다차원 색인에 저장하는 방법을 사용한다. 그림 1은 다계수 이 동평균 변환 및 저차원 변환을 통하여 하나의 윈도우에 대해서 색인에 저장할 MBR이 구성되는 과정을 나타낸다.
- 그리고, 다계수 이동평균 변환을 기존 서브시퀀스 매칭에 적용하는 이론적 근거 를 정리로서 제시하고 증명하였다. 또한, 다계수 이동평균 변환을 기존 서브시퀀스 매칭인 FRM과 DualMatch 에 적용하여, 새로운 이동평균 변환 서브시퀀스 매칭 알 고리즘인 FRM-MAT와 DM-MAT를 각각 제시하였다. 마지막으로, 제안한 방법의 우수성을 데이타 종류, 선택률 범위, 질의 시퀀스 길이를 달리한 많은 실험을 통해 입증하였다.
- 본 절에서는 다섯 가지 방법에 대한 성능 평가 결과를 설명한다. 먼저, 실험 1)에서는 질의 시퀀스 길이를 고정하고, 여러 선택률에 대해 이동평균 계수를 달리하 면서 실험을 수행하였다. 그리고, 실험 2)에서는 선택률 을 고정하고, 여러 질의 시퀀스 길이에 대해 이동평균 계수를 달리하면서 실험을 수행하였다.
- 본 연구의 동기는 FRM과 DualMatch와 같은 기존 서브시퀀스 매칭에서 사용했던 보조정리 1의 수식 (2)를 이동평균 변환 서브시퀀스 매칭에 그대로 활용하자는데 있다. 보조정리 1을 사용할 경우, 색인 검색 범위가 司、而 으로 줄어들어 효과적인 서브시퀀스 매칭을 수행 할 수 있다.
- 본 장에서는 단일 색인을 사용하는 이동평균 변환 서 브시퀀스 매칭을 제안한다. 저)3.
- 본 절에서는 FRM의 서브시퀀스 매칭 방법에 다계수 이동평균 변환을 적용하여 임의 계수 이동평균 변환을 지원하는 서브시퀀스 매칭 방법을 설명한다. FRM에서 는 데이타 시퀀스를 슬라이딩 윈도우로 나누고, 질의 시 퀀스를 디스조인트 윈도우로 나누는 윈도우 구성법을 사용한다.
- 성능 평가를 위하여 순차 스캔, 제안한 방법 두 가지, 모든 계수에 대해 색인을 구성하는 방법 두 가지 등 총 다섯 가지 방법을 실험하였다.
- 실험 결과로는 각 방법의 실제 수행 시간을 측정하였다. 질의 시퀀스는 데이타 시퀀스의 임의 위치(random offset)를 시작 엔트리로 하는 S"Q) + kT 의 서브시 퀀스를 추출하여 /c-이동평균 변환한 시퀀스로 하였으며, 노이즈(noise) 효과를 피하기 위하여 같은 길이를 갖는 10개의 다른 질의 시퀀스에 대해서 실험한 후 평균을 취한 값을 실험 결과로 하였다.
- DualMatch[8]와 GeneralMatch[4]는 윈도우 구성법을 달리하여 FRM의 성능을 개선한 서브시퀀스 매칭 방법 들이다. 우선, DualMatch에서는 윈도우 구성의 이원성 (duality) 개념을 제시하고, 이원성에 기반하여 데이타 시퀀스를 디스조인트 윈도우로 나누고 질의 시퀀스를 슬라이딩 윈도우로 나누는 FRM의 이원적 접근법을 제 안하였다. 다음으로, GeneralMatch에서는 FRM과 Dual- Match에서 사용한 슬라이딩 윈도우와 디스조인트 윈도 우를 일반화한 J-슬라이딩 윈도우와 J-디스조인트 윈도 우 개념을 제시하고, 이들 일반화된 윈도우를 사용한 서 브시퀀스 매칭 방법을 제안하였다.
- 이동평균 변환 서브시퀀스 매칭 방법을 제안한다. 우선, FRM에서 취한 데이타 시퀀스를 슬라이딩 윈도우로 나 누는 방법에 다계수 이동평균 변환 개념을 적용하여 다 차원 색인을 구성하는 방법을 제안하고, 구성된 다차원 색인을 사용하여 이동평균 변환 서브시퀀스 매칭을 수 행하는 방법을 제안한다. 다음으로, 제안한 다계수 이동 평균 변환 개념을 사용하면, 데이타 시퀀스를 디스조인 트 윈도우로 나누는 방법을 사용하는 DualMatch도 이 동평균 서브시퀀스 매칭 방법으로 확장될 수 있음을 보 인다.
- 본 논문의 공헌은 다음과 같이 요약할 수 있다. 우선, 기존 연구들을 이동평균 변환 서브시퀀스 매칭에 적용 할 때 나타나는 문제점을 분석하였다. 다음으로, 이동평균 변환의 개념을 확장하여 다계수 이동평균 변환의 개 념을 정형적으로 정의하였다.
- 즉, 각각의 k에 대해서, 데이타 시퀀스들이 /c-이동평균 변환된 시퀀스들을 대상으로 별개의 다차원 색인을 구 성해야 한다. 이 방법은 기존 서브시퀀스 매칭 방법 [2, 4, 8]을 그대로 활용할 수 있어 구현이 용이하나, 모든 k에 대해서 별도의 다차원 색인을 구성해야 하므로, 색 인 공간의 오버헤드와 색인 관리의 오버헤드가 발생하는 문제점이 있다[7丄 이와 같은 문제점을 해결하기 위 하여, 본 논문에서는 하나의 색인을 사용하면서도 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 방법을 제안한다.
- 본 논문에서는 단일 색인을 사용하는 이동평균 변환 서브시퀀스 매칭 방법을 제안한다. 기존의 서브시퀀스 매칭 알고리즘[2, 8]은 이동평균 변환 서브시퀀스 매칭에 그대로 적용될 수 없다[7].
- 그런데, DM-MAT의 서브시퀀스 매칭 알고리즘에서는 질의 시 퀀스를 슬라이딩 윈도우로 나눔으로 인하여, 많은 질의 검색이 수행된다. 이러한 문제점을 해결하기 위하여 DualMatch에서와 같이, 실제로는 여러 개의 점을 포함 하는 질의 MBR을 구성하여 범위 질의의 횟수를 줄이는 방법을 사용한다그러나, 설명의 편의상, 본 논문에서는 각 점으로 직접 질의하는 것으로 기술한다.
- 반면에, 본 논문에서는 하나의 색인을 사용하면서도, 임의 계수에 대한 이동평균 변환 서브시퀀스 매칭을 효율적으로 수행하는 방법을 제안한다. 이를 위하여, 우선 윈도우를 여러 계수로 구성된 계수 집합에 대해서 이동평균 변환하는 다계수 이동평균 변한(poly-order moving average transform) 개념을 제시한다. 다계수 이동평균 변환이란, 각 윈도우를 특정 계수에 대해서 이동평균 변환하는 것이 아니라, 여러 계수에 대해서 이동평균 변환하여 윈도우 의 집합을 구성하는 변환을 의미한다.
- 즉, 계수 집합 K={2, 4, 8, 16, 32, 64, 128}로 하였다. 이에 따라, FRM-MAT 및 DM-MAT에서는 계수 집합 K 에 대해서 하나의 다차원 색인을 구성하였으며, FRM-ORG 및 DM-ORG 에서는 집합 K 의 모든 원소인 일곱 개의 계수에 대해서 각각 다차원 색인을 구성하였다.
- 제안한 방법의 우수성을 입증하기 위하여 두 가지 종 류의 데이타를 사용하여 많은 실험을 수행하였다. 사용한 데이타는 하나의 긴 데이타 시퀀스로 구성된 것으로서, 이는 여러 개의 데이타 시퀀스로 구성된 경우와 동일한 효과를 가진다[2, 8].
- 본 논문에서 제안한 이동평균 변환 서브시퀀스 매칭 은 정규화 변환, 스케일링 및 쉬프팅 등 다른 변환을 지 원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 즉, 기존의 방법들이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도 우에 대해서 확장된 혹은 일반화된 변환의 개념을 도입 하고 이를 서브시퀀스 매칭에 활용한다. 따라서, 제안한 방법은 이동평균 변환을 포함하는 많은 다른 종류의 변 환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있을 것으로 사료된다.
- 그러나, Rafiei 등은 임의 계수의 이동평균 변환을 지원하기 위하여, 전통 적인 이동평균 변환 정의가 아닌 다른 정의를 사용하였다. 즉, 길이 n인 시퀀스를 이동평균 변환할 때, k-이동 평균 값을 구할 수 없는 마지막 (k-1)개의 데이타 값들 에 대해서 부족한 (/L1)개의 값들을 시퀀스의 맨 앞에서 가져와 순환적(circular)으로 灯이동평균 값들을 구 하였다. 이와 같이, 전통적인 이동평균의 정의를 사용하 지 않음으로써, Rafiei 등의 전체 매칭 연구는 서브시퀀 스 매칭에 그대로 적용될 수 없다[7].
- 따라서, 제안하는 FRM-MAT에서도 여러 개의 슬라이딩 윈도우가 변환된 여러 개의 MBR을 하나의 MBR에 포함시키는 방법을 사용한다. 즉, 연속 된 여러 슬라이딩 윈도우를 대표하는 MBR을 구성하고, 이 MBR을 첫번째 슬라이딩 윈도우의 시작 위치 및 마 지막 슬라이딩 윈도우 시작 위치와 함께 다차원 색인에 저장하는 방법을 사용한다. 그러나, 설명의 편의상, 본 논문에서는 그림 2와 같이 각 슬라이딩 윈도우에 해당하는 MBR을 직접 저장하고 서브시퀀스 매칭을 수행하는 것으로 기술한다.
- 본 논문에서는 이동평균 변환을 서브시퀀스 매칭에 적용하는 유사 시퀀스 모델[기을 다룬다. 즉, 질의 시퀀 스와 데이타 서브시퀀스의 거리를 비교하는 것이 아니라, 이들을 주어친 계수 依세 의해 徉이동평균 변환한 이후의 두 시퀀스를 비교하여, 변환된 두 시퀀스가 매 치하는지의 여부를 판단하는 유사 시퀀스 모델을 다룬 다. 이와 같이 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 방법을 본 논문에서는 간략히 이동평균 변환 서브시퀀스 매칭이라 부른다.
대상 데이터
- 또한, 최소 질의 시퀀스 길이로 256을 사용하여, FRM-MAT 및 FRM-ORG의 윈도우 크기는 최소 질의 시퀀스 길이와 같은 256을 사용하고, DM-MAT와 DM-ORG는 FRM의 절반인 128을 사용 하였다[8]. 그리고, 실험에 사용한 이동평균 계수는 2, 4, 8, 16, 32, 64, 128을 사용하였다. 즉, 계수 집합 K={2, 4, 8, 16, 32, 64, 128}로 하였다.
- 6 운영 체제이다. 다차원 색인으로는 모두 R*-트리[18]를 사용하였으며, 데이타 페이지 및 색인 페이지의 크기는 4096 바이트를 사용하였다. 그리고, 특성 추출 함수로는 DFT 변환[2이을 사용하였으며, 특성 은 6개3)를 사용하였다.
성능/효과
- 0배 성능을 향상시킨 것으로 나타났다. 그리고, FRM-ORG 및 DM-ORG에 대한 FRM-MAT 및 DM-MAT의 성 능 저하는 각각 평균 7% 및 27%에 불과한 것으로 나타났다.
- 이러한 문제점을 해결하기 위하여, 본 논문에서 우선 이동평균 변 환을 일반화하여 다계수 이동평균 변환의 개념을 제안 하였다. 그리고, 이러한 다계수 이동평균 변환을 사용하 면, 하나의 색인을 사용해서도 임의 계수에 대한 이동평균 변환 서브시퀀스 매칭을 효율적으로 수행할 수 있음을 보였다, 여기에서, 다계수 이동평균 변환이란, 각 윈 도우를 특정 계수에 대해서 이동평균 변환하는 것이 아 니라, 여러 계수에 대해서 이동평균 변환하여 윈도우의 집합을 구성하는 변환으로서, 단일 계수의 이동평균 변 환의 정의를 여러 계수로 구성되는 집합에 대해서 확장 한 것이다.
- 그림에서 보면, 제안한 FRM-MAT와 DM-MAT는 선택률에 관계없이 순차 스캔에 비하여 수행 시간을 크게 줄였음을 알 수 있다. 그림 6의 STOCK-DATA에 대한 실험결과를 요약하면, FRM-MAT는 순차 스캔에 비하여 평균 22.4 배 성능을 향상시키고, DM-MAT는 순차 스캔에 비하여 평균 33.8배 성능을 향상시킨 것으로 나타났다. 반면 에, FRM-MAT 및 DM-MAT는 모든 계수에 대해 색 인을 구성하는 FRM-ORG 및 DM-ORG에 비해서는 평균 9% 및 42%까지 각각 성능이 저하되었다.
- 그림을 보면, WALK-DATA의 경우도 STOCK-DATA와 마찬가지 로, 제안한 FRM-MAT 및 DM-MAT의 성능이 순차 스캔에 비하여 크게 향상되었음을 알 수 있다. 그림 7의 WALK-DATA에 대한 실험결과를 요약하면, FRM- MAT는 순차 스캔에 비하여 평균 17.8배 성능을 향상 시키고, DM-MAT는 순차 스캔에 비하여 평균 22.0배 성능을 향상시킨 것으로 나타났다. 그리고, FRM-ORG 및 DM-ORG에 대한 FRM-MAT 및 DM-MAT의 성 능 저하는 각각 평균 7% 및 27%에 불과한 것으로 나타났다.
- 01 인 경우이다. 그림에서 보면, 제안한 FRM-MAT와 DM-MAT는 선택률에 관계없이 순차 스캔에 비하여 수행 시간을 크게 줄였음을 알 수 있다. 그림 6의 STOCK-DATA에 대한 실험결과를 요약하면, FRM-MAT는 순차 스캔에 비하여 평균 22.
- 다음으로, 그림 7은 WALK-DATA에 대해 질의 시 퀀스 길이를 512로 고정하고, 각 선택률에 대해 계수를 달리하면서 수행 시간을 측정한 결과이다. 그림을 보면, WALK-DATA의 경우도 STOCK-DATA와 마찬가지 로, 제안한 FRM-MAT 및 DM-MAT의 성능이 순차 스캔에 비하여 크게 향상되었음을 알 수 있다. 그림 7의 WALK-DATA에 대한 실험결과를 요약하면, FRM- MAT는 순차 스캔에 비하여 평균 17.
- 우선, FRM에서 취한 데이타 시퀀스를 슬라이딩 윈도우로 나 누는 방법에 다계수 이동평균 변환 개념을 적용하여 다 차원 색인을 구성하는 방법을 제안하고, 구성된 다차원 색인을 사용하여 이동평균 변환 서브시퀀스 매칭을 수 행하는 방법을 제안한다. 다음으로, 제안한 다계수 이동 평균 변환 개념을 사용하면, 데이타 시퀀스를 디스조인 트 윈도우로 나누는 방법을 사용하는 DualMatch도 이 동평균 서브시퀀스 매칭 방법으로 확장될 수 있음을 보 인다. 그리고, 이들 FRM 및 DualMatch에 다계수 이동 평균 변환을 적용한 색인 구성 알고리즘과 서브시퀀스 매칭 알고리즘을 각각 제시한다.
- 본 논문에서는 다계수 이동평균 변환 을 사용하여 다차원 색인을 구성하면, 하나의 색인을 사 용해서도 이동평균 변환 서브시퀀스 매칭을 수행할 수 있음을 보인다. 또한, 다계수 이동평균 변환을 사용하면, 기존 서브시퀀스 매칭에서 사용하였던 이론을 그대로 이동평균 변환 서브시퀀스 매칭에 적용할 수 있음을 정 리로서 제시하고 증명한다.
- 8배까지 크게 향상시킨 것으로 나타났다. 또한, 이동평균 변환의 각 계수에 대해 모두 색인을 생성한 경우에 비해서 성능 저하는 매우 적은 반면에, 필요한 색인 공간은 크게 줄 인 것으로 나타났다(일곱 개의 계수를 사용한 경우, 성 능 저하는 평균 9%~42%에 불과한 반면 색인 공간은 약 1/7.0로 크게 줄인다).
- 또한, 다계수 이동평균 변환을 기존 서브시퀀스 매칭인 FRM과 DualMatch 에 적용하여, 새로운 이동평균 변환 서브시퀀스 매칭 알 고리즘인 FRM-MAT와 DM-MAT를 각각 제시하였다. 마지막으로, 제안한 방법의 우수성을 데이타 종류, 선택률 범위, 질의 시퀀스 길이를 달리한 많은 실험을 통해 입증하였다. 실제 주식 데이타에 대한 실험 결과, 제안한 방법은 순차 스캔에 비해서 평균 22.
- 8배 성능을 향상시킨 것으로 나타났다. 반면 에, FRM-MAT 및 DM-MAT는 모든 계수에 대해 색 인을 구성하는 FRM-ORG 및 DM-ORG에 비해서는 평균 9% 및 42%까지 각각 성능이 저하되었다. 그 이유는 색인에 저장하는 MBR 크기 측면에서 볼 때, 하나의 색인에서 모든 계수를 고려하는 FRM-MAT 및 DM- MAT의 경우가 하나의 색인에서 하나의 계수만을 고려 하는 FRM-ORG 및 DM-ORG의 경우에 비하여 크기 때문이다.
- 본 논문에서 제안한 이동평균 변환 서브시퀀스 매칭 은 정규화 변환, 스케일링 및 쉬프팅 등 다른 변환을 지 원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 즉, 기존의 방법들이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도 우에 대해서 확장된 혹은 일반화된 변환의 개념을 도입 하고 이를 서브시퀀스 매칭에 활용한다.
- 이러한 다계수 이 동평균 변환을 사용하는 이유는 이동평균 변환에 사용되는 계수 값이 다르더라도, 각 계수에 따라 변환된 윈 도우들은 유사한 엔트리 값을 가지는 이동평균 변환의 정의에 기반한다. 본 논문에서는 다계수 이동평균 변환 을 사용하여 다차원 색인을 구성하면, 하나의 색인을 사 용해서도 이동평균 변환 서브시퀀스 매칭을 수행할 수 있음을 보인다. 또한, 다계수 이동평균 변환을 사용하면, 기존 서브시퀀스 매칭에서 사용하였던 이론을 그대로 이동평균 변환 서브시퀀스 매칭에 적용할 수 있음을 정 리로서 제시하고 증명한다.
- 그리고, 이들 FRM 및 DualMatch에 다계수 이동 평균 변환을 적용한 색인 구성 알고리즘과 서브시퀀스 매칭 알고리즘을 각각 제시한다. 성능 평가 결과, 제안한 두 가지 서브시퀀스 매칭 방법은 선택률의 범위 및 질의 시퀀스의 길이에 관계없이 모든 경우에 있어서 순 차 스캔보다 성능을 크게 향상시킨 것으로 나타났다. 실제 주식 데이타에 대한 실험 결과, 제안한 방법은 순차 스캔에 비해 성능을 평균 22.
- 성능 평가 결과, 제안한 두 가지 서브시퀀스 매칭 방법은 선택률의 범위 및 질의 시퀀스의 길이에 관계없이 모든 경우에 있어서 순 차 스캔보다 성능을 크게 향상시킨 것으로 나타났다. 실제 주식 데이타에 대한 실험 결과, 제안한 방법은 순차 스캔에 비해 성능을 평균 22.4배에서 33.8배까지 크게 향상시킨 것으로 나타났다. 또한, 이동평균 변환의 각 계수에 대해 모두 색인을 생성한 경우에 비해서 성능 저하는 매우 적은 반면에, 필요한 색인 공간은 크게 줄 인 것으로 나타났다(일곱 개의 계수를 사용한 경우, 성 능 저하는 평균 9%~42%에 불과한 반면 색인 공간은 약 1/7.
- 마지막으로, 제안한 방법의 우수성을 데이타 종류, 선택률 범위, 질의 시퀀스 길이를 달리한 많은 실험을 통해 입증하였다. 실제 주식 데이타에 대한 실험 결과, 제안한 방법은 순차 스캔에 비해서 평균 22.4배~33.8배 까지 크게 성능을 향상 시킨 것으로 나타났다. 또한, 이 동평균 변환의 각 계수에 대해 모두 색인을 생성한 경우와 비교했을 때, 성능 저하는 매우 적은 반면에, 필요한 색인 공간은 크게 줄인 것으로 나타났다(일곱 개의 계수를 사용한 경우, 성능 저하는 평균 9%~42%에 불 과한 반면 색인 공간은 약 1/7.
- 그림 8과 9를 보면, 제안한 FRM-MAT와 DM- MAT는 질의 시퀀스의 길이에 관계없이 순차 스 캔에 비하여 수행 시간을 크게 줄였음을 알 수 있다. 이들 실험결과를 요약하면, 제안한 FRM-MAT 및 DM- MAT는 순차 스캔에 비해서 평균 08배~42.6배 이상 성능올 크게 향상시킨 것으로 나타났으며, FRM-ORG 및 DM-ORG에 대한 성능 저하는 평균 6%-98% 이하 에 불과한 것으로 나타났다.
후속연구
- 즉, 기존의 방법들이 새로운 검색 범위를 찾거나 여러 색인을 사용하여 문제를 해결한 반면에, 제안한 방법은 각 윈도 우에 대해서 확장된 혹은 일반화된 변환의 개념을 도입 하고 이를 서브시퀀스 매칭에 활용한다. 따라서, 제안한 방법은 이동평균 변환을 포함하는 많은 다른 종류의 변 환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있을 것으로 사료된다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.