空间数据库中的障碍反向最近邻查询  

Obstructed reverse nearest neighbor queries in spatial databases

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

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

出　　处：《计算机工程与应用》2011年第34期130-133,共4页Computer Engineering and Applications

基　　金：黑龙江省教育厅2011年度科学技术研究项目(No.12511102)

摘　　要：反向最近邻查询已成为空间查询的热点问题,而障碍物在实际应用中是不可避免的,因而在障碍物环境中的反向最近邻查询也成为重要的空间查询。已有的可视反向最近邻查询只考虑了可视性,并没有考虑最小障碍距离。提出一种障碍物环境中新的反向最近邻查询的变体,查找障碍距离最小的反向最近邻,即障碍反向最近邻查询。利用障碍距离的计算和相应的剪枝规则,给出障碍反向最近邻查询的算法及相关定理和证明。Reverse Nearest Neighbor（RNN） query has been a hot subject of spatial query.In the real world,obstacles are not avoided,so the RNN query which considers the obstacle existed has become an important spatial query.The existed visible RNN only considers the visibility and does not take obstructed distance into consideration.This paper introduces a novel variant of RNN queries,the Obstructed Reverse Nearest Neighbor（ORNN） search,which finds the RNN with the shortest obstructed distance among the obstacles.By using the computation of obstructed distance and the related pruning heuristics,the ORNN query processing algorithm is proposed,and the relevant theorem and proof are given.

关 键 词：反向最近邻 空间数据库 可视性 障碍距离 

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