障碍环境下线段反k最近区域查询方法研究  

Research on Line Reverse k Nearest Region Query Method in Obstacle Environment

作　　者：张丽平[1] 任玲玲 郝晓红[1] 李松[1] ZHANG Liping;REN Lingling;HAO Xiaohong;LI Song(College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)

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

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

基　　金：国家自然科学基金No.61370084;黑龙江省教育厅科学技术研究项目No.1253lz004~~

摘　　要：反k最近区域查询问题是近邻查询领域的一个新问题,为了弥补现有的研究成果无法有效地处理障碍空间下的线段反k最近区域查询问题,提出了在障碍环境下基于Voronoi图的线段反k最近区域查询方法。在实际中主要应用于评估查询对象的影响力。该方法首先对数据区域集进行约减,缩减了查询的搜索范围。然后根据剪枝过程所提定理对候选集进行过滤,获得更精确的候选集。最后基于Voronoi图的性质提出相关定理,精炼OLRk NR(obstacle line reverse k nearest region)查询的结果集。所提方法根据Voronoi图特性在剪枝、精炼过程中提升了查询速度和查询准确率。理论研究和实验表明,所提方法可以有效处理障碍环境下基于线段的反k最近区域查询问题。The reverse k nearest region query is a new problem.In order to make up for the existing research results which can not effectively deal with the line reverse k nearest region query problem in the obstacle space,this paper proposes the reverse k nearest region query of line segment method based on Voronoi graph in obstacle environment.In practice,it is mainly used to evaluate the influence of query objects.Firstly,the method reduces the data region set and reduces the search range of the query.Then,based on the theorem of the pruning process,it filters the candidate set to obtain more accurate candidate selections.Finally,according to the nature of the Voronoi graph,some related theorems are proposed to refine the result set of OLRkNN(obstacle line reverse k nearest neighbor)query.This method greatly changes the query speed and query accuracy in the process of pruning and refining according to the characteristics of the Voronoi graph.Theoretical studies and experiments show that the proposed method can effectively deal with the problem of the reverse k nearest region query based on line segment in obstacle environment.

关 键 词：障碍空间 VORONOI图 线段 反k最近区域 

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