Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

@

Journal of Information Science and Engineering, Vol. 30 No. 4, pp. 1569-1583 (September 2014)


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


YU GU, GE YU AND XIAONAN YU
College of Information Science and Engineering
Northeastern University
Shenyang, 100819 P.R. China 

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.

Keywords: nearest neighbor searching, obstructed space, location-based service, Voronoi diagram, spatial databases

Full Text () Retrieve PDF document (201409_15.pdf)

Received October 9, 2012; revised February 4 & March 25, 2013; accepted April 15, 2013.
Communicated by Jan-Jan Wu.
* This work was supported by National Natural Science Foundation of China (61003058) and the Fundamental Research Funds for the Central Universities (N130404010).