基于混合聚类的空间索引算法研究及应用

摘要

随着Internet技术和GIS(Geographical Information System，地理信息系统)技术的发展，WebGIS成为GIS领域研究的热点。利用网络技术，依托空间数据库，通过与浏览器的交互，WebGIS使不同地区的客户端实现图形及属性数据的查询与检索。由于空间数据本身的复杂性和海量性，实现对海量空间数据快速查询必须使用索引技术，选择高效的索引技术是提高空间数据库和GIS性能的重要方法。
　　 R树的生成过程是个典型的空间聚类问题，利用混合聚类算法将相邻或相近的对象聚集在一起，将聚类后的数据使用Hilbert分形曲线进行线性排序，在此基础上生成Hilbert R树。根据这个思路，提出了一种基于混合聚类的高性能空间索引算法。实验证明，该算法虽然增加了存储开销，但是缩短了在空间数据库上执行空间查询的响应时间，明显加快了搜索速度，改善了查询性能。
　　 论文的主要内容如下：
　　 1.详细分析了R树和R树改进算法的结构，构造原理和查询过程，重点研究插入新的空间对象导致的结点分裂算法，以及分析了它们的适用范围和存在的问题；
　　 2.分析K-means聚类技术的缺陷，对经典的算法进行了部分扩充和改进，提出了面向Hilbert R树的混合聚类算法；
　　 3.提出对空间对象聚集的区域和稀疏的区域分别处理；
　　 4.将混合聚类技术引入R树的生成过程中，提出一种基于混合聚类的空间索引算法。在R树的生成过程中，采用混合聚类的思想对空间对象进行预处理，将相邻或相近的对象聚集在一起组成R-树的结点。它能获得比一般R树更小的结点覆盖区域，具有更高的检索效率以及与R树相差无几的建树时间，最后给出基于混合聚类的空间索引算法流程；
　　 5.实现基于混合聚类的空间索引，并给出实验数据和分析，并将研究成果应用于东莞市水资源管理系统中。

目录

文摘

英文文摘

声明

第1章 绪论

1.1课题背景及研究意义

1.2国内外研究现状

1.3本文的研究内容及研究方法

1.4论文的组织

第2章空间数据查询技术

2.1 空间数据

2.2空间数据库

2.3空间数据存储

2.3.1二进制大对象存储(BLOB)

2.3.2结构化存储

2.3.3关系拓扑存储

2.4空间数据管理方法

2.5 小结

第3章几种典型的空间索引算法分析和比较

3.1 空间索引分类

3.2 R-Tree索引算法

3.2.1 R-Tree的索引结构

3.2.2 R-Tree的索引操作

3.2.3 R-Tree索引算法评价

3.3 R+树索引

3.4 R*树索引算法

3.4.1 R*树索引操作

3.4.2 R*树索引算法评价

3.5 小结

第4章基于混合聚类的空间索引算法

4.1 混合聚类相关算法

4.1.1 K-means算法

4.1.2 K-medoids算法

4.1.3混合聚类算法

4.2 Hilbert R树索引

4.2.1 Hilbert曲线

4.2.2 Hilbert R树

4.2.3 Hilbert R树的生成

4.2.4 Hilbert R树的算法评价

4.3基于混合聚类的Hilbert R-Tree索引算法

4.3.1算法改进思路

4.3.2索引类的设计

4.3.3实验结果与分析

4.3.4性能评估

4.4小结

第5章 改进算法在水资源管理系统中的应用

5.1系统目标和功能

5.2综合数据库设计

5.2.1综合数据库功能

5.2.2 GIS空间数据存储

5.2.3结构化数据存储

5.3地理信息显示平台

5.3.1业务需求

5.3.2功能模块

5.4空间查询

5.4.1 点查询

5.4.2区域查询

5.4.3组合查询

5.5小结

结论

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果