空间数据库K最接近对查询算法的研究

摘要

目前，空间数据库已广泛地应用于地理信息系统(GIS)、医学图像和计算机辅助设计与制造(CAD/CAM)等多个领域。由于其庞大的空间数据量以及空间物标、空间查询的高度复杂性，空间查询成为空间数据库应用的难点和研究热点。
　　 所谓K最接近对查询(K-CPQ)，就是在两个空间数据集中进行检索查询，以得到距离最接近的K个物标对。K-CPQ是空间连接查询和最近邻查询的结合体，它既可以像连接查询给出所有的待选物标对，也可以像最近邻查询，依据裁剪原则和更新策略查找距给定物标最近的物标。K-CPQ在决策制定和数据挖掘等方面有重要的应用。
　　 本文针对空间数据库在约束条件下的K最接近对查询算法开展研究，拟解决约束空间中的空间数据搜索和匹配问题：
　　 首先，本文分析了空间数据和空间索引的特点、空间存取机制的基本需求，分析常用的空间索引技术，重点分析了R树索引技术；
　　 其次，面向水上空间数据组织与管理，分析了S-57数据组织结构，在建立水上空间数据库逻辑结构的基础上，建立R树空间索引；
　　 再次，针对K最接近对查询问题中的主树剪裁策略和更新策略，给出基于距离排序递归算法、平面扫描递归算法和平面扫描迭代算法的约束下K最接近对查询算法。算法能够动态地调整距离阈值，对搜索路径进行裁剪，避免不必要的计算量。
　　 最后，对给出的三种约束下K最接近对查询算法进行了评价。

目录

文摘

英文文摘

声明

第一章 绪论

1.1研究的背景、目的与意义

1.2国内外研究现状

1.2.1 GIS及空间数据库的发展现状

1.2.2空间数据库K最接近对查询研究现状

1.3论文研究内容及章节安排

第二章 空间数据及索引技术

2.1空间数据及索引技术的特征

2.1.1空间数据的特征

2.1.2空间索引结构的特征

2.1.3空间存取机制的基本要求

2.1.4空间数据的目标近似

2.1.5基于目标近似的空间检索过程

2.2常用索引技术比较

2.2.1二叉树索引技术

2.2.2 B树索引技术

2.2.3四叉树索引技术

2.2.4 R树索引技术

第三章 水上空间数据的组织与管理

3.1 S-57标准的数据组织结构分析

3.2水上空间数据组织和管理

3.3基于R树的空间数据库索引建立

第四章 K最接近对查询算法的研究

4.1预备知识

4.1.1 K-CPQ定义

4.1.2 MBR对函数

4.2约束K最接近查询算法

4.2.1约束K最接近对查询定义

4.2.2相关函数

4.2.3裁剪原则和更新策略

4.2.4约束K最接近对查询算法

4.3算法评价

第五章 总结与展望

5.1本文总结

5.2对未来工作的展望

参考文献

致谢

研究生履历