论文部分内容阅读
随着智能交通和地理信息系统的飞速发展,空间数据库查询技术得到了广大学者的关注。其中,反向最远邻查询是从数据点集中查找将目标点作为其最远邻的数据点,用来获取目标点的弱影响集,其研究成果被广泛应用于设施选址、抗震救灾、市场营销等重大领域,由此可见,反向远邻查询技术具有极其重要的研究意义与实用价值。然而,针对现实情境中多个目标点的反向最远邻查询问题,已有的研究成果都存在一定的局限性,为此,本文提出了欧式空间中组反向最远邻查询和障碍空间中组反向k远邻查询这两类问题,并展开了深入的探讨,主要研究内容论述如下。首先,提出了基于欧式空间中的组反向最远邻查询的概念以及基于最小覆盖圆的组反向最远邻查询算法(Circle-Group Reverse Farthest Neighbors,C-GRFN)。该算法首先获取查询点集的最小覆盖圆及其圆心,将所有查询点集看作一个整体进行考虑,减少了对查询点集的访问;其次通过基于四分邻域区和P-ray的剪枝策略进行数据点集的过滤;最后利用反范围查询算法进行精炼,约减数据集,获取最终结果,有效的解决了欧式空间中的组反向最远邻查询问题。其次,将组反向最远邻查询的概念延伸到障碍空间中,提出了障碍空间中组反向k远邻查询的定义,并给出了一种基于Voronoi图的查询优化算法(Voronoi-Obstacle Group Reverse k Farthest Neighbors,V-OGRkFN),该算法首先利用最小覆盖圆算法对组查询问题进行优化,并对数据点集构建Voronoi图索引,通过基于Voronoi图性质的剪枝策略过滤数据点集,并借助反k近邻与反k远邻之间的转化关系获取候选集,最后通过精炼算法将候选集中的点集进行提纯,提高了查询的精确性,解决了障碍空间中组反向k远邻查询的问题。最后,针对上述算法分别进行实验对比验证。其中,欧式空间中的组反向最远邻查询算法从数据集容量、查询点集大小以及数据的空间分布等方面出发设计对比实验;障碍空间下的组反向k远邻查询算法从数据集容量、查询点集大小、障碍物集合大小、k值以及障碍率等角度出发设计对比实验。实验结果表明所提算法均具有良好的查询性能。