.png){kind=icon}
.png){kind=icon}
Return
Range-Based Nearest Neighbor Queries with Complex-Shaped Obstacles
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2017.2779487.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 of continuous obstructed nearest-neighbor (CONN), anRONNquery retrieves a set of obstructed nearest neighbors corresponding 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 ofOB-tree lies in the idea of dividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an algorithmfor construction of the OB-tree and propose a space division scheme, called optimal obstaclebalance(OOB2) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, called RONN 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 NNqueries 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 theRONN-OBA algorithmoutperforms the two R-tree based algorithms and RONN-OA significantly.
Keywords:
Nearest neighbor
range-based nearest neighbor
obstacle
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W