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

Group Reverse k Nearest Neighbor Query Based on Voronoi Diagram in Spatial Databases

作　　者：张丽平[1] 刘蕾[1] 李松[1] 于嘉希 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机科学与探索》2016年第10期1365-1375,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金;No.61370084;黑龙江省自然科学基金;No.F201302;黑龙江省教育厅科学技术研究项目;Nos.12541128;12531z004~~

摘　　要：为了改进现有的组反k最近邻查询算法的查询速度与准确度,提出了一种基于Voronoi图的组反k最近邻查询方法(group reverse k nearest neighbor guery method based on Voronoi diagram,V_GRk NN)。该方法获得的结果集是将这组查询点中任意一点作为kN N的数据点集合,在实际应用中可以用来评估一组查询对象的影响力。该方法的特点是首先对查询点集Q进行优化处理,降低查询点数量对查询效率的负面影响;接着对数据点集P进行约减,缩小查询搜索范围;然后根据基于Voronoi图的剪枝策略对候选集进行过滤;最后经过精炼获得GRk NN查询的结果集。该方法在数据集处理阶段很大程度上提高了查询速度,在过滤、精炼阶段利用Voronoi图的特性提高了查询的准确性。理论研究和实验表明,所提方法的效率明显优于可选的已有方法。To overcome the limitation of query objects in group reverse k nearest neighbor (GRkNN) query, this paper proposes the group reverse k nearest neighbor query method based on Voronoi diagram (V_GRkNN). The proposed method finds data points that take any point in the query objects set as one of their k nearest neighbors. In the practical application, V_GRkNN query can be used to evaluate the influence of a group of query objects. Firstly, the query points set Q is optimized in order to reduce the effect of the query points number on query efficiency, the data points set P is pruned to reduce the searching ranges. And then according to the pruning strategies based on Voronoi diagram,the candidate set is filtered. Finally, a refinement process is used to get the query ?? s final results. The V_GRkNN method greatly improves the query speed and efficiency. Theoretical research and experiments show that the efficiency of the proposed V_GRkNN method obviously outperforms other algorithms.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]