空间数据库中基于Voronoi图的组反k最近邻查询

来源：计算机科学与探索杂志2016年第10期北京时间：

作者：张丽平，刘蕾，李松，于嘉希

单位：哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

摘要：为了改进现有的组反k最近邻查询算法的查询速度与准确度，提出了一种基于Voronoi图的组反k最近邻查询方法（group reverse k nearest neighbor guery method based on Voronoi diagram，V_GRkNN）。该方法获得的结果集是将这组查询点中任意一点作为kNN的数据点集合，在实际应用中可以用来评估一组查询对象的影响力。该方法的特点是首先对查询点集Q进行优化处理，降低查询点数量对查询效率的负面影响；接着对数据点集P进行约减，缩小查询搜索范围；然后根据基于Voronoi图的剪枝策略对候选集进行过滤；最后经过精炼获得GRkNN查询的结果集。该方法在数据集处理阶段很大程度上提高了查询速度，在过滤、精炼阶段利用Voronoi图的特性提高了查询的准确性。理论研究和实验表明，所提方法的效率明显优于可选的已有方法。

关键词：Voronoi图,反k最近邻,组反k最近邻,索引结构