论文部分内容阅读
空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用,需要研究新的查询处理技术。因此如何提供各种高效的空间与空间对象查询处理技术是当前空间数据库领域的研究热点之一。到目前为止,人们提出了利用不同空间索引结构进行空间数据库查询的多种类型,其中大多数都是基于R-树索引结构的,例如最近邻查询、反最近邻查询、连续最近邻查询、k最近邻查询、动态最近邻查询以及最近对查询等。基于此,本文做了如下工作:首先,本文对最近邻查询进行研究,系统地总结了现有的最近邻查询算法、连续最近邻查询算法、动态最近邻查询算法,并且对其进行分析,然后加以改进。对经典反最近邻查询问题进行研究,掌握了最基本的反最近邻查询方法,在分析该算法的不足的基础上,得到了如下的反最近邻查询算法。其次,通过对基于Voronoi图的最近邻查询问题的研究,引入了基于Voronoi图及其对偶图的反最近邻查询算法,将Voronoi图与Rdnn-树结合,给出了VRdnn-树的定义,先利用此索引结构缩小了在海量空间数据库中进行反最近邻查询的查询范围,然后再利用Voronoi图及其对偶图进行查询,能够大大缩小算法的时间复杂度。最后,给出了基于Voronoi图的反最近邻查询算法,利用Voronoi图及数据集中点的凸包进行反向最近邻查询,通过判断查询点与凸包的位置关系,可去除大量的数据点,并且给出了在数据点被加入或删除后,查询点的反向最近邻变化情况的算法。为了便于查询,设计了相应的空间存储数据结构。上述两种算法都比较适合处理平面及复杂曲面上数据点的反最近邻查询问题,并且对于处理多个查询点的反最近邻问题有明显的优势。