선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 따라서 본 논문에서는 검색 시퀀스와 데이터베이스에 저장된 시퀀스의 길이가 같다는 가정에서 비슷한 정도, 즉 유사도가 ε 범위에 존재하는 모든 시퀀스를 효율적으로 검색하기 위한 색인 기법을 연구한다.
제안 방법
- 본 논문에서의 연구 진행 방향은 다음과 같은 방법을 사용하였다. (1) 대용량 시퀀스 데이터의 확보, (2) 시퀀스에서의 불완전 데이터 보완, (3) DFT를 이용한 시퀀스 데이터의 변환 후 데이터웨어하우스에 저장, (4) 영역 지정 방식의 질의를 사용한 유사 검색의 성능 향상을 위한 비트맵 인덱스 생성, (5) 유사도의 지정과 비 트맵 인덱스를 사용한 질의의 실행, (6) 상황에 따른 비교될 속성개수 변경 (7) 최소비용확인을 통한 유사 시퀀스 검색으로 연구를 진행하였다.
- 관계 형에서 원시 데이터를 활용하여 쉽게 표현하는 방법은 [표 1]과 같이 순수 관계형으로 표시하는 방법과, [표 2]와 같이 객체-관계형의 컬렉션 자료형으로 표현하는 2가지 방법이 있다. 2가지 방법은 장단점이 있으나 불규칙적인 시간 간격의 조정과 새로운 데이터의 삽입을 고려할 때 본 연구에서는 [표 1]의 방법을 사용하였다.
- DFT로 변환된 데이터의 유사검색 기능 평가를 위하여 데이터는 무작위로 입력하였으며 다양한 경우의 시퀀스 패턴을 확인하기 위하여 [그림 3]과 같이 대표적 인 패턴을 입력하였다. [그림 3]은 기본 데이터로 패턴 별로 저장되어 있는 것을 보여주고 있으며, 데이터는 4 개씩 패턴에 변화를 주어 입력하였고 시작하는 값은 각각 다르게 저장되어있다.
- 본 장에서는 DFT와 비트맵을 이용한 유사검색의 모의실험을 통하여 유사 검색의 성능을 평가하였으며 상 황별로 그 결과를 설명하였다. [그림 2]의 영역을 지정한 유사 검색 SQL에서 유사범위를 나타내는 r의 값, 그리고 DFT로 변환한 후 사용할 속성의 개수 n에 따라 유사 검색 성능을 평가하였다.
- [그림 3]은 기본 데이터로 패턴 별로 저장되어 있는 것을 보여주고 있으며, 데이터는 4 개씩 패턴에 변화를 주어 입력하였고 시작하는 값은 각각 다르게 저장되어있다. ➀번과 ➆번은 급격하게 증가 하는 값과 조금씩 증가하는 패턴을 정리하였고, ➁번은 ➀번과 ➆번과 반대이며 대표적인 패턴들을 만들어 그 기능을 확인하였다.
- [그림 2]의 SQL에서 r1, r2, r3, r4, r5, r6는 각 차원의 허용 범위 또는 오차 범위를 나타내므로 [그림 2]의 SQL은 유사범위 이내의 데이터를 찾아낸다. 검색 결과에서 가장 유사한 것을 찾는 것 또는 유사 정도에 따른 연산들은 후처리 과정에서 주기억장치에서 이루어지는 방법을 적용한다.
- 본 논문에서의 시퀀스 검색을 위한 과정은 대용량의 시퀀스 데이터웨어하우스에서 검색 시퀀스와 유사한 패턴을 가지는 즉 유사도 ε 범위 내에 있는 모든 검색 시퀀스를 찾기 위한 방법으로 원천 데이터를 시퀀스 데이터로 표현한 후 원천 데이터를 유사 검색에 적합하게 DFT를 사 용하여 변환하였다. 그 다음 변환된 데이터를 효율적으로 검색하기 위한 인덱스를 구축하였고 마지막으로 제안된 방법의 성능 평가를 위한 실험 시스템을 구축하고 그 성능을 평가하였다.
- 인덱스를 사용하기 위해서는 [그림 1]의 SQL 구문과 같이 각 컬럼의 값을 직접 비교하는 방식은 적합하지 않다. 대신 어떤 범위 내에 존재하는 레코드를 구하고, 그 다음 후 처리 방식으로 최근접 레코드를 찾는 방식을 사용한다. 따라서 [그림 1]의 SQL을 다음의 [그림 2] 형식으로 바꾼다.
- 본 논문에서 시퀀스가 저장되는 곳은 시퀀스 데이터가 입출력이 빈번하지 않으며 지속적으로 시퀀스가 추가되는 시퀀스의 특성에 따라 시퀀스에 적용되는 연산이 OLTP (On-Line Transaction Processing)가 아니라 OLAP(On-Line Analytic Processing)와 데이터 마이닝 (data mining)이 적용되는 데이터웨어하우스 (data warehouse)이다. 데이터웨어하우스에서는 그 특성상 효율적인 연산을 위한 전처리 (pre-processing) 시간이 소비되어도 전체 성능에 영향을 미치지 않으므로 본 논문에서의 전처리 과정은 시간 도메인으로 구성된 시퀀스 원시 데이터에 DFT (Discrete Fourier Transform) 를 적용하여 주파수 도메인 데이터로 변경한다. 변경된 데이터는 DFT의 특성으로 인하여 유사 패턴의 검색에 적합하며 또 유사도를 비교할 때 일부분만 사용되므로 색인에 사용되는 속성의 개수를 줄이는 장점이 있다.
- 본 논문에서의 시퀀스 검색은 대부분의 경우 원시 데이터에 직접 적용하기는 힘들다. 따라서 본 연구에서는 운용 데이터베이스의 데이터를 직접 사용하는 방법이 아니라 전처리 과정을 거친 후 데이터웨어하우스에 저장된 데이터를 사용하는 방식을 적용한다.
- 먼저 [표 1]의 데이터를 데이터웨어하우스에 저장할 때 어떻게 표현할 것인지에 대한 연구를 진행하였다. 관계 형에서 원시 데이터를 활용하여 쉽게 표현하는 방법은 [표 1]과 같이 순수 관계형으로 표시하는 방법과, [표 2]와 같이 객체-관계형의 컬렉션 자료형으로 표현하는 2가지 방법이 있다.
- 먼저 데이터베이스 데이터를 데이터웨어하우스에 저장하기 위하여 필요한 데이터를 추출하였다. 추출된 데이터를 ID와 날짜로 정렬한 원시 데이터가 다음의 [표 1] 형식을 가진다고 가정할 때 다음 테이블의 내용을 정리하여 검색하기 쉽게 변환하였다.
- 3가지 방법은 데이터 도메인에 따라 다른 특성을 가지고 있다. 본 논문에서 다루는 개인의 정보 특성상 부정 오류 (false negative)보다는 긍정 오류 (false positive)가 더 의미를 가지므로 3)번의 방식을 채택한다.
- 본 논문에서의 시퀀스 검색을 위한 과정은 대용량의 시퀀스 데이터웨어하우스에서 검색 시퀀스와 유사한 패턴을 가지는 즉 유사도 ε 범위 내에 있는 모든 검색 시퀀스를 찾기 위한 방법으로 원천 데이터를 시퀀스 데이터로 표현한 후 원천 데이터를 유사 검색에 적합하게 DFT를 사 용하여 변환하였다.
- 이 방법들은 공간 인덱스의 한계 문제로 속성의 개수를 3개 또는 4개로 제한해야 하는 단점이 있었다. 본 논문에서의 연구 방법은 영역 지정 방식의 질의 방식과 비트맵 인덱스를 사용하여 기존의 연구 결과들과 다른 실험결과를 보였다. 영역 지정 시 사용하는 유사도에 따라 질의 결과의 개수가 바뀜에 주파수 영역으로 변환된 데이터의 속성이 가변적으로 변동될 수 있음을 보였다.
- 2절의 방식에 의해 불완전한 데이터를 처리한 후 다음 단계는 [표 1]의 데이터를 검색 가능한 형태로 변환하는 과정을 수행하였다. 본 연구 에서는 [표 1]의 시퀀스를 DFT를 이용하여 변환한 후 DFT 계수의 초기 n개만 사용하는 방법을 적용한다. (n=3인 경우 실수와 허수 부분으로 구성되어 있으므로 6개의 값이 필요하다) 따라서 최초의 원시 데이터에서 다음의 [표 3] 테이블을 생성한다.
- [그림 1]의 방식과 같이 인덱스를 사용하지 않는 경우 DFT_TABLE에 저장된 모든 데이터를 전부 스캔하기 위하여 디스크 IO가 많아지는 비효율성이 있다. 본 연구에서는 이 문제점을 해결하기 위한 방법으로 [표 3]의 컬럼 n1 ~ n6에 대한 인덱스를 적용하는 방식을 사용한다. 인덱스를 사용하기 위해서는 [그림 1]의 SQL 구문과 같이 각 컬럼의 값을 직접 비교하는 방식은 적합하지 않다.
- 본 장에서는 DFT와 비트맵을 이용한 유사검색의 모의실험을 통하여 유사 검색의 성능을 평가하였으며 상 황별로 그 결과를 설명하였다. [그림 2]의 영역을 지정한 유사 검색 SQL에서 유사범위를 나타내는 r의 값, 그리고 DFT로 변환한 후 사용할 속성의 개수 n에 따라 유사 검색 성능을 평가하였다.
- 성능 평가의 기준은 DFT로 변환된 값의 개수와 값의 범위에 따른 비교방법과 결과의 수, 비용 등을 토대로 작성을 하였다. 데이터는 10,000개, 50,000개, 100,000 개의 경우에 따른 결과로 실험을 하였으며 10 경우에 따라 비교되는 실수, 허수의 개수 역시 변화되었으며 각각의 결과와 비용이 다른 경우를 보였으며 비트맵 인덱 스를 사용하여 검색 속도를 높였다.
대상 데이터
- 본 논문에서 시퀀스가 저장되는 곳은 시퀀스 데이터가 입출력이 빈번하지 않으며 지속적으로 시퀀스가 추가되는 시퀀스의 특성에 따라 시퀀스에 적용되는 연산이 OLTP (On-Line Transaction Processing)가 아니라 OLAP(On-Line Analytic Processing)와 데이터 마이닝 (data mining)이 적용되는 데이터웨어하우스 (data warehouse)이다. 데이터웨어하우스에서는 그 특성상 효율적인 연산을 위한 전처리 (pre-processing) 시간이 소비되어도 전체 성능에 영향을 미치지 않으므로 본 논문에서의 전처리 과정은 시간 도메인으로 구성된 시퀀스 원시 데이터에 DFT (Discrete Fourier Transform) 를 적용하여 주파수 도메인 데이터로 변경한다.
성능/효과
- 반환되는 결과가 많은 경우 속성의 개수를 추가하여 반환되는 결과 개수를 줄여 그에 따르 는 비용 역시 줄여야 하겠으며 후처리 과정에 필요한 비용도 줄여 보다 정확한 결과를 얻을 수 있다. 결과 값을 보면 알 수 있듯이 속성의 개수가 3개만 해도 되는 경우가 있는가 하면 범위에 포함되는 결과 값이 많은 경우에는 비트맵 인덱스를 사용함으로 속성의 개수를 많이 하면 할수록 빠르고 정확한 결과를 얻을 수 있다. 필요에 따라 결과 값이 작다면 속성의 개수를 3개만 사용해도 기존 연구 결과와 같이 충분한 검색 결과를 얻을 수 있을 것이나 반면 유사 범위의 선택 폭이 너무 느슨해 결과의 개수가 많다면 속성의 개수 역시 4, 5, 6으로 늘려 반환되는 결과 값의 수도 줄이고 더불어 비용 역시 감소시킬 수 있다.
- 성능 평가의 기준은 DFT로 변환된 값의 개수와 값의 범위에 따른 비교방법과 결과의 수, 비용 등을 토대로 작성을 하였다. 데이터는 10,000개, 50,000개, 100,000 개의 경우에 따른 결과로 실험을 하였으며 10 경우에 따라 비교되는 실수, 허수의 개수 역시 변화되었으며 각각의 결과와 비용이 다른 경우를 보였으며 비트맵 인덱 스를 사용하여 검색 속도를 높였다.
- 본 논문에서의 모의실험 결과에 의하면 대용량 시퀀스에서 유사 시퀀스를 검색하는 방법으로 시퀀스의 DFT 변환, 유사도 범위를 지정하는 방식의 질의, 그리고 비트맵 인덱스를 사용하는 실행 환경이 우수한 성능을 나타내는 것을 보였다. 이는 대부분의 상용 DBMS 에서 사용하는 R-tree 또는 Quad 트리와 같은 공간 인덱스가 실제 환경에서 4차원 공간 이상을 지원하지 못하는 문제점으로 인하여 시퀀스를 주파수 영역으로 변 환하여 사용하는 방식에서 2개 이상의 속성 (실수 2개, 허수 2개)을 사용하지 못하는 매우 실질적인 문제점을 해결하였다.
- 본 논문의 실험결과에 의하면 유사 검색의 과정에서 유사도 (r의 값)를 사용한 검색 방법에서 검색 결과에 포함되는 결과의 개수가 적은 경우에는 실수, 허수의 속성개수를 기존 연구의 결과와 같이 각각 3개 정도만 해도 충분한 결과를 얻을 수 있었다. 하지만 속성을 3 개 사용하여 유사 검색의 결과에 긍정 오류에 의해 반환되는 결과 값이 많다면 많은 비용이 필요하게 된다.
- 본 논문에서의 연구 방법은 영역 지정 방식의 질의 방식과 비트맵 인덱스를 사용하여 기존의 연구 결과들과 다른 실험결과를 보였다. 영역 지정 시 사용하는 유사도에 따라 질의 결과의 개수가 바뀜에 주파수 영역으로 변환된 데이터의 속성이 가변적으로 변동될 수 있음을 보였다.
- 결과 값을 보면 알 수 있듯이 속성의 개수가 3개만 해도 되는 경우가 있는가 하면 범위에 포함되는 결과 값이 많은 경우에는 비트맵 인덱스를 사용함으로 속성의 개수를 많이 하면 할수록 빠르고 정확한 결과를 얻을 수 있다. 필요에 따라 결과 값이 작다면 속성의 개수를 3개만 사용해도 기존 연구 결과와 같이 충분한 검색 결과를 얻을 수 있을 것이나 반면 유사 범위의 선택 폭이 너무 느슨해 결과의 개수가 많다면 속성의 개수 역시 4, 5, 6으로 늘려 반환되는 결과 값의 수도 줄이고 더불어 비용 역시 감소시킬 수 있다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.