An Efficient Method for k Nearest Neighbor Searching in Obstructed Spatial Databases

作者：Gu Yu^*; Yu Ge; Yu Xiaonan

来源：Journal of Information Science and Engineering, 2014, 30(5): 1569-1583.

• nearest neighbor searching
• obstructed space
• location-based service
• Voronoi diagram
• spatial databases

Currently, there has been an increasing development in the area of location-based service. An important type of query in this area is k nearest neighbor (kNN) query, which retrieves the top k nearest neighbors based on the user's position. Although a wide spectrum of work has been conducted on this query type, most of these studies focus on the ideal Euclidean plane without obstacles considered. In this paper, we propose a method to efficiently process kNN queries in the obstructed space. We first present a grid-partition index combined with the obstructed voronoi diagram which can be pre-computed off-line. Furthermore, several pruning methods are designed to search the nearest neighbor efficiently. Also, the incremental kNN query technique is proposed based on our proposed model and index construction. Compared to the R-tree based spatial search methods, the experimental results verify the superior efficiency of our,kNN query processing algorithms based on the real data sets.

• 出版日期2014-9
• 单位东北大学