일반기술

대용량 데이터베이스에서의 고속에 의한 다해상도의 최적탐색방법

기술의 개요 - 본 기술은 대용량 데이터베이스에서의 고속에 의한 다해상도의 최적 탐색방법에 관한 것이다. 종래의 클러스터 기반 기법들은 최적 검색을 보장하지 못하며, 탐색 속도가 만족 할만한 검색 정확도를 얻기에는 충분히 빠르지 못하였다. 이에 본 기술은 1) 가능성이 있는 클러스터와 가능성이 없는 클러스터를 정확하게 구분하는 부등식을 유도하고 이를 이용한 최적의 탐색 기법을 구현토록 한다. 2) 고속 처리를 위한 다해상도 데이터 구조에 기반을 둔 부등식을 유도하고 이를 이용한 고속 최적 탐색 기법을 구현토록 한다. - 본 기술에 따른 대용량 데이터베이스에서의 고속에 의한 다해상도의 최적 탐색방법은 1) 데이터베이스 내의 모든 데이터들을 일정 수의 클러스터(유사한 특징을 갖는 클러스터)들로 나눈다. 2) 각 클러스터와 문의자간 거리의 하계(lower bound)를 구하여 가능성이 없다고 판단될 경우 그 클러스터를 제거하고 최종적으로 가능성이 있다고 판단된 클러스터들의 데이터들 중에서 최적 정합자를 찾는다. 3) 보다 많은 계산량 감소를 위해 탐색 과정에서 불필요한 특징 정합 연산을 줄이기 위한 다해상도 데이터 구조에 기반을 둔 거리부등식 성질을 유도한다.기술의 특징 - 제 1 단계 : 데이터베이스에 저장된 문의자 특징 Q의 다 해상도 구조를 구함. - 제 2 단계 : 구조에서 문의자 특징 Q와 가장 근접한 초기의 최소거리 을 무한대로 설정. - 제 3 단계 : 초기의 데이터베이스 i와 계층 l를 모두 1로 설정. - 제 4 단계 : 임의의 저해상도 계층 l에서 문의자 히스토그램과 i번째 히스토그램과의 거리를 산출함. - 제 5 단계 : 임의의 고해상도 계층 L에서 문의자 히스토그램과 i번째 히스토그램과의 거리를 산출함. - 제 6 단계 : 최종의 최소거리를 갖는 데이터를 최적 정합자로 선택.기술의 장점 - 가능성이 있는 클러스터와 가능성이 없는 클러스터를 정확하게 구분하는 부등식을 유도하고 이를 이용한 최적의 탐색 기법을 구현할 수 있도록 함.