Study On Reverse K-Nearest-Neighbor Query Techniques In Obstructed Spatial Databases

With the rapid development of location-based services (LBS) and the Internet of Things in recent years, technologies for spatial queries are becoming more and more important. Moreover, nearest queries and the variant are among the most widely used spatial queries, such as range query, skyline query and reverse k-nearest-neighbor query. Among these queries, reverse k-nearest-neighbor query retrieves all the points that have q as their k nearest neighbors, which has received considerable attention due to its importance in a wide range of applications, such as spatial decision support, profile-based marketing, resource allocation, etc. However, these studies are proposed for the ideal Euclidean Space and Road Network Space. Queries for reverse k nearest neighbors are influenced by obstacles such as buildings and lakes in practice.Taking into account those problems raised above, this paper focuses on study on reverse k-nearest-neighbor queries techniques in obstructed spatial databases.Firstly, in order to solve the problem that obstacles are invisible and the snapshot query point is stationary, our paper first gives the formal definition of reverse k-nearest-neighbor queries for a stationary point, then propose efficient pruning algorithms based on an obstructed Voronoi diagram. Our experiments based on real and synthetic data sets demonstrate the efficiency and accuracy of our proposed approach.Secondly, this thesis improves the above algorithms by proposing ORkNN algorithm in the case of a dynamic given query point. ORkNN algorithm first indexes data points by grids and locates the dynamic query point by efficient pruning strategy, and then constructs a new obstructed Voronoi cell locally and processes the obstructed reverse k-nearest-neighbor queries using our previous pruning and update policies. Plentiful experimental work proves that our ORkNN algorithm has high effectiveness and efficiency.Finally, considering the continuously moving users’queries, we raise a problem of reverse k-nearest-neighbor continuous queries in obstructed spatial databases. Our paper make a research on the issue that is how to compute its control points and split points after a query point becoming a query path, and then update our result list. Experiments show that our proposed algorithms have superiority on efficiency and accuracy.