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

Obstructed reverse nearest neighbor queries in spatial databases

反向最近邻查询已成为空间查询的热点问题,而障碍物在实际应用中是不可避免的,因而在障碍物环境中的反向最近邻查询也成为重要的空间查询。已有的可视反向最近邻查询只考虑了可视性,并没有考虑最小障碍距离。提出一种障碍物环境中新的反向最近邻查询的变体,查找障碍距离最小的反向最近邻,即障碍反向最近邻查询。利用障碍距离的计算和相应的剪枝规则,给出障碍反向最近邻查询的算法及相关定理和证明。

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.