멀티미디어 데이타로 부터 나오는 정보를 효과적으로 사용하기 위해서는 멀티미디어 데이타의 저장과 색인, 검색을 지원하는 기법이 필요하다. 멀티미디어 데이타의 내용에 의한 색인 및 검색은 이것을 가능하게 하는 중요한 기술이지만 현재 해결해야 할 많은 문제를 갖고 있다.
본 논문은 멀티미디어 데이타베이스에서 내용에 의한 검색을 위한 새로운 색인 구조인 HG-트리 (또는 Hilbert grid 트리)와 관련 알고리듬을 제시한다. HG-트리는 다차원 점 색인 구조로서 멀티미디어 데이타의 내용에 기반한 질의 처리를 위한 유용하고 효율적인 구조이다. 현재까지 많은 다차원 점 색인 구조들이 제안되었지만 HG-트리는 그보다 우월한 성능을 보인다.
HG-트리 설계시의 주된 두 가지 목표는 색인 구조의 저장 효율을 높이고, 디렉토리 점유율을 낮추는 것이다. 저장 효율이 높고, 디렉토리 점유율이 낮을수록 질의 처리 시의 디스크 접근 횟수를 줄인다. 첫번째 목표를 이루기 위해 노드 범람 발생시, 가능하면 노드 분리를 억제시킨다. 노드 분리가 불가피할 때는 두개의 노드를 세 개로 분리하여 가능하면 노드가 수용하는 데이타 양의 균형을 맞추도록 한다. 다차원 공간에 이러한 전략을 수행하기 위해 Hilbert곡선을 사용하여 데이타 객체들과 디렉토리 노드들에게 일차원적인 순서를 부여하였다.
두 번째 목표인 디렉토리 점유율을 줄이기 위해 아래 레벨의 모든 영역을 포함하는 최소 경계 간격 (minimum bounding interval)을 도입하여 디렉토리 영역을 나타낸다. 이것은 특히 전체 데이타 공간에 비해 실제 데이타 집합이 점유하는 공간이 작을 때 효과적이다.
그런데, 이상의 두 가지 목표 사이에는 상쇄 효과가 있어서 동시에 두 가지를 다 이루기는 매우 어렵다. 그러나 HG-트리는 이 상쇄 효과를 어느 정도까지 제어할 수 있는 융통성을 갖고 있다. 본 논문에서는 HG- 트리를 설계, 구현하고, 삽입 및 삭제, 검색 (정확 일치 검색, 영역 검색, 최대 근접 검색)을 위한 알고리듬을 제공한다.
HG-트리의 성능을 평가하기 위해, 다양한 실험을 통해 현재 가장 성공적인 다차원 점 색인 구조로 평가 받는 buddy-트리와 검색, 갱신 (삽입, 삭제), 저장 비용을 비교하였다. 모든 비교 항목 (검색, 갱신, 저장) 에서 평균적으로 HG-트리는 buddy-트리보다 우수하였으며, 이것은 HG-트리가 대용량 멀티미디어 데이타베이스에서의 내용에 의한 색인 및 검색을 위한 효과적인 도구임을 증명하는 것이다.
또한 본 논문에서는 내용에 의한 멀티미디어 검색에서 가장 널리 사용되는 질의 형태인 최대 근접 질의의 평균 검색 시간을 추정할 수 있는 수학적 공식을 개발하였다. 아울러, 다차원 색인 구조상에서의 최대 근접 질의의 성능에 영향을 주는 요소를 규명하였다. 유도한 공식의 정확성을 검증하기 위하여 다양한 실험을 수행하였으며, 실험 결과에 의하면, 제안된 공식은 균일한 데이타 분포뿐만 아니라 편중되고 상관 관계를 갖는 데이타 분포에서도 정확함이 입증되었다.
