한글내용
(Korean Abstract) |
새로운 많은 응용들이 데이터베이스 시스템으로 하여금 고차원(high dimensional) 데이터 집합에 대한 효율적인 지원을 요구하고 있다. 그러나 많은 노력에도 불구하고 현재의 계층 구조의 다차원 색인 기법들은 고차원, 예를 들어 100차원 이상에서는 이론적으로나 실제적으로 만족할 만한 성능을 보여주지 못하고 있다. 따라서 이러한 차원의 저주(dimensionality curse)를 해결하는 방법으로서, 차원을 줄이거나 또는 근사(approximate) 해를 구하는 등의 접근법이 최근에 개발되었다. 그러나 이러한 방법들은 근본적으로 질의 처리 결과의 정확도의 상실이라는 문제를 갖고 있다. 따라서 정확도의 보존을 위한 기법으로 최근에 VA-file, LPC-file과 같이 벡터 근사(vector approximation)에 기반한 기법들이 개발되었다. 이들은 기존의 트리 형태의 다차원 색인 구조로는 순차 검색보다 성능이 우월할 수 없다는 가정 하에 압축된 색인 파일을 구성하고 이를 순차 검색함으로써 검색 성능을 보장 받으려고 한다. 그러나 이 방법은 검색 성능이 색인 파일의 크기에 영향을 받으며, 한번에 큰 검색 공간을 줄이는 기존의 트리 형태의 계층적 색인 구조의 장점을 상실한다.
본 논문에서는 고차원 데이터 집합에서 덩어리(clusters)와 국외자(outliers)를 구분해내어, 데이터 집합의 분할을 덩어리에 집중하고, 이 덩어리들을 계층 구조로 구성함으로써 고차원 데이터 집합에 대해서도 트리 형태의 계층적 색인 구조를 형성할 수 있음을 보인다. |
