다양한 유형의 공간객체를 위한 R<SUP>m</SUP>-tree 기반의 mkNN 질의처리기법 = mkNN Query Processing Method based on Rm-tree for Spatial Objects with Multi-types

국문 초록 (Abstract)

본 논문에서는 다양한 유형의 위치기반 데이터들을 하나의 R-트리로 통합한 Rm-트리구조와 이 Rm-트리를 이용하여 질의포인트로부터 각 유형별로 k개의 가까운 위치기반 데이터를 찾는 mkNN(multi-type k Nearest Neighbor) 질의처리기법을 제안하였다. 특히, 다양한 유형의 위치기반 데이터들을 각 유형별로 독립된 R-트리로 유지하지 않고, 하나의 Rm-트리로 통합하여 관리함으로써 mkNN 질의처리시 같은 레벨의 공간의 반복탐색을 줄일 수 있도록 하였다. 그리고 각 유형에 대한 위치데이터를 관리하는 부가적인 유형정보 자료구조로서 위치데이터들을 포함하는 지역정보를 담은 TMBR(Type Minimum Bounding Rectangle), 데이터 개수정보를 담은 l-entry를 새로이 고안하여 mkNN 질의처리시 효율적인 휠터링(filtering)과 검색과정이 이루어지도록 하였다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose an Rm-tree that integrates with location data of various types. We also propose an efficient mkNN query processing technique based on the Rm-tree that computes to find k nearest neighbors with m types for a given query point p. Especially, our proposed mkNN query processing method is able to reduce the repetitive traversal of the search space to compute multi-type k nearest neighbors. We add TMBR(Type Minimum Bounding Rectangle) and l-entry to Rm-tree to have the efficient filtering and searching performance for the processing of mkNN query.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. Rm-트리구조 및 Rm-트리를 이용한 mkNN 질의처리 알고리즘
• 3. 성능평가
• 4. 결론
• 참고문헌