最近邻查询和反最近邻查询算法研究

摘要

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

目录

文摘

英文文摘

声明

第1章绪论

1.1研究目的及意义

1.2国内外研究现状分析

1.2.1最近邻查询现状分析

1.2.2反最近邻查询现状分析

1.3最近邻查询和反最近邻查询的应用

1.4课题来源

1.5本文主要研究内容

1.6本章小结

第2章基础知识

2.1最近邻查询的分类及其定义

2.2反最近邻查询的定义及性质

2.2.1反最近邻查询的定义

2.2.2反最近邻查询的性质

2.3 R-树及其变种

2.3.1 R-树

2.3.2 R+-树

2.3.3 R+-树

2.4 Voronoi图

2.4.1Voronoi图的定义

2.4.2Voronoi图的性质

2.5构造Voronoi图的算法

2.6本章小结

第3章最近邻查询算法

3.1静态最近邻查询及K最近邻查询算法

3.1.1距离度量

3.1.2基于R-树的深度优先(DF)算法

3.1.3基于R-树的最佳优先(BF)算法

3.2动态最近邻查询算法

3.3连续最近邻查询算法

3.4本章小结

第4章反最近邻查询算法

4.1反最近邻查询算法

4.1.1基于RNN-树的反最近邻查询算法

4.1.2基于Rdnn-树的反最近邻查询算法

4.2基于Voronoi图及其对偶图的反最近邻查询算法

4.2.1算法思路

4.2.2算法描述

4.2.3算法分析

4.3基于Voronoi图的反最近邻查询算法

4.3.1算法思路

4.3.2算法描述

4.3.3算法分析

4.3.4处理新增点对反最近邻查询的影响

4.3.5处理删除点后对反最近邻查询的影响

4.4本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢