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

摘要

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

关键词