비공간 검색 조건이 포함된 k-최근접 질의 처리를 위한 R-트리와 시그니쳐 화일의 결합 = Combining R-trees and Signature Files for Handling k-Nearest Neighbor Queries with Non-spatial Predicates

국문 초록 (Abstract)

멀티미디어 데이타베이스에서 k-최근접 질의는 가장 일반적이며, 비공간 검색 조건이 포함된 경우가 많다. 현재까지 이러한 질의를 위한 여러 기법 중에서 Hjaltason과 Samet이 제안한 점증적 최근접 알고리즘이 가장 유용하다고 알려져 있다[1]. 질의 처리를 위해 상위 연산자가 k보다 많은 객체를 요구할 때, 이 알고리즘은 처음부터 질의를 재실행하지 않고 다음 객체를 전달할 수 있기 때문이다. 그런데, 이 알고리즘에서 사용하는 R-트리는 결국에는 비공간 검색 조건을 만족시키지 않을 투플 후보들을 부분적으로 제거할 수가 없기 때문에 비효율적이다. 본 논문에서 우리는 이 알고리즘을 보완한 RS-트리 기반 점증적 최근접 알고리즘을 제안한다. RS-트리는 R-트리와, 그 보조 트리로서 계층적 시그니쳐 화일을 기반으로 하는 S-트리로 구성된다. S-트리는 R-트리를 탐색하는 과정에서 많은 불필요한 투플을 제거하는 역할을 수행한다. 본 논문에서는 실험을 통해 RS-트리가 Hjaltason과 Samet의 알고리즘의 성능을 향상시킬 수 있음을 보인다.

다국어 초록 (Multilingual Abstract)

In multimedia databases, k-nearest neighbor queries are very popular and include commonly non-spatial predicates. Among the available techniques for such queries, the incremental nearest neighbor algorithm proposed by Hjatason and Samet is known as the most useful algorithm[1]. The reason is that if k' > k neighbors are needed, it can provide the next neighbor for the upper operator without restarting query from scratch. However in their algorithm, the R-tree has no facility capable of partly pruning tuple candidates that will turn out not to satisfy the remaining predicates, leading their algorithm to inefficiency. In this paper, we propose an RS-tree-based incremental nearest neighbor algorithm complementary to their algorithm. The RS-tree in our algorithm is a hybrid of the R-tree and the S-tree, as its buddy tree, based on the hierarchical signature file, which participates in pruning a large portion of worthless candidates while traversing the R-tree. Experimental results show that our RS-tree enhances Hjaltason and Samet's algorithm.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 점증적 최근접 알고리즘
• 4. 주요 아이디어(Key Ideas)
• 5. RS-트리를 이용한 점증적 최근접 알고리즘
• 6. 실험 결과
• 7. 결론
• 참고문헌
• 저자소개