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

基于线性四叉树的快速邻域查询算法优化研究

作　者: 武云龙
导　师: 张健沛
学　校: 哈尔滨工程大学
专　业: 计算机应用技术
关键词: 空间数据库空间索引线性四叉树邻域查询网格区域
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 75次
引　用: 0次
阅　读: 论文下载

内容摘要

伴随着地理信息系统研究的不断深入,位置服务系统得到了越来越广泛的发展与应用。由于空间数据固有的海量性和复杂性使得传统的数据库查询技术越来越难以发挥其应有的作用,空间数据查询技术亟需发展与创新。空间数据的庞大与繁杂表明了一个数据库性能的优劣决定性因素在于查询的效率。目前较为常用的邻域查询方法多是把已知对象与所查对象抽象成空间中的一个点或者一块方形区域,从而来简化实际目标对象物理形状的不规则性,而基于线性四叉树快速邻域查询技术正是以此为基础来展开研究的。由于此方法还处于不断的发展状态中,所以在查询效率上还有许多有待改进的地方。针对目前的基于线性四叉树快速邻域查询算法存在的不足,本文主要在以下几方面做出改进。首先,将各结点赋予相应的属性值,从而省略了结点状态列表的存储空间,及其四叉树与网格区域的相互访问时间;其次,放弃树形结构的传统存储观念,直接将网格区域存储在主存中,使得结构更加的清晰,易懂;最后,通过附加层次属性值,在查找过程中省略了原算法通过递归遍历找出邻接结点的复杂过程,从而提高了原算法的查找效率。本文在最后以理论、计算、实例相结合的方法,分析验证了改进后算法的有效性及其优越性。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-15
  1.1 论文研究的目的和意义  10-11
  1.2 国内外研究现状  11-13
  1.3 论文主要工作内容和组织结构  13-15
第2章空间索引技术概述  15-34
  2.1 空间数据  15-21
    2.1.1 空间数据特征  15-16
    2.1.2 空间数据模型  16
    2.1.3 空间数据的目标  16-17
    2.1.4 空间索引的需求  17-18
    2.1.5 空间索引技术的分类  18-21
  2.2 常用的空间索引技术  21-26
    2.2.1 KD 树及其变形树  21-23
    2.2.2 R-树及其变形树  23
    2.2.3 四叉树及其变形树  23-26
  2.3 数据分块技术  26-27
    2.3.1 常规数据分块技术  26
    2.3.2 基于线性四叉树的数据分块技术  26-27
  2.4 四叉树编码方式  27-31
    2.4.1 四叉树链式编码  28-29
    2.4.2 线性四叉树层次编码  29-30
    2.4.3 线性四叉树动态编码  30-31
  2.5 空间索引技术研究  31-33
    2.5.1 R-树的空间索引结构分析  31-32
    2.5.2 四叉树空间索引结构分析  32-33
  2.6 本章小结  33-34
第3章基于线性四叉树的快速邻域查询算法改进  34-51
  3.1 基于线性四叉树的快速邻域查询算法  34-40
    3.1.1 基于线性四叉树的快速邻域查询算法分析  34-39
    3.1.2 基于线性四叉树的快速邻域查询算法存在的不足  39-40
  3.2 改进基于线性四叉树的快速邻域查询算法  40-50
    3.2.1 属性值决策法优化线性四叉树  41
    3.2.2 属性值的添加、查询方法及作用  41-45
    3.2.3 基于主存存储式结构优化线性四叉树快速邻域查询  45-48
    3.2.4 结点快速层次定位法  48-49
    3.2.5 基于线性四叉树快速邻域查询算法综合改进方法  49-50
  3.3 本章小结  50-51
第4章算法效率分析与实例验证  51-61
  4.1 改进算法完整描述  51-53
  4.2 改进算法效率分析  53-56
    4.2.1 数组查找与链表查找的比较分析  53-54
    4.2.2 结点层次定位法效率分析  54-55
    4.2.3 综合效率分析  55-56
  4.3 实例分析  56-60
  4.4 本章小结  60-61
结论  61-62
参考文献  62-67
致谢  67

基于线性四叉树的快速邻域查询算法优化研究

内容摘要

全文目录

相似论文