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

k Nearest Neighbor Query Based on Voronoi Diagram for Obstructed Spaces

作　　者：张丽平[1] 经海东 李松[1] 崔环宇[1] 

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

出　　处：《计算机科学》2016年第5期174-178,187,共6页Computer Science

基　　金：国家自然科学基金资助项目(61370084);黑龙江省自然科学基金资助项目(F201302);黑龙江省教育厅科学技术研究项目(12541128;12531z004)资助

摘　　要：为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。In order to enhance the efficiency of k nearest neighbor in obstructed spaces,k nearest neighbor query method based on Voronoi diagram in obstructed spaces was studied,and kNN-Obs algorithm based on Voronoi diagram in obstructed spaces was proposed.This algorithm adopts two processes：filtration and refinement.Filtration mainly uses the filter function of Voronoi diagram and largely reduces the number of query points.Refinement mainly screens objects within the candidate set according to barrier distance and Voronoi neighbor.And further ADDkNN-Obs algorithm for newly-added points and DENkNN-Obs algorithm for deleted points were given.The experiment shows that the algorithm has advantages in dealing with the k nearest neighbor problem in obstructed spaces.

关 键 词：VORONOI图 k最近邻查询(kNN) 障碍空间 障碍距离 

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