Range-Based Nearest Neighbor Queries with Complex-Shaped Obstacles
Huaijie Zhu, Xiaochun Yang, Bin Wang, Wang-Chien Lee · IEEE Transactions on Knowledge and Data Engineering · 2017
In this paper, we study a novel variant of obstructed nearest neighbor queries, namely,range-based obstructed nearest neighbor(RONN) search. As a natural generalization ofcontinuous obstructed nearest-neighbor(CONN), an RONN query retrieves a set ofobstructed nearest neighborscorresponding to every point in a specified range. We propose a new index, namely binary obstructed tree (calledOB-tree), for indexing complex objects in the obstructed space. The novelty of OB-tree lies in the idea ofdividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an algorithm for construction of the OB-tree and propose a space division scheme, calledoptimal obstacle balance(OOB2) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, calledRONN by OB-tree Acceleration(RONN-OBA), which exploits the OB-tree and a binary traversal order of data objects to accelerate query processing of RONN. In addition, we extend our work in several aspects regarding the shape of obstacles, and range-based$k$NN queries in obstructed space. At last, we conduct a comprehensive performance evaluation using both real and synthetic datasets to validate our ideas and the proposed algorithms. The experimental result shows that the RONN-OBA algorithm outperforms the two R-tree based algorithms and RONN-OA significantly.