基于Voronoi图的连续反向最近邻查询  

Continuous Reverse Nearest Neighbor Search Based on Voronoi Diagram

作　　者：杨泽雪[1,2] 郝忠孝[1,3] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]黑龙江工程学院计算机科学与技术系,哈尔滨150050 [3]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程》2014年第1期272-274,279,共4页Computer Engineering

基　　金：黑龙江省教育厅科学技术研究基金资助项目(12521442)

摘　　要：为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。In order to solve continuous reverse nearest neighbor query of moving points in dynamic environment, continuous reverse nearest neighbor query is divided into monochromatic and bichromatic study. By using Voronoi diagram of moving points, monochromatic continuous reverse nearest neighbor and bichromatic continuous reverse nearest neighbor query algorithm are given. The relevant theorem and proof of the algorithm＇s correctness and termination are given, and its time complexity analysis is presented. According to whether the topology of the Voronoi diagram of moving points changes, it has two categories： change and no change. By analysis of candidate region changes in each category, Voronoi diagram is reconstructed in change region, and corresponding solutions are given. In most cases, the query results can be found only needing generate Voronoi diagram of local moving points. It can reduce the cost of continuous reverse nearest neighbor queries.

关 键 词：连续反向最近邻查询 空间数据库 空间查询 VORONOI图 拓扑结构 反向最近邻 

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