三防决策支持系统中空间索引结构与空间查询算法研究

论文摘要

随着计算机技术的快速发展和社会需求的急剧增长,空间信息系统技术飞速发展,其应用领域在不断扩大。面对海量的空间数据及其复杂的数据特征,如何提高空间数据的查询效率成为当前空间信息系统应用领域研究的重要课题。针对以上问题,本文以三防决策支持系统为背景,在系统空间索引结构以及系统空间查询算法上做了如下工作和贡献:1)系统空间索引的改进。空间索引效率的好环往往从索引的存储效率、查询效率和更新效率等几个方面来衡量。然而,很难设计一种空间索引结构同时使得以上几个方面全部高效。本文根据系统的空间数据类型和功能特性,分析研究各空间索引的效率,通过理论分析构造了一种适合三防决策支持系统的空间索引结构——基于Hilbert编码的固定网格索引。实验证明,该索引结构提高了系统的空间查询效率,优化了系统性能。2)系统空间索引的构建算法设计。系统空间索引结构的构建算法共分三步:划分网格,把整幅地图根据实际情况划分为2的N次方个网格;建立网格索引表,在存储索引信息时,根据网格的行号和列号产生该网格的Hilbert编码作为该网格的唯一标识;遍历所有的图形对象,取出其坐标信息,判断其所在的网格或与之相交的网格,并将相应索引记录插入索引文件。3)最短路径查询算法(Dijkstra)的改进。Dijkstra算法的主要缺点为存储结构和待查询的下一个最近节点。本文主要从以下两方面改进:一是存储结构的改进,采用JAVA框架提供的集合类Hashtable来存储数据,压缩了数据的存储空间;二是执行效率的提高,每次只需更新中间结点所记录的后续点的距离即可,这样可快速提高原算法的执行效率。系统当中只需要得到从起点到终点的最短路径,通过减少循环执行次数,进一步加快空间查询操作的速度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景与意义
• 1.2 国内外研究现状
• 1.3 论文的主要内容及组织结构
• 第2章 三防决策支持系统
• 2.1 项目背景
• 2.2 系统结构
• 2.2.1 系统总体框架
• 2.2.2 系统逻辑结构
• 2.2.3 软件体系结构
• 2.3 系统功能
• 第3章 三防决策支持系统相关技术概述
• 3.1 空间数据结构
• 3.1.1 栅格数据
• 3.1.2 空间矢量数据
• 3.2 空间索引结构
• 3.2.1 基于规则网格的索引结构
• 3.2.2 基于对象的索引结构
• 3.2.3 四叉树索引
• 3.3 空间查询
• 第4章 三防决策支持系统中空间索引结构研究
• 4.1 三防决策支持系统特性分析
• 4.1.1 空间数据类型分析
• 4.1.2 主要功能特性分析
• 4.2 空间索引结构效率研究
• 4.2.1 影响本系统索引结构效率的因素
• 4.2.2 基于规则网格的索引与基于对象索引的比较
• 4.2.3 基于规则网格的索引与其他索引的比较
• 4.3 系统空间索引的改进
• 4.3.1 Hilbert 曲线
• 4.3.2 改进索引结构分析
• 4.3.3 实验结果分析
• 4.4 系统空间索引的构建算法设计
• 4.4.1 网格编码
• 4.4.2 构建算法
• 4.5 本章小结
• 第5章 三防决策支持系统中空间查询算法研究
• 5.1 空间选择查询
• 5.1.1 点查询
• 5.1.2 区域查询
• 5.2 最短路径查询
• 5.2.1 Dijkstra 算法基本思想
• 5.2.2 改进的Dijkstra 算法
• 5.2.3 实验结果分析
• 5.3 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文及科研成果