선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 분석한다. 또한, 이 분석 결과를 토대로 전체 서브 시퀀스 매칭의 처리 성능을 개선시키기 위한 향후의 연구 방향을 제시하고자 한다.
- 본 논문에서 해결하고자 하는 문제는 공식 (3)의 비용 T 를 최소로 하는 윈도우 크기 리스트 W= 를 효과적으로 구하는 것이다.
- 그러나 모드 가능한 윈도우 크기 리스트의 수는 개 이므로 이러한 방식의 알고리즘은。((4严)의 지수적 시간 복잡도를 가지게 된다. 본 논문에서는 os叽2)의 시간 복잡도를 갖는 알고리즘을 제시한다. 먼저 歸 4개의 모든 가능한 윈도우 크기 리스트를 고려할 필요 없이 湛%개의 윈도우 크기 리스트만 고려하면 최적의 윈도우 크기 리스트를 찾을 수 있음을 보이고 개의 윈도우 크기 리스트에서 0(mn2) 시간에 최적의 윈도우크기 리스트를 찾는 알고리즘을 소개한다
- 본 논문에서는 기존의 기법에서 윈도우 크기 효과에 의하여 검색 성능이 저하되는 문제점을 해결하고자 인덱스 보간법 [18]에 기반한 새로운 서브시퀀스 매칭 기법을 제안하였다. 인덱스 보간법이란 하나 이상의 인덱스를 구축하고, 주어진 질의 시퀀스의 길이에 따라 하나의 적절한 인덱스를 선택하여 검색을 수행함으로써 서브 시퀀스 매칭 성능을 향상시키는 기법이다.
- 본 논문에서는 다양한 실험을 통하여 윈도우 크기 효과가 전체 서브시퀀스 매칭에 미치는 영향을 정량적으로 분석한다. 또한, 이 분석 결과를 토대로 전체 서브 시퀀스 매칭의 처리 성능을 개선시키기 위한 향후의 연구 방향을 제시하고자 한다.
- 본 논문에서는 이러한 문제점을 해결하고자 인덱스보간법(index interpolation)[18]에 기반한 새로운 서브 시퀀스 매칭 기법을 제안한다. 인덱스 보간법이란 둘 이상의 인덱스를 구축하고 주어진 질의 시퀀스의 길이에 따라 하나의 적절한 인덱스를 선택하여 서브시퀀스 매칭을 수행하는 기법이다.
- 인덱스 관리비용은 인덱스를 저장하기 위한 물리적 공간뿐만 아니라, 데이타가 삽입, 삭제, 갱신될 때마다 해당 인덱스를 그에 따라 모두 변경하는 비용을 포함한다. 본 논문에서는 인덱스 보간법에서 최적의 검색 성능을 지원할 수 있는 가능한한 적은 수의 인덱스들을 선택하여 구성하는 방안에 대하여 논의한다.
- 인덱스 보간법을 응용하여 서브시퀀스 매칭을 수행하기 위해서는 먼저 다수의 인덱스들을 위한 윈도우 크기들을 결정해야 한다. 본 연구에서는 물리적 데이타베이스 설계 방식을 이용하여 이러한 최적의 다수의윈도우 크기들을 선정하는 문제를 해결하였다. 이를 위하여 시계열 데이타베이스에서 수행될 예정인 질의 시퀀스들의 집합과 인덱스 구성의 기반이 되는 윈도우들의 크기의 집합이 주어질 때, 전체 서브시퀀스 매칭들을 수행하는 데에 소요되는 비용을 예측할 수 있는 공식을 산출하였다.
가설 설정
- 또한, 이러한 질의 시퀀스 길이의 리스트와 빈도수 리스트를 각각 L=로 표기한다, 여기서 기은 질의 시퀀스 길이의 종류를 의미하며, 4V4의 관계가 성립한다고 가정한다.
-
응용에서 인덱스 보간법을 이용하여 구성한 以개의 인덱스에 사용된 윈도우 크기 리스트를 归=로 정의하며, 이 때에 wr
제안 방법
- 이러한 인덱스 검색 단계의 결과, 질의 시퀀스와 £-매치 할 가능성이 높은 많은 후보 서브시퀀스(candidate subsequence)들이 반환된다. 그 다음, 착오 채택(false alarm)[l, 4]을 해결하기 위하여 이 후보 서브시퀀스들을 포함하는 각 시퀀스를 디스크로부터 액세스하여 후보 서브시퀀스갸 질의 시퀀스와 실제로 "매치 하는가의 여부를 판단한다. 본 논문에서는 이 과정을 후처리 .
- "제안된 기법은 응용에서 사용될 질의 시퀀스들에 대한 정보로서의 쌍과 응용에서 구성할 인덱스의 개수 m을 입력으로 받아 서브시퀀스 매칭을 최적으로 처리할 수 있는 인덱스들을 구성할 수 있도록 윈도우크기 叫, 沔, …""%를 결정한다."
- .데이타베이스에서 수행될 예정인 질의 시퀀스들의 집합이 주어지고, 인덱스 구성의 기반이 되는 윈도우들의 크기들이 결정되었을 때, 전체 서브시퀀스 매칭들을 수행하는 데에 소요되는 비용을 예측할 수 있는 공식을 산출하였다.
- .수행 비용 공식을 이용하여 서브시퀀스 매칭의 성능을 극대화 할 수 있도록 최적의 윈도우 크기들을 결정하는 효율적인 알고리즘을 제안하였다.
- 첫번째 실험에서 사용된 윈도우 크기는 w = 64이며, 질의 시퀀스의 길이는 Len(Q) = 64, 128, 256, 512, 1024이다. 두번째 실험은 첫 번째 실험과 반대로 고정된 길이의 질의 시퀀스에 대하여 다양한 크기의 윈도우들로 구성된 각각의 인덱스를 이용하여 서브시퀀스 매칭을 수행함으로써 윈도우의 크기에 따른 검색 성능 변화를 살펴본다. 두번째 실험에서 사용된 질의 시퀀스 길이는 Len(Q) 二 1024이며, 윈도우의길이는 w = 64, 128, 256, 512, 1024이다.
- 이를 위하여 시계열 데이타베이스에서 수행될 예정인 질의 시퀀스들의 집합과 인덱스 구성의 기반이 되는 윈도우들의 크기의 집합이 주어질 때, 전체 서브시퀀스 매칭들을 수행하는 데에 소요되는 비용을 예측할 수 있는 공식을 산출하였다. 또한, 이 비용 공식을 이용하여 전체 서브 시퀀스 매칭들의 성능을 극대화 할 수 있는 최적의 윈도우 크기들을 결정하는 알고리즘을 제안하였으며, 이 알고리즘의 최적성과 효율성을 이론적으로 규명하였다. 끝으로, 제안된 기법이 기존의 단순한 기법과 비교하여 상당한 성능 개선 효과가 있음을 다양한 실험을 통해서 검증하였다.
- 본 논문에서는 os叽2)의 시간 복잡도를 갖는 알고리즘을 제시한다. 먼저 歸 4개의 모든 가능한 윈도우 크기 리스트를 고려할 필요 없이 湛%개의 윈도우 크기 리스트만 고려하면 최적의 윈도우 크기 리스트를 찾을 수 있음을 보이고 개의 윈도우 크기 리스트에서 0(mn2) 시간에 최적의 윈도우크기 리스트를 찾는 알고리즘을 소개한다
- 먼저, 인덱스 구성을 위하여 각 시퀀스로부터 길이 w 의 윈도우들을 추출하고, 각 윈도우를 이산 퓨리에 변환 (discrete Fourier transform- DFT) 혹은 웨이블릿 변환(wavelet transform)-^- 이용하여 저차원 f-공간(f << w) 상의 윈도우 점(window poinlj으로 변환한다. 효과적인 서브시퀀스 매칭을 위하여 이러한 윈도우 점들을 다차원 인덱스(multidimensional index) 의 하나인 R*-트리 U기에 저장한다.
- 제안된 기법은 응용에서 사용될 질의 시퀀스들에 대한 정보로서<길이, 빈도>의 쌍과 응용에서 구성할 인덱스의 개수 m을 입력으로 받아 서브시퀀스 매칭을 최적으로 처리할 수 있는 인덱스들을 구성할 수 있도록 윈도우크기 叫, 沔, …"%를 결정한다. 먼저, 전체 서브 시퀀스 매칭 처리를 위한 비용 공식을 도출하고, 그 공식에 기반하여 전체 질의 시퀀스들을 대상으로 최적의 서브 시퀀스 매칭 수행을 위한 윈도우 크기를 선정하는 알고리즘을 제시한다.
- 그러나 이러한 방식의 알고리즘은。(?舟)의 시간 복잡도를 가지게 된다. 본 논문에서 제시하는 C火m展) 시간 복잡도 알고리즘의 기본 아이디어는 다이나믹 프로그래밍 기법을 이용하여 부분 질의 시퀀스 길이 리스트들에 대해서 최소 실행 비용을 먼저 구하고 그 결과를 이용하여 전체 질의 시퀀스 길이 리스트들에 대해서 최소 실행 비용을 구하는 것이다.
- 8 GHz Pentium 4 프로세서에 512 MB의 메모리를 장착한 PC와 MS Windows 2000 운영 체제를 사용하였다. 본 실험에서는 일정한 실험 결과를 얻기 위하여 운영 체제에서 제공하는 버퍼링 (buffering) 기능을 사용하지 않고 바로 디스크를 액세스하는 시스템 I/O 함수를 이용하였다. 또한, 다차원 인덱스로는 1KB 크기의 페이지를 갖는 R*- 트리[1 기를 사용하였다.
- 본 실험에서의 성능 평가의 대상으로 선정한 서브 시퀀스 매칭 기법은 단일 인덱스만을'이용하는 기존의 기법(A), 최소 질의 시퀀스 길이와 최대 시퀀스 길이 범위내에서 균등한 간격으로 윈도우 크기를 설정하여 구성한 다중 인덱스들을 이용하는 기법 (B), 본 논문에서 제안한 기법으로 생성한 다중 인덱스들을 이용하는 기법 (C) 등 세가지이다.
- 본 장에서는 서브시퀀스 매칭 수행 시에 윈도우 크기효과에 의한 성능 저하를 극복하기 위한 방법으로 인덱스 보간법(index interpolation)[18]을 이용하는 새로운 기법을 제안한다. 인덱스 보간법은 먼저 서로 다른 크기의 윈도우들을 대상으로 다수의 인덱스들을 구축한 후, 서브시퀀스 매칭시 주어진 질의 시퀀스의 길이에 가장 적합한 하나의 인덱스를 인덱스 검색 단계에서 사용하는 기법이다.
- 범위 질의를 구성한다. 사전에 구성된 R* -트리에 대하여 이 범위 질의를 처리하는 인덱스 검색 단계 (index search step)를 수행한다. 인덱스 검색 단계의결과, 질의 점과 유클리드 거리가 e 이하인 모든 데이타점들과 대응되는 데이타 시퀀스들을 반환하는데, 이들을 후보 집합(candidate set) 이라 한다.
- 성능 지수로는 검색에 소요된 실행 시간을 사용하였으며, 두 가지 사전 실험 모두에 대하여 허용치 £은 최종 질의 결과로서 20 개의 서브시퀀스들을 반환하도록 조정하였다.
- 4개의 그룹내의 질의 시퀀스들이 빈번하게 사용되고, 16개 그룹내의 질의 시퀀스들은 사용이 빈번하지 않음을 의미한다. 성능 평가지수로서 전체 그룹내의 총 216개의 질의 시퀀스를 대상으로 서브시퀀스 매칭을 수행하는 데에 걸린 실행 시간의 평균을 사용하였다. 각 질의 시퀀스에 대한 허용치 e 은 서브시퀀스 매칭의 결과로 20 개의 서브시퀀스를 반환하도록 조정하였다.
- 시퀀스와 데이타 시퀀스들을 대상으로 하는 서브시퀀스 매칭 방법 FRM을 제안하였다. FRMe 전체 매칭 기법의 기본 아이디어를 확장한 것으로서, R*- 트리 인덱싱을 위하여 고정된 길이 w를 갖는 윈도우(window) 개념을 이용한다.
- 본 논문에서는 세 가지 실험을 수행한다. 실험 1에서는 실제 데이타를 이용하여 인덱스의 개수를 변경하며 세 가지 기법들간의 성능을 비교한다. 실험 2에서는 합성데이타를 이용하여 데이타 시퀀스의 개수를 변경하면서 세 가지 기법들간의 성능을 비교한다.
- 실험 2에서는 1024의 길이를 갖는 합성 데이타를 2000, 3000, 4000, 5000 개로 개수를 증가시키면서, 세 가지 기법의 성능의 변화를 관찰하였다. 기법(B)와 기법 (C)에서는 각각 4개의 다중 인덱스를 사용하도록 설정하였다.
- 실험 1에서는 실제 데이타를 이용하여 인덱스의 개수를 변경하며 세 가지 기법들간의 성능을 비교한다. 실험 2에서는 합성데이타를 이용하여 데이타 시퀀스의 개수를 변경하면서 세 가지 기법들간의 성능을 비교한다. 실험 3에서는 합성데이타를 이용하여 데이타 시퀀스의 길이를 변경하며 세 가지 기법들간의 성능을 비교한다.
- 실험 3에서는 2000, 3000, 4000, 5000의 길이를 갖는 1000개의 합성 데이타를 대상으로 세가지 기법의 성능의 변화를 관찰하였다. 실험 2에서와 마찬가지로, 기법 (B)와 기법(C)에서는 각각 4개의 다중 인덱스를 사용하도록 설정하였다.
- 실험 2에서는 합성데이타를 이용하여 데이타 시퀀스의 개수를 변경하면서 세 가지 기법들간의 성능을 비교한다. 실험 3에서는 합성데이타를 이용하여 데이타 시퀀스의 길이를 변경하며 세 가지 기법들간의 성능을 비교한다.
- 본 연구에서는 물리적 데이타베이스 설계 방식을 이용하여 이러한 최적의 다수의윈도우 크기들을 선정하는 문제를 해결하였다. 이를 위하여 시계열 데이타베이스에서 수행될 예정인 질의 시퀀스들의 집합과 인덱스 구성의 기반이 되는 윈도우들의 크기의 집합이 주어질 때, 전체 서브시퀀스 매칭들을 수행하는 데에 소요되는 비용을 예측할 수 있는 공식을 산출하였다. 또한, 이 비용 공식을 이용하여 전체 서브 시퀀스 매칭들의 성능을 극대화 할 수 있는 최적의 윈도우 크기들을 결정하는 알고리즘을 제안하였으며, 이 알고리즘의 최적성과 효율성을 이론적으로 규명하였다.
- 전체 매칭을 위하여 길이가 1인 질의 시퀀스를 위와 동일한 방법으로 저차원 卜공간상의한 점으로 변환하고, 변환한 질의 점을 중심점, 허용치 £을 범위로 사용하는 범위 질의를 구성한다. 사전에 구성된 R* -트리에 대하여 이 범위 질의를 처리하는 인덱스 검색 단계 (index search step)를 수행한다.
- 선정 방안에 관하여 논의한다. 제4」절에서는 여러 개의 윈도우 크기가 주어졌을 때 주어진 질의 시퀀스의 길이에 가장 적합한 하나의 윈도우를 선택하는 방법에 대해서 설명하고 제4.2절에서는 여러 개의 질의 시퀀스의 길이와 빈도수가 주어졌을 때 서브시퀀스 매칭의 처리 비용 공식을 제안하고, 이 공식을 기반으로 최적의윈도우 크기들을 선정하는 알고리즘을 제안한다.
- 질의 시퀀스는 임의로 선택된 데이타 시퀀스 내의 임의위치로부터 서브시퀀스를 추출하여 각 요소 값에 적절한 범위 내의 임의의 값을 더하는 방식으로 변형하여 생성하였다. 하드웨어 및 소프트웨어 환경, 데이타 시퀀스의 윈도우 분할 및 저차원 변환 R*- 트리의 구성 둥에 대해서는 성능 평가 실험을 다루는 저】5장에서 구체적으로 설명한다.
- 첫 번째 실험은 고정된 크기의 윈도우로 구성된 하나의 인덱스를 이용하여 여러가지 길이의 질의 시퀀스들에 대한 서브 시퀀스 매칭을 수행하여 질의 시퀀스의 길이에 따른 성능 변화를 살펴본다. 첫번째 실험에서 사용된 윈도우 크기는 w = 64이며, 질의 시퀀스의 길이는 Len(Q) = 64, 128, 256, 512, 1024이다.
대상 데이터
- 인덱스만을 사용하였으며, 기법 .(B)에서는 크기가 일정한 간격으로 설정된 각각 3, 4, 5가지의 윈도우들을대상으로하는 다중 인덱스를 사용하였고, 기법 (C) 에서는 본 논문에서 제안한 알고리즘으로 선택된 3, 4, 5가지의 윈도우들을 대상으로하는 다중 인덱스를 사용하였다.
- 1] 사이에서 균일한 분포를 취하는 랜덤 변수이며, ■시퀀스의 첫 요소 값 sie 구간 [1, 10] 사이의 임의의 값을 취하도록 하였다. 다양한 환경에 대한 실험을 위하여 각각 2,000개, 3, 000개, 4, 000 개, 5,000개의 길이가 1, 024인 데이타 시퀀스들로 구성된 다섯 가지 Syn_Data들과 길이가 각각 2,000, 3, 000, 4, 000, 5,000인 1,000개의 데이타 시퀀스들로 구성된 다섯 가지 Syn_Data들을 생성하였다.3)
- 두번째 실험은 첫 번째 실험과 반대로 고정된 길이의 질의 시퀀스에 대하여 다양한 크기의 윈도우들로 구성된 각각의 인덱스를 이용하여 서브시퀀스 매칭을 수행함으로써 윈도우의 크기에 따른 검색 성능 변화를 살펴본다. 두번째 실험에서 사용된 질의 시퀀스 길이는 Len(Q) 二 1024이며, 윈도우의길이는 w = 64, 128, 256, 512, 1024이다.
- 실제 응용 분야에서 널리 사용된다. 따라서 본 논문은 이러한 서브시퀀스 매칭을 연구의 대상으로 한다.
- 본 실험에서는 일정한 실험 결과를 얻기 위하여 운영 체제에서 제공하는 버퍼링 (buffering) 기능을 사용하지 않고 바로 디스크를 액세스하는 시스템 I/O 함수를 이용하였다. 또한, 다차원 인덱스로는 1KB 크기의 페이지를 갖는 R*- 트리[1 기를 사용하였다. 인덱싱을 위한 저차원 변환은 DFT를 통하여 수행하였으며, 특성 추출 계수 f=6으로 하였다.
- 사전 실험에서 사용된 데이타는 길이가 1024인 620 개의 한국의 실제 주식 데이타 시퀀스를 사용하였다. 질의 시퀀스는 임의로 선택된 데이타 시퀀스 내의 임의위치로부터 서브시퀀스를 추출하여 각 요소 값에 적절한 범위 내의 임의의 값을 더하는 방식으로 변형하여 생성하였다.
- 실험 1에서 기법(A)는 w=32인 윈도우를 대상으로 하나의 인덱스만을 사용하였으며, 기법 .(B)에서는 크기가 일정한 간격으로 설정된 각각 3, 4, 5가지의 윈도우들을대상으로하는 다중 인덱스를 사용하였고, 기법 (C) 에서는 본 논문에서 제안한 알고리즘으로 선택된 3, 4, 5가지의 윈도우들을 대상으로하는 다중 인덱스를 사용하였다.
- 실험을 위한 환경으로는 2.8 GHz Pentium 4 프로세서에 512 MB의 메모리를 장착한 PC와 MS Windows 2000 운영 체제를 사용하였다. 본 실험에서는 일정한 실험 결과를 얻기 위하여 운영 체제에서 제공하는 버퍼링 (buffering) 기능을 사용하지 않고 바로 디스크를 액세스하는 시스템 I/O 함수를 이용하였다.
- 첫 번째 실험은 고정된 크기의 윈도우로 구성된 하나의 인덱스를 이용하여 여러가지 길이의 질의 시퀀스들에 대한 서브 시퀀스 매칭을 수행하여 질의 시퀀스의 길이에 따른 성능 변화를 살펴본다. 첫번째 실험에서 사용된 윈도우 크기는 w = 64이며, 질의 시퀀스의 길이는 Len(Q) = 64, 128, 256, 512, 1024이다. 두번째 실험은 첫 번째 실험과 반대로 고정된 길이의 질의 시퀀스에 대하여 다양한 크기의 윈도우들로 구성된 각각의 인덱스를 이용하여 서브시퀀스 매칭을 수행함으로써 윈도우의 크기에 따른 검색 성능 변화를 살펴본다.
데이터처리
- 또한, 다차원 인덱스로는 1KB 크기의 페이지를 갖는 R*- 트리[1 기를 사용하였다. 인덱싱을 위한 저차원 변환은 DFT를 통하여 수행하였으며, 특성 추출 계수 f=6으로 하였다. 서브 시퀀스 매칭을 위한 기법으로는 FRM에 비하여 더 우수한 성능을 보이는 것으로 규명된 바 있는⑸ DualMatch 를 이용하였다.
이론/모형
- 이 결과, 인덱싱의 대상이 되는 전체 데이타 윈도우 점들의 수가 매우 많아지므로, R*- 트리를 위한 저장 공간이 커지며, 이 결과 인덱스 검색 단계의 성능이 크게 저하된다[4]. FRM에서는 이러한 문제를 해결하기 위하여 다수의 데이타 윈도우 점들을 포함하는 최소 포함 사각형(minimum bounding rectangle- MBR)들을 구성한 후 이 MBR들을 R*- 트리 [1 기에 저장하는 방법을 사용하였다.
- 인덱싱을 위한 저차원 변환은 DFT를 통하여 수행하였으며, 특성 추출 계수 f=6으로 하였다. 서브 시퀀스 매칭을 위한 기법으로는 FRM에 비하여 더 우수한 성능을 보이는 것으로 규명된 바 있는⑸ DualMatch 를 이용하였다.
- 우리는 을 동적 프로그래밍 기법을 이용하여 계산한다. 먼저 C‘冬에 대하여 다음의 순환 구조(recurrence)가 성립됨을 보인다.
- 이들은 각각 참고문헌 [4]와 [5] 에서소개된 방법이다. 참고문헌 [5]의 명칭을 따라 본 논문에서는 [4]의 기법을 FRM, [5]의 기법을 Dual-Match 라 부른다. FRM과 Dual-Match는 효과적인 서브 시퀀스 매칭을 위하여 인덱스를 사용한다.
성능/효과
- .제안된 기법이 단순한 기존의 기법과 비교하여 상당한 성능 개선 효과가 있음을 다양한 실험을 통해서 검증하였다.
- 본 실험에서 동일한 수의 질의시퀀스들을 포함하는 그룹의 개수와 그 그룹에 포함된 질의 시퀀스의 개수는 실제 응용의 특성을 반영하여 아래의 표 1과 같이 설정하였다. 4개의 그룹내의 질의 시퀀스들이 빈번하게 사용되고, 16개 그룹내의 질의 시퀀스들은 사용이 빈번하지 않음을 의미한다. 성능 평가지수로서 전체 그룹내의 총 216개의 질의 시퀀스를 대상으로 서브시퀀스 매칭을 수행하는 데에 걸린 실행 시간의 평균을 사용하였다.
- 또한, 이 비용 공식을 이용하여 전체 서브 시퀀스 매칭들의 성능을 극대화 할 수 있는 최적의 윈도우 크기들을 결정하는 알고리즘을 제안하였으며, 이 알고리즘의 최적성과 효율성을 이론적으로 규명하였다. 끝으로, 제안된 기법이 기존의 단순한 기법과 비교하여 상당한 성능 개선 효과가 있음을 다양한 실험을 통해서 검증하였다.
- 전체 실험 결과들을 요약하면 다음과 같다. 단 하나의 인덱스만을 이용하는 기존의 기법과 비교하여, 다중 인덱스를 사용하는 방식을 채택함으로써 큰 성능 개선 효과를 얻을 수 있었다. 또한, 사용되는 질의 시퀀스 길이의 분포를 고려하지 않은 일정 간격의 단순한 다중 인덱스를 이용하는 기법(B)와 비교해서도 제안된 기법(C) 는 상당한 실행 시간의 단축 효과를 보이는 것으로 나타났다.
- 데이타 시퀀스의 개수가 증가하더라도 기법(A)에 비하여 기법(B)가 좋은 성능을 보였고, 기법(B어】 비하여 제안된 기법에 의하여 정해진 다중 인덱스를 이용한 기법(C)가 더 나은 성능을 보였다. 기법(C)는 기법(A)에 비하여 약 5.
- 두번째 사전 실험의 결과 FRM과 DualMatch 모두 윈도우 크기가 증가함에 따라 검색 시간이 급격하게 감소하였다. 이는 질의 시퀀스와 윈도우 크기 간의 차이가 작아짐에 따라 윈도우 크기 효과에 따라 인덱스 검색 결과 후보 집합에 포함되는 후보 서브 시퀀스의 개수가 급격하게 감소하기 때문이다.
- 5배 성능이 향상되었다. 또한, 3개의 인덱스를 이용한 경우, 기법(C)는 기법(A)에 비하여 약 5.6배, 기법(B에 비하여 약 3.2배 성능이 향상되었다.
- 5배의 성능 향상 올 보였다. 또한, 대량의 합성 데이타를 이용한 실험 결과, 제안된 기법은 단일 인덱스를 사용한 경우와 비교하여 데이타 시퀀스의 개수 및 길이에 상관 없이 약 6 배의 성능 향상을 보였으며, 일정 간격의 인덱스를 사용한 경우와 비교하여 약 2배의 성능 향상을 보였다.
- 단 하나의 인덱스만을 이용하는 기존의 기법과 비교하여, 다중 인덱스를 사용하는 방식을 채택함으로써 큰 성능 개선 효과를 얻을 수 있었다. 또한, 사용되는 질의 시퀀스 길이의 분포를 고려하지 않은 일정 간격의 단순한 다중 인덱스를 이용하는 기법(B)와 비교해서도 제안된 기법(C) 는 상당한 실행 시간의 단축 효과를 보이는 것으로 나타났다.
- 다음과 같다. 먼저 위의 공식에 의하여 구해진윈도우 크기 WmaxGfc)를 사용하면 서브시퀀스 매칭에서 착오 기각이 발생하지 않음을 보이고 %以(4)가 착오 기각이 발생하지 않는 윈도우의 크기 중에서 가장 큰 윈도우 크기임을 이용하여 최적의 윈도우 크기임을 보인다.
- 본 논문의 주요 공헌은 다음과 같다. 먼저, 윈도우 크기 효과로 인한 서브시퀀스 매칭의 심각한 성능 저하 현상을 정량적으로 관찰하여, 하나의 윈도우 크기를 대상으로 만든 단 하나의 인덱스만을 이용하는 것은 실제 응용에서 만족할만한 성능을 제공할 수 없다는 것을 규명하였다. 또한, 이러한 문제로 인해 다양한 윈도우 크기들을 기반으로 다수의 인덱스들을 구성하여 서브 시퀀스 매칭을 수행하는 인덱스 보간법의 응용이 필요함을 보였다.
- 인덱스 보간법은 실제 응용에 따라 인덱스 구축 방법, 인덱스 선택 방법, 세부적인 처리 알고리즘 등이 달라진다. 본 논문에서 제안된 기법은 기존의 FRM과 Dual-Match에 모두 적용될 수 있는 기법이며, 검색 성능을 크게 향상시킬 수 있다.
- 사전 실험의 결과를 요약하면, 질의 시퀀스의 크기와윈도우의 크기의 차이가 커짐에 따라서 서브시퀀스 매칭의 성능은 급격하게 저하되는 것으로 나타났다. 따라서 기존 기법에서와 같이 하나의 윈도우 크기를 대상으로 생성된 단 하나의 인덱스만을 이용하는 경우, 실제 응용에서 만족할만한 성능을 낼 수 없다는 것을 알 수 있다.
- 실제 주식 데이타를 사용한 실험 결과, 제안된 기법은 단일 인덱스를 사용한 경우와 비교하여 약 7.8배, 일정 구간 인덱스를 사용한 경우와 비교하여 1.5배의 성능 향상 올 보였다. 또한, 대량의 합성 데이타를 이용한 실험 결과, 제안된 기법은 단일 인덱스를 사용한 경우와 비교하여 데이타 시퀀스의 개수 및 길이에 상관 없이 약 6 배의 성능 향상을 보였으며, 일정 간격의 인덱스를 사용한 경우와 비교하여 약 2배의 성능 향상을 보였다.
- 실험 결과, 하나의 인덱스를 사용하는 기법(A)에 비하여 일정 간격의 다중 인덱스를 이용한 기법(B)가 좋은 성능을 보였고, 기법(B)어) 비하여 제안된 기법에 의하여 선정된 다중 인덱스를 이용한 기법(C)가 더 좋은 성능을 보였다. 그림 4에서 5개의 인덱스를 이용한 경우, 기법 (C)는 기법 (A)에 비하여 약 7.
- 실험 결과는 실험 2와 그 경향이 매우 유사하게 나타났다 기법(C)는 데이타 시퀀스의 길이에 상관 없이 기법(A) 와 비교하여 약 6.2배, 기법(B)에 비하여 약 2배의 성능이 개선되는 것으로 나타났다.
- 첫번째 사전 실험의 결과 FRM과 Dual-Match 모두질의 시퀀스의 길이가 길어짐에 따라 검색 시간이 점차 증가하였다. 이러한 원인은 윈도우 크기 효과에 따라 질의 시퀀스와 윈도우 크기 간의 차이가 커지면서 인덱스 검색 결과 후보 집합에 포함되는 후보 서브시퀀스의 개수가 증가하기 때문이다.
후속연구
- 먼저, 윈도우 크기 효과로 인한 서브시퀀스 매칭의 심각한 성능 저하 현상을 정량적으로 관찰하여, 하나의 윈도우 크기를 대상으로 만든 단 하나의 인덱스만을 이용하는 것은 실제 응용에서 만족할만한 성능을 제공할 수 없다는 것을 규명하였다. 또한, 이러한 문제로 인해 다양한 윈도우 크기들을 기반으로 다수의 인덱스들을 구성하여 서브 시퀀스 매칭을 수행하는 인덱스 보간법의 응용이 필요함을 보였다. 인덱스 보간법을 응용하여 서브시퀀스 매칭을 수행하기 위해서는 먼저 다수의 인덱스들을 위한 윈도우 크기들을 결정해야 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.