障碍空间中基于Voronoi图的组反k最近邻查询研究

Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space

为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.

In order to solve the problem that the existing methods can not deal with the group reverse k nearest neighbor(GR^NN)query in obstructed space,the group reverse k nearest neighbor query method(OGR^NN)in obstructed space based on Voronoi diagram is put forward.The method finds data points that take any point in the query objects set as one of their obstacle k nearest neighbors.In the practical application,OGR^NN query can be used to evaluate the influence of a group of query objects.According to the changes of the obstacle set,the OGR^NN query in static obstacle environment(STA OGR^NN query)and the OGR^NN query in dynamic obstacle environment(DYN_OGR^NN query)are given.The STA_OGR^NN query method greatly reduces the number of non-candidates by the properties of Voronoi diagram in pruning stageand reduces the searching ranges quickly,which improves query efficiency.It also improves the accuracy of the algorithm in refining stage.Then three DYN_OGR^NN query algorithms are given.They are the OGR^NN query algorithm under the condition of dynamically increasing obstacles,the OGR^NN query algorithm under the condition of dynamically reducing obstacles and the OGR^NN query algorithm under the condition of dynamically moving obstacles.Theoretical study and experiments show that the proposed algorithms have extremely high efficiency.