障碍环境中可视反向视域K最近邻查询  

Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment

作　　者：杨泽雪 王阿川[1] 李陆[3] 李松 YANG Zexue;WANG Achuan;LI Lu;LI Song(College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China;Department of Computer Science and Technology,Heilongjiang Institute of Technology,Harbin 150050,China;Heilongjiang Provincial Big Data Center of Government Affairs,Harbin 150028,China;College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China)

机构地区：[1]东北林业大学信息与计算机工程学院,哈尔滨150040 [2]黑龙江工程学院计算机科学与技术系,哈尔滨150050 [3]黑龙江省政务大数据中心,哈尔滨150028 [4]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机工程》2022年第8期258-265,共8页Computer Engineering

基　　金：中国博士后科学基金(2019M651318);黑龙江省自然科学基金(LH2020F047);黑龙江省高等教育教学改革重点委托项目(SJGZ20200145);黑龙江工程学院创新团队项目(2020CX07)。

摘　　要：在障碍环境下的空间应用中,用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题,将视域可视性引入到反向K最近邻查询中,提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q,可视反向视域K最近邻查询检索P中数据点,并将q作为可视视域K最近邻。应用查询点进行障碍过滤,得到障碍过滤算法,利用数据对象的视域进行剪枝,使用查询点与数据对象的关系剪枝,形成有效的障碍剪枝规则,并根据剪枝规则得到视域可视性判断算法。在此基础上,分别基于R^(*)-树和VFR-树提出可视反向视域K最近邻查询算法R^(*)-V2-RKNN和VFR-V2-RKNN,并分别通过对R^(*)-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明,VFR-V2-RKNN算法的查询性能明显优于R^(*)-V2-RKNN算法。In spatial applications used in obstacle environments,users are usually only interested in visible data objects within the field of view.To solve the problem of a reverse nearest-neighbor query within the field of view in an obstacle environment,view field visibility is introduced into the Reverse K-Nearest Neighbor(RKNN)query,and a Visible Reverse View Field K-Nearest Neighbor(V2-RKNN)query algorithm is proposed.The query considers both the visibility and view field,which makes up for the deficiency in which the existing query only considers one aspect.Given a spatial data set P,an obstacle set O,and a query point q,the V2-RKNN query retrieves the data points in P that have q as their visible view field K-nearest neighbor.First,a query point is used for obstacle filtering to obtain the obstacle filtering algorithm.The view field of the data object is then used for pruning,and the relationship between the query point and data object is applied to the pruning to form effective obstacle pruning rules,based upon which a view field visibility judgment algorithm is achieved.On this basis,two visible reverse view field K nearest neighbor algorithms,R^(*)-V2-RKNN and VFR-V2-RKNN,based on an R^(*)-tree and VFR-tree,respectively,are developed.The two algorithms obtain their query results through one traversal of an R^(*)-tree and VFR-tree,respectively,and the query efficiency of the VFR-V2-RKNN algorithm is verified experimentally on real and synthetic data sets.

关 键 词：障碍 可视性 视域 反向K最近邻查询 空间查询 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]