空间数据库中的组障碍最近邻查询研究

Group Obstacle Nearest Neighbor Query in Spatial Database

已有的关于组最近邻查询的研究都是基于欧氏距离的,无法解决存在障碍情况下基于障碍距离的组最近邻查询问题.为此,提出障碍物环境中组最近邻查询的一种新的变体,即组障碍最近邻(group obstacle nearest neighbor,GONN)查询.GONN返回数据集中与查询点集中所有点的障碍距离之和最小的点.根据数据集中的点与查询点集的最小外包距离(minimum bounding rectangle,MBR)之间的不同位置关系,构造各种情况下查询点集的MBR相对于数据集中点的剪枝区域.利用剪枝区域剪去障碍集中对障碍距离计算无影响的障碍,给出数据集中点与查询点集之间障碍距离的计算算法.定义组障碍最近邻查询的剪枝规则,根据障碍距离计算给出组障碍最近邻查询的算法.并给出相关定理和证明.实验结果证明算法具有较高效率.

Existing research work on group nearest neighbor query is based on Euclidean distance, which can not solve the nearest neighbor query problem based on obstructed distance in the case of presence of obstacles. A new variant of group nearest neighbor query in obstacle environments is proposed, that is, group obstacle nearest neighbor query. It retrieves a data point from dataset with the smallest sum of obstructed distances to all query points. According to the different positional relationships between a point in the dataset and MBR of query points, the pruning regions for MBR of query points to the point in the dataset in various circumstances are constructed. By using the pruning regions, the obstacles of no effect on obstructed distance calculation are cut. And the obstructed distance calculation algorithm between the point in the dataset and query points is given. The pruning rules of group obstacle nearest neighbor query are defined, which contain the Euclidean distance pruning rules and obstructed distance pruning rules. The GONN algorithm for group obstacle nearest neighbor query is put forward, which is based on the BF traversal of R-tree for dataset and combines the pruning rules and the obstructed distance calculation algorithm. The proofs of the algorithm＇s correctness and termination are brought forward, and time complexity analysis is given. Experimental results show that the algorithm has high efficiency.