This thesis presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P` of P such that k nearest neighbors of each object in P` include q and each object in P` has a direction toward q within a pre-defined distance. I formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. My method utilizes a grid-based index to cluster the spatial objects, and the B+tree to index the direction angle. I adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than the pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. From extensive experiments, I show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time.
본 학위논문에서는 방향성을 고려하는 이종데이터 상의 역최근접 질의를 제안한다. 공간 데이터 집합 P와 S, S 집합에 속해있는 질의 객체 q가 주어졌을 때, DBRkNN 질의는 q 객체를 최대 k번째 최근접 객체로 여기고 방향이 q 객체로 향해있으며 사전에 정의된 거리 내에 소유하는 모든 부분집합 P`을 반환한다. 본 학위논문에서는 DBRkNN 질의를 정의하고, DART라는 DBRkNN 질의를 처리하기 위한 효율적인 알고리즘을 제안한다. DART는 그리드 기반의 색인을 하여 공간 객체들을 클러스터하고 B+트리를 이용하여 방향을 색인한다. 역최근접 질의 처리에서 자주 사용되는 Filter-refinement 프레임워크를 적용하였다. Filtering 단계에서는 사전에 정의된 거리보다 질의 객체로부터 멀리 떨어진 객체를 제외하고, 또한 올바르지 않은 방향을 가진 객체도 제외한다. Refinement 단계에서는 남겨진 객체들에 대해서 실제로 각 객체가 질의 객체를 최대 k번째 최근접 객체로 여기는지를 확인한다. 실험을 통해서 DART 알고리즘이 R 트리 기반의 나이브 알고리즘보다 색인과 질의 처리부분에서 더 효율적임을 보였다.
