A Method for Reverse k-Nearest-Neighbor Queries in Obstructed Spaces
Yu Xiao · Chinese Journal of Computers · 2011
With the rapid development of location-based services(LBS) and the Internet of Things,technologies for spatial queries are becoming more and more important.Moreover,nearest neighbor queries and the variant are widely used spatial queries.Recently,there has been much work on reverse k nearest neighbors(RkNN) queries.However,these studies are proposed for the ideal Euclidean Space.Queries for reverse k nearest neighbors are influenced by obstacles in practice.In this paper,we study a method for reverse k nearest neighbors queries in obstructed spaces,and propose efficient pruning algorithms based on an obstructed Voronoi diagram.Furthermore,these pruning methods greatly reduce the number of searched points by properties of Voronoi diagrams and obstructed distance.Finally,our experiments based on real and synthetic data sets demonstrate the efficiency and accuracy of our proposed approach.