空间数据库中反最近邻查询技术的研究

摘要

空间查询是空间数据库相关技术研究的重点和难点，反最近邻查询技术已经成为空间查询领域的热点课题。目前反最近邻查询技术的研究还处于起步阶段，各方面的技术还不成熟，存在一定的缺陷。本文对反最近邻查询进行了综合分析，在此基础上提出了新的查询方法，具体内容如下。 1.对反最近邻查询技术进行了研究，提出了Cutting裁剪算法，进一步将反最近邻查询划分为过滤与提纯两阶段，给出了反最近邻查询过滤阶段与提纯阶段的算法，然后对算法的正确性进行了论述，并用实例对算法进行了分析说明。 2.对反k最近邻查询技术进行了研究，给出了k-Cutting裁剪算法，进一步针对反k最近邻查询自身的特点，将反最近邻查询算法推广到反k最近邻查询，给出了适用于反k最近邻查询的算法。 3.对特定维上的反最近邻查询技术进行了研究，提出了适用于特定维上反最近邻查询的数据模型，基于该数据模型，提出了划分为过滤与提纯两阶段并且不依赖于高维数据索引结构的查询算法。 4.对上述算法进行了实验验证，通过对实验结果的分析比较，可以看出本文提出的反最近邻查询算法能够较好地完成查询任务，反k最近邻查询算法在k值较大时，效率上的优势更加明显，特定维上的反最近邻查询算法在处理高维数据时，体现了良好的性能。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景

1.2研究现状

1.3研究内容

1.4研究意义

1.5本文组织结构

第2章基础知识

2.1引言

2.2空间数据

2.3空间索引

2.3.1空间索引的分类

2.3.2 R树

2.4空间查询

2.4.1空间选取

2.4.2空间结合

2.4.3最近邻查询和反最近邻查询

2.5本章小结

第3章反最近邻查询技术

3.1引言

3.2基本定义

3.3反最近邻查询算法

3.3.1 Cutting裁剪算法

3.3.2过滤阶段的TSJ-filter算法

3.3.3提纯阶段的TSJ-refine-round算法

3.3.4提纯阶段的TSJ-refine算法

3.3.5实例分析

3.3.6算法分析

3.4本章小结

第4章反k最近邻查询技术

4.1引言

4.2反k最近邻查询算法

4.2.1裁剪方案

4.2.2 k-Cutting裁剪算法

4.2.3过滤阶段的k-TSJ-filter算法

4.2.4提纯阶段的k-TSJ-refine-round算法

4.2.5提纯阶段的k-TSJ-refine算法

4.3本章小结

第5章特定维上的反最近邻查询技术

5.1引言

5.2 Voronoi单元的计算

5.2.1坐标轴截点逼近法

5.2.2层次网格逼近法

5.3过滤阶段的TSK-filter算法

5.3.1数据模型

5.3.2 TSK-filter算法

5.4提纯阶段的TSK-refine算法

5.4.1 TSK-refine算法的主要思想

5.4.2 TSK-refine算法描述

5.5本章小结

第6章算法的实验验证

6.1引言

6.2验证反k最近邻查询技术

6.2.1实验设置

6.2.2实验结果分析

6.3验证特定维上的反最近邻查询技术

6.3.1实验设置

6.3.2实验结果分析

6.4本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介