ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (4): 861-871.doi: 10.7544/issn1000-1239.2017.20151111

• 软件技术 • 上一篇    下一篇

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

张丽平1,刘蕾1,郝晓红1,李松1,郝忠孝1,2   

  1. 1(哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080); 2(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) (zhanglptg@163.com)
  • 出版日期: 2017-04-01
  • 基金资助: 
    国家自然科学基金项目(61370084);黑龙江省自然科学基金项目(F201302);黑龙江省教育厅科学技术研究项目(12531z004)

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

Zhang Liping1, Liu Lei1, Hao Xiaohong1, Li Song1, Hao Zhongxiao1,2   

  1. 1(School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080); 2(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Online: 2017-04-01

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

关键词: Voronoi图, 组反k最近邻, 障碍空间, 空间数据库, 动态查询

Abstract: In order to solve the problem that the existing methods can not deal with the group reverse k nearest neighbor (GRkNN) query in obstructed space, the group reverse k nearest neighbor query method (OGRkNN) 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, OGRkNN query can be used to evaluate the influence of a group of query objects. According to the changes of the obstacle set, the OGRkNN query in static obstacle environment (STA_OGRkNN query) and the OGRkNN query in dynamic obstacle environment (DYN_OGRkNN query) are given. The STA_OGRkNN query method greatly reduces the number of non-candidates by the properties of Voronoi diagram in pruning stage, and reduces the searching ranges quickly, which improves query efficiency. It also improves the accuracy of the algorithm in refining stage. Then three DYN_OGRkNN query algorithms are given. They are the OGRkNN query algorithm under the condition of dynamically increasing obstacles, the OGRkNN query algorithm under the condition of dynamically reducing obstacles and the OGRkNN query algorithm under the condition of dynamically moving obstacles. Theoretical study and experiments show that the proposed algorithms have extremely high efficiency.

Key words: Voronoi diagram, group reverse k nearest neighbor (GRkNN), obstructed space, spatial database, dynamic query

中图分类号: