一种障碍空间中的反k最近邻查询方法

摘要

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