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

论文摘要

随着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.实现基于混合聚类的空间索引,并给出实验数据和分析,并将研究成果应用于东莞市水资源管理系统中。

论文目录

• 摘要
• ABSTRACT
• 第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 小结
• 结论
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文及科研成果