学位论文 > 优秀研究生学位论文题录展示

GIS空间索引技术的研究

作　者: 吴敏君
导　师: 陈天滋
学　校: 江苏大学
专　业: 计算机应用技术
关键词: 网格索引 R树索引混合索引空间索引聚类 GIS
分类号: P208
类　型: 硕士论文
年　份: 2006年
下　载: 908次
引　用: 14次
阅　读: 论文下载

内容摘要

近年来GIS技术获得了迅猛发展，已广泛应用于公共管理，科学研究和商业领域。地理信息系统已经成为当前相关领域中一个十分活跃的研究课题。地理信息数据量日趋海量化，海量空间数据的处理需要通过空间存储技术提高处理效率。由于空间数据本身的复杂性，以及海量数据查询的要求日益提高，使得研究高效的空间索引技术成为GIS领域中一项重要的课题。本文首先综述了地理信息系统和空间索引技术研究方面的一些最新工作，描述了空间数据的特征，对该研究开展以来所提出的主要空间索引技术进行了比较、分析和分类阐述。并讨论了空间索引算法的改进和设计思路。由于目前已有的空间索引算法难以权衡空间存储效率和算法操作时间效率之间的矛盾。因此，本文综合区域分割原理和面向对象的分割原理的优点，提出了一种新的基于粗分网格和聚类R树的混合空间索引算法(HSIBGR)。该算法将研究区域划分为若干大网格建立一级索引，针对每个网格建立基于R树的二级索引。通过两级索引机制有效地节省了存储空间，同时将空间对象的操作限制在局部范围内，减少了空间对象的操作时间。在进行R树结点分裂时，根据空间对象聚集分布的特性，提出了一种基于聚类技术的R树结点分裂算法(C-Linear)，进一步优化了空间数据的组织，有效地提高了索引效率。接着，本文将C-Linear算法加入到HSIBGR索引中，详细讨论了HSIBGR空间索引的插入、删除和查询操作。最后，采用C++设计了C-Linear算法和HSIBGR算法，并用随机函数产生多种应用场景，将C-Linear算法和包含C-Linear的HSIBGR算法以及Guttman的R树算法和R树二次结点分裂算法在Linux系统下进行了模拟实验，通过对性能指标的比较和分析，结果表明HSIBGR算法的效率要高于Guttman的R树算法的效率，C-Linear算法的有效性要比R树二次结点分裂算法的有效性好。

全文目录

学位论文版权使用授权书  3-4
独创性声明  4-5
摘要  5-6
ABSTRACT  6-10
第一章引言  10-13
  1.1 论文的背景  10-11
  1.2 论文研究的主要内容与主要工作  11-12
  1.3 论文的组织结构  12-13
第二章 GIS 空间索引技术的分析与评价  13-35
  2.1 空间索引技术概述  13-15
  2.2 基于网格的空间索引技术  15-20
    2.2.1 基于固定网格划分的空间索引算法  15-16
    2.2.2 基于多层次网格的空间索引算法  16-18
    2.2.3 自适应层次网格空间索引算法  18-19
    2.2.4 基于粗分格网的空间对象范围索引  19-20
  2.3 基于树结构的空间索引技术  20-26
    2.3.1 基于R树的空间索引算法  21-23
    2.3.2 基于R~+树的空间索引算法  23-24
    2.3.3 基于R~*树的空间索引算法  24-25
    2.3.4 基于四分树的空间索引算法  25-26
  2.4 混合结构的空间索引技术  26-33
    2.4.1 一种固定网格和四分树相结合的空间索引算法(CELLQTREE)  26-28
    2.4.2 R树与四分树相结合的空间索引算法  28-30
    2.4.3 R~*树与四分树相结合的空间索引算法  30-32
    2.4.4 一种渐变空间中的动态索引算法  32-33
  2.5 空间索引技术改进方案的讨论  33-34
  2.6 本章小结  34-35
第三章基于粗分网格和聚类R树的混合空间索引机制(HSIBGR)  35-43
  3.1 概述  35
  3.2 基本概念  35-37
  3.3 混合空间索引机制算法原理  37-38
  3.4 索引机制  38-40
  3.5 基于分割聚类技术的R树结点线性分裂算法  40-42
    3.5.1 K均值聚类算法  40-41
    3.5.2 C-Linear分裂算法  41-42
  3.6 本章小结  42-43
第四章 HSIBGR空间索引的操作算法  43-54
  4.1 概述  43
  4.2 主要数据结构的定义  43-46
    4.2.1 R树的数据结构定义  43-45
    4.2.2 桶数组数据结构的定义  45
    4.2.3 跨块地物索引信息及其桶对应关系表结构  45-46
  4.3 主要类功能  46-47
    4.3.1 磁盘页管理类(CIdxPage)  46
    4.3.2 R树类(CIdxRtree)  46
    4.3.3 空间索引类(CIdxManage)  46
    4.3.4 缓冲区管理类(CIdxBuffer)  46-47
  4.4 HSIBGR索引主要操作和算法  47-53
    4.4.1 聚类R树的插入算法  47-48
    4.4.2 聚类R树的删除算法  48-49
    4.4.3 聚类R树的检索算法  49-50
    4.4.4 HSIBGR空间索引的插入算法  50-51
    4.4.5 HSIBGR空间索引的删除算法  51-52
    4.4.6 HSIBGR空间索引的检索算法  52-53
  4.5 本章小结  53-54
第五章 HSIBGR空间索引算法性能分析和评价  54-60
  5.1 概述  54
  5.2 HSIBGR索引算法性能的定性分析和评价  54-55
    5.2.1 HSIBGR索引算法的空间复杂性分析和评价  54
    5.2.2 HSIBGR索引算法的时间复杂性分析和评价  54-55
  5.3 C-Linear算法性能的定量测试和分析  55-57
    5.3.1 实验环境配置  55-56
    5.3.2 C-Linear算法对R树插入操作性能的影响  56
    5.3.3 C-Linear算法对R树查询操作性能的影响  56-57
  5.4 HSIBGR索引算法性能的定量测试和分析  57-59
    5.4.1 性能评价方法  57
    5.4.2 实验参数设置  57
    5.4.3 HSIBGR算法对插入操作性能的影响  57-58
    5.4.4 HSIBGR算法对删除操作性能的影响  58-59
    5.4.5 HSIBGR算法对检索操作性能的影响  59
  5.5 本章小结  59-60
第六章总结与展望  60-62
  6.1 工作总结  60-61
  6.2 工作展望  61-62
参考文献  62-66
致谢  66-67
在读期间发表的论文  67

GIS空间索引技术的研究

内容摘要

全文目录

相似论文