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.%随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象(RkNN)的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种基于障碍Voronoi图的高效的剪枝方法.根据Voronoi图和障碍距离的特性,大幅度减少了数据点处理个数.最后,作者使用真实的数据集和多种方式分布的模拟数据,验证了算法的高效性和准确性.
展开▼
