초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

서브시퀀스 매칭은 주어진 질의 시퀀스와 변화의 추세가 유사한 서브시퀀스들을 시계열 데이터베이스로부터 검색하는 연산이다. 본 논문에서는 서브시퀀스 매칭 처리의 성능 병목을 파악하고, 이를 해결함으로써 전체 서브시퀀스 매칭의 성능을 크게 개선하는 방안에 관하여 논의한다. 먼저, 사전 실험을 통하여 후처리 단계가 서브시퀀스 매칭의 성능 병목이며, 후처리 단계의 최적화가 기존의 서브시퀀스 매칭 기법들이 간과한 매우 중요한 이슈임을 지적한다. 이러한 서브시퀀스 매칭의 성능 병목을 해결하기 위하여 후처리 단계를 최적으로 처리할 수 있는 간단하면서도 매우 효과적인 기법을 제안한다. 제안된 기법은 후처리 단계에서 후보 서브시퀀스들이 질의 시퀀스와 실제로 유사한가를 판단하는 순서를 조정함으로써 기존의 후처리 단계의 처리에서 발생하는 많은 디스크 액세스의 중복과 CPU 처리의 중복을 완전히 제거할 수 있다. 실제 데이터와 생성 데이터를 이용한 다양한 실험들을 통하여 제안된 기법의 성능 개선 효과를 정량적으로 검증한다.

서브시퀀스 매칭은 주어진 질의 시퀀스와 변화의 추세가 유사한 서브시퀀스들을 시계열 데이터베이스로부터 검색하는 연산이다. 본 논문에서는 서브시퀀스 매칭 처리의 성능 병목을 파악하고, 이를 해결함으로써 전체 서브시퀀스 매칭의 성능을 크게 개선하는 방안에 관하여 논의한다. 먼저, 사전 실험을 통하여 후처리 단계가 서브시퀀스 매칭의 성능 병목이며, 후처리 단계의 최적화가 기존의 서브시퀀스 매칭 기법들이 간과한 매우 중요한 이슈임을 지적한다. 이러한 서브시퀀스 매칭의 성능 병목을 해결하기 위하여 후처리 단계를 최적으로 처리할 수 있는 간단하면서도 매우 효과적인 기법을 제안한다. 제안된 기법은 후처리 단계에서 후보 서브시퀀스들이 질의 시퀀스와 실제로 유사한가를 판단하는 순서를 조정함으로써 기존의 후처리 단계의 처리에서 발생하는 많은 디스크 액세스의 중복과 CPU 처리의 중복을 완전히 제거할 수 있다. 실제 데이터와 생성 데이터를 이용한 다양한 실험들을 통하여 제안된 기법의 성능 개선 효과를 정량적으로 검증한다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 논문에서는 기존의 서브시퀀스 매칭 처리의 성능 병옥욜 파악하고, 이흘 신속하게 처리하기 위한 간단하면서도 매우 효과적인 윈도우 순서 기법을 제안하였다. 실험 결과에 의하면, 제안된 기법을 채택함으로써 전체 서브시퀀스 매칭에 소요외는 시간의 90%에 이르던 후처리 단계의 비중을 70%이하로 내릴 수 있었다.
• 기존의 기법늘TFal94][Moo011 등은 주로 위와 같이 착오 채택의 수를 졸이는 방안에 관해서만 연-μ의 초점을 맞추었으며, 좋은 후처리 단계의 처리 방식을 고안하는 전략은 간과하였다. 본 논문에서는 좋은 후처리 단계의 수행 방식을 제시하고, 이를 퉁하여 전체 서브시퀀스 매칭의 성능올 크게 향상시키고자 한다.
• 본 언T에서는 후처리 단계에서 소요되는 시간올 줄일 수 있는 또 하나의 중요한 전락으로서 후처리 단4의 수해 방식 자체를 개선함 것을 제시한다. 이 전략온 동일한 수의 후보 서브시퀀스들이 반환된 경우라도, 후처리 단계가 효과적으로 수행된다면 처리 성능을 개선시킬 수 있다는 점에서 착안한 것이다.
• 디스크 액세스 및 CPU 처리의 중복 문제가 발생하는 근본척인 원인온(1) 데이터 윈도우들이 동일한 시퀀스 훅은 서브시퀀스로부터 추출되었는 지의 여부에 관계없이 R*-트리 내에 독립적으로 저장되며, (2) 후처리 단 계에서 인덱스 검색의 결과로 반환되는 순서 n대로 후보 서브시퀀스의 착오 채택 여부흘 검사한다는 데에 있다. 본 연구에서는 이러한 문제룔 해결하기 위한 간단하면서도 매우 효과적인 윈도우 순서 기법올 제안한다. 제안하는 기법의 기본 전략은 인덱스 검색의 결과로 반환되는 후보 윈도무들외 처리 순서를 조정함으로써 동일한 시퀀스에 속하는 후보 윈도 우됼, 같온 서브시퀀스에 속하는 후보 윈도우들을 연속적으로 처리한다는 것이다.
• 본 언T에서는 후처리 단계에서 소요되는 시간올 줄일 수 있는 또 하나의 중요한 전락으로서 후처리 단4의 수해 방식 자체를 개선함 것을 제시한다. 이 전략온 동일한 수의 후보 서브시퀀스들이 반환된 경우라도, 후처리 단계가 효과적으로 수행된다면 처리 성능을 개선시킬 수 있다는 점에서 착안한 것이다. 기존의 기법늘TFal94][Moo011 등은 주로 위와 같이 착오 채택의 수를 졸이는 방안에 관해서만 연-μ의 초점을 맞추었으며, 좋은 후처리 단계의 처리 방식을 고안하는 전략은 간과하였다.
• 이것은 동일한 후보 서브시쾐스를 질의 시퀀스와 중북하여 비교하는 기존외 기법의 문제점을 제안된 기법이 해결하였기 때문이다. 이것온 제안된 기법에서 요구하는 정렬 오버切드가 전체 성능에 부정적인 영향을 미치지 왆옴을 보여주는 것이다.
• 본 논문에서는 FRM과 Du그 1-Match 모두에서 후처리 단계가 서브시퀀스 매칭외 성능 병목이며, 후처리 단계의 최적화가 기존의 서브시퀀스 매칭 기법들이 간과한 메우 중요한 이슈임을 지적한다. 이러한 서브시퀀스 매칭외 성능 벙윽을 헤결하기 위하여 후처리 단계를 최적으로 처리할 수 있는 간단하면서도 데우 효과적인 기법을 제안한다. 제안된 기법온 후처리 단계에서 후보 서브시큰스들이 질의 시퀀스와 실제로 유사한가를 판단하는 순서是 조정함으로써 기존의 후처리 단계의 처리에서 발생하는 많온 디스크 액세스의 중복과 CPU 처리의 중북을 완전히 제거할 수 있다.
• 60 배까지 향상시키는 효 과# 보였다. 현재, 제안된 기법을 다양한 변환올 지원하는 서브시퀀스 매칭에 적응하는 방안과 그 성능 개선 효과를 정량적으로 규명하는 문제애 대하여 연구하고 있다.

제안 방법

• L온 셜험 결과是 나타낸 것이다. 먼저, 선텍륲偽ele라ivitv)[Se】79]이 10애인 경우의 PRTime(DISK) 와 PP.Time(CP 功를 분석한다. PPEne(DISK) 의 경우, 제안된 기법이 기존 기법과 비교하여 30(-5.
• 먼저, 실험 1에서는 K£tock_Data로부터 추출한 깊이 256의 디스조인트 윈도오들을 포함하는 R*-트리에 대하여 제안된 기법과 기존 기법을 채택 하는 서로 다른 두 가지 Dual-Match 기반 서브시큰스 매칭 수행하였다. 사용된 각 잘와 시퀀스외 길이는 512이다.
• K_Stock_D교t그는 비교적 소규모의 데이터베이스이다. 본 성능 평가예서 는 제안된 기법이 대규모 데이터베이스에서도 효과적으로 동작함을 규평 하기 위하여 다양한 시퀀스의 수횰 갖도록 싱성한 대규모 Sy虹Data를 이용한 실혐올 추가로 수행하였다.
• 본 연구에서는 먼저 위에서 서브시퀀스 미칭의 전체 처히 시간 중 각 요소가 차지하는 비중을 분석하기 위하여 다음과 같온 사전 실험올 수행하였다. 사용된 실험 데이터는 길이가 1, 024인 620개의 한국의 실쟤 주식 데이터이다.
• 제안된 기법온 후처리 단계에서 후보 서브시큰스들이 질의 시퀀스와 실제로 유사한가를 판단하는 순서是 조정함으로써 기존의 후처리 단계의 처리에서 발생하는 많온 디스크 액세스의 중복과 CPU 처리의 중북을 완전히 제거할 수 있다. 실재 데이터와 从성 데이터를 이웅한 다양한 실협들을 퉁하여 제안된 기범외 성능 개선 효과를 정량적으로 검중한다
• 실험 2에서는 데이터 시퀀스의 길이는 LOOO으로 고정시킨 상태에서 톄이터 시쿤스들의 수틀 5,000, 10, 000, 15,000, 20, 000, 25,000으로 변화하면서 제안된 기법과 기촌 기법을 채택하는 서로 다른 두 가지 Du겨 1-Match 기반 서브시퀀스 몌칭외 성능옻 비교하였다. 사웅된 질의 시퀀스의 길이는 500이며, 질의 선핵를.
• 사용된 실험 데이터는 길이가 1, 024인 620개의 한국의 실쟤 주식 데이터이다. 저차원 변환올 위해서는 DFT를 사웅하고, 각 시퀀스로부터 인덱싱울 위한 6개의 륵성을 추출함으로써 6차원 R*-트리를 구성하였다. 사융된 질외 시퀀스의 길이는 768이며, 허용치 e 온 15개의 최종 질의 결과가 나오도록 설정하였다.
• 제안된 윈도우 순서 기법의 성능 비교 다상온 기존의 인덱스 검색 단계에서 반환하는 순서대로 후처리를 수행하는 기존의 기법이다. 참고 문헌 [MooO기에서 아미 DuSMatch가 FRM보다 월동하게 우수한 성능욜 가지는 것으로 판명되었으므로, 본 성눙 평가에서는 제안된 기법과 기존의 기법욜 DuakMatch에 적毋■항으로써 두 기법의 성능올 비교하였다,
• 본 연구에서는 이러한 문제룔 해결하기 위한 간단하면서도 매우 효과적인 윈도우 순서 기법올 제안한다. 제안하는 기법의 기본 전략은 인덱스 검색의 결과로 반환되는 후보 윈도무들외 처리 순서를 조정함으로써 동일한 시퀀스에 속하는 후보 윈도 우됼, 같온 서브시퀀스에 속하는 후보 윈도우들을 연속적으로 처리한다는 것이다.
• 제안된 윈도우 순서 기법의 성능 비교 다상온 기존의 인덱스 검색 단계에서 반환하는 순서대로 후처리를 수행하는 기존의 기법이다. 참고 문헌 [MooO기에서 아미 DuSMatch가 FRM보다 월동하게 우수한 성능욜 가지는 것으로 판명되었으므로, 본 성눙 평가에서는 제안된 기법과 기존의 기법욜 DuakMatch에 적毋■항으로써 두 기법의 성능올 비교하였다,

대상 데이터

• 본 연구에서는 성눙 분석을 위하여 실제 데이터베이스 K_Stock_Data와 합성 데이터 Svn Data들 사용하였다. K Stock_Data는 사전 실험해서 사요하였던 것과 동일하며, 합성 데이터 SYn_Data니의 각 시퀀스 S = <sl, s2, …, sn> 는 다음과 같은 렌덤 워크(random walk) 형태를 가진다 [Agr93].
• 먼저, 실험 1에서는 K£tock_Data로부터 추출한 깊이 256의 디스조인트 윈도오들을 포함하는 R*-트리에 대하여 제안된 기법과 기존 기법을 채택 하는 서로 다른 두 가지 Dual-Match 기반 서브시큰스 매칭 수행하였다. 사용된 각 잘와 시퀀스외 길이는 512이다.
• 본 연구에서는 먼저 위에서 서브시퀀스 미칭의 전체 처히 시간 중 각 요소가 차지하는 비중을 분석하기 위하여 다음과 같온 사전 실험올 수행하였다. 사용된 실험 데이터는 길이가 1, 024인 620개의 한국의 실쟤 주식 데이터이다. 저차원 변환올 위해서는 DFT를 사웅하고, 각 시퀀스로부터 인덱싱울 위한 6개의 륵성을 추출함으로써 6차원 R*-트리를 구성하였다.
• 저차원 변환올 위해서는 DFT를 사웅하고, 각 시퀀스로부터 인덱싱울 위한 6개의 륵성을 추출함으로써 6차원 R*-트리를 구성하였다. 사융된 질외 시퀀스의 길이는 768이며, 허용치 e 온 15개의 최종 질의 결과가 나오도록 설정하였다. 윈도우의 길이로는 FRM 의 경우 512, Du亦Match의 경우 256으로 설정하였다.

이론/모형

• 참고 문헌 |Fal94] 및 [MooO기에서는 서브시毛스 매칭율 위한 처리 거 범율 제안하였다. 참고 운헌 [M(x)0기의 명칭을 따라 본 논문에서는 [Fal941의 기법을 FRM' [MooO기의 기법을 Du기-Match라 부룐다. 두 기법 모두 미리 지정된 고정죈 길이 w흘 갖는 윈도우(window) 게념을 이융한다.

성능/효과

• PP-Tg(CPU)의 경우, 후보 서브시콘스 식별자돌올 정렬해야 하는 추가의 오버챙드가 있옴에도 제안된 기법이 기존 기법과 비교하여 더 나온 성능을 보였다. 이것은 동일한 후보 서브시쾐스를 질의 시퀀스와 중북하여 비교하는 기존외 기법의 문제점을 제안된 기법이 해결하였기 때문이다.
• Time(CP 功를 분석한다. PPEne(DISK) 의 경우, 제안된 기법이 기존 기법과 비교하여 30(-5.896/0.195) 배 이상의 성능 개선 효과書 가지뇬 것오로 나타났다. 표 4.
• 가로축은 데이日 시퀀스의 수 卷 나타내며, 세로축온 서브시퀀스 매칭올 위한 후처리 단계 수행 시간 (PP-Total) 및 전체 수행 시간(T아al)을 나타낸다. 데이터 시퀀스의 수가 중가함에 따라 두 가지 기법윺 위한 후처리 단계 수행 시간은 거외 선형적으로 증가하는 것으로 나타났다. 후처리 단계 수행 시간외 중가울에서 는 두 기법이 큰 차이를 보였다.
• 본 논문에서는 FRM과 Du그 1-Match 모두에서 후처리 단계가 서브시퀀스 매칭외 성능 병목이며, 후처리 단계의 최적화가 기존의 서브시퀀스 매칭 기법들이 간과한 메우 중요한 이슈임을 지적한다. 이러한 서브시퀀스 매칭외 성능 벙윽을 헤결하기 위하여 후처리 단계를 최적으로 처리할 수 있는 간단하면서도 데우 효과적인 기법을 제안한다.
• 1. 선택률의 변화에 따르는 제안된 기법의 성능 개선 효과.
• 본 논문에서는 기존의 서브시퀀스 매칭 처리의 성능 병옥욜 파악하고, 이흘 신속하게 처리하기 위한 간단하면서도 매우 효과적인 윈도우 순서 기법을 제안하였다. 실험 결과에 의하면, 제안된 기법을 채택함으로써 전체 서브시퀀스 매칭에 소요외는 시간의 90%에 이르던 후처리 단계의 비중을 70%이하로 내릴 수 있었다. 이것온 제안된 기법이 서브시퀀스 먜칭 외 성눙 병윽을 성공적으로 해결하였옴을 시사하는 것이다.
• 이러한 서브시퀀스 매칭외 성능 벙윽을 헤결하기 위하여 후처리 단계를 최적으로 처리할 수 있는 간단하면서도 데우 효과적인 기법을 제안한다. 제안된 기법온 후처리 단계에서 후보 서브시큰스들이 질의 시퀀스와 실제로 유사한가를 판단하는 순서是 조정함으로써 기존의 후처리 단계의 처리에서 발생하는 많온 디스크 액세스의 중복과 CPU 처리의 중북을 완전히 제거할 수 있다. 실재 데이터와 从성 데이터를 이웅한 다양한 실협들을 퉁하여 제안된 기범외 성능 개선 효과를 정량적으로 검중한다
• 이것은 제안된 기법이 서브시퀸스 매칭의 성능 병목을 성공적으로 해곃하였옴올 보여주는 것이다. 제안된 기법을 퉁한 성능 병묵의 헤결 결과, 전채 수행 시간온 약 3.88 배에서 4.21 배 개선되는 것으로 나타났다.
• 천제 후처리 단겨 수행 시간(FP、Time(CPB+PP-Time(DISK))외 경우, 제안된 가법온 기존 기법외 성능을 7.19(-(0.780+5.896)/(0.733+0.195)) 배 개선한 것으로 나타났다. 포한, 전체 서브시퀀스 매칭의 수행 시간(Total)의 경우, 제안된 기법을 후처리 단계에 걲용함으로써 얻게 되는 성눙 걔선 효과는 4.
• 195)) 배 개선한 것으로 나타났다. 포한, 전체 서브시퀀스 매칭의 수행 시간(Total)의 경우, 제안된 기법을 후처리 단계에 걲용함으로써 얻게 되는 성눙 걔선 효과는 4.91(-7.232/1.473) 배로 나탁났다. 선택是 5x10』및 1时에 대한 실험 결과도 선택률 发尸인 경우의 실험결과와 매우 유사한 경향율 보였다.
• 이것온 제안된 기법을 채택하는 경우, 후처리 과정에서 나타나는 시퀀스 액세스의 중복과 서브시퀀스 비교의 중뵥을 완전히 제거할 수 있기 때문이다. 후처리 단계 수행 시간에 대한 제안된 기법의 성능 개선 효과는 약 5.14 배에서 약 5.22 배 사이로 나타 났다

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기