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

空间数据库的索引技术研究

作 者: 张泽宝
导 师: 张健沛
学 校: 哈尔滨工程大学
专 业: 计算机应用技术
关键词: 空间数据库 空间索引 批量加载技术 聚类分析 方向关系查询 近邻查询
分类号: TP311.13
类 型: 博士论文
年 份: 2009年
下 载: 574次
引 用: 2次
阅 读: 论文下载
 

内容摘要


空间索引技术是空间数据库领域中的一个重要的研究内容,索引的性能将直接影响数据库的性能,且数据的检索和查询是应用最多的操作,为了提高查询的速度,必须建立高效的空间索引结构支持相关的操作,空间索引技术经历了多年的研究和发展,形成了一套较完整的体系结构,但由于空间数据的海量性、复杂性和多样性的特点,对索引结构提出了更高的要求,对空间数据库中索引结构的研究成为一个研究的热点问题,如何建立高效的索引结构、提出有效的查询处理算法是迫切的研究课题。本文从空间索引的建立和基于索引的空间对象查询两个方面进行了研究,提出了一些较为有效的解决方法。针对现有的索引方法不能较好的保持空间数据的映射相关性,相邻的空间对象不能存储在索引中相近的结点上,引入了批量加载的方法对数据进行预处理,在分析影响空间索引性能的指标因素的基础上,对相对变化不多的静态数据,提出了一种静态的批量加载方法,减少索引覆盖区域的大小,通过实验对算法进行了验证,实验结果表明,提出的方法获得较好的空间利用率,性能较以前算法有了改善和提高。空间索引结构要随着数据进行动态的调整,动态索引结构的创建本质是聚类问题。对已有的聚类算法的分析,引入基于网格和密度的聚类算法对数据进行聚类,改进了原有聚类算法中的一些缺陷,将对象按照聚簇进行划分,通过两级的索引机制进行组织索引,每个聚簇都建立各自的索引结构,通过全局的R树索引结构建立整个索引,实验结果表明,提出的算法进一步提高了索引的时间和空间复杂度。针对现有的基于方向关系模型的查询处理过程,在过滤阶段不能获得较好的过滤结果,导致求精步骤的时间复杂度较高。根据对象MBR之间的方向关系的定义,在过滤和求精步骤之间插入一个中间步骤,根据参考对象落在空间区域的不同划分,判断目标和参考对象的方位关系,通过对所有的可能组合的情况进行分析,给出了解决方法,实现了更好的过滤候选对象目的,减少进入求精步骤的数据对象,从而提高了基于方向关系的查询速度。通过实例对提出的方法进行了分析,性能有了很大的提高,证明了算法的有效性,又通过实验进行验证,实验结果表明,算法在查询时间和I/O访问上均都有了提高。针对在近邻查询中参考对象被简化为一个点,使得查询的结果受到一定程度的影响,且现有的k近邻的查询算法不能很好的处理对象之间近邻查询的问题。提出了基于等距离线的k近邻查询算法,给出了更准确的过滤边界值和对象之间的距离定义,提出了新的剪枝策略,减少了计算实际对象距离的计算量,通过实例和实验对算法进行了分析和验证,分析的结果表明,算法有较好的过滤性能,能够提高基于对象的k近邻查询效率,进一步提高了算法在时间和空间上的性能。

全文目录


摘要  5-7
ABSTRACT  7-13
第1章 绪论  13-27
  1.1 研究背景、目的及意义  13-14
  1.2 国内外研究现状  14-24
    1.2.1 R 树家族的索引建立  16-20
    1.2.2 批量加载的索引建立  20-23
    1.2.3 索引的查询方法  23-24
    1.2.4 索引技术的应用  24
  1.3 空间索引存在的问题  24-25
  1.4 论文的组织结构与研究内容  25-27
第2章 空间数据索引概述  27-48
  2.1 空间数据及索引结构特点  27-30
    2.1.1 空间数据的特点  28-29
    2.1.2 空间索引结构的特点  29-30
  2.2 空间索引的发展和分类  30-33
    2.2.1 空间索引的发展  30-31
    2.2.2 空间索引的分类  31-33
  2.3 典型的空间索引结构  33-41
    2.3.1 K-D 树索引结构  33-34
    2.3.2 K-D-B 树索引结构  34
    2.3.3 四叉树索引结构  34-35
    2.3.4 网格索引结构  35-36
    2.3.5 R 树家族索引结构  36-40
    2.3.6 典型的索引结构对比  40-41
  2.4 空间数据查询方式  41-43
  2.5 空间查询代价模型  43-46
  2.6 本章小结  46-48
第3章 基于批量加载技术的索引建立方法  48-61
  3.1 问题的提出  48-49
  3.2 相关研究  49-54
    3.2.1 静态的批量加载技术  50-53
    3.2.2 动态的批量加载技术  53-54
  3.3 基于批量加载的索引建立方法  54-57
    3.3.1 算法的描述  55-56
    3.3.2 算法的分析  56-57
  3.4 仿真实验与结果分析  57-60
    3.4.1 实验的数据集和性能指标  57-58
    3.4.2 结果对比分析  58-60
  3.5 本章小结  60-61
第4章 基于改进聚类的索引建立方法  61-84
  4.1 问题的提出  61-62
  4.2 相关研究  62-74
    4.2.1 聚类分析  62-71
    4.2.2 聚类方法的比较  71-73
    4.2.3 基于聚类的索引构建  73-74
  4.3 基于改进聚类的索引建立方法  74-79
    4.3.1 算法思想  74-75
    4.3.2 改进的聚类方法  75-77
    4.3.3 树型索引结构的建立  77-78
    4.3.4 算法描述  78-79
  4.4 仿真实验与结果分析  79-83
    4.4.1 性能指标和数据集  79-80
    4.4.2 结果对比  80-81
    4.4.3 性能分析  81-83
  4.5 本章小结  83-84
第5章 方向关系查询过滤方法  84-104
  5.1 问题的提出  84-86
  5.2 相关研究  86-92
    5.2.1 方向关系模型  86-88
    5.2.2 锥形模型的查询处理方法  88-91
    5.2.3 投影模型的查询处理  91-92
  5.3 方向查询精过滤方法  92-100
    5.3.1 MBR 的方向关系  92-94
    5.3.2 算法的方向模型  94
    5.3.3 方向关系查询处理过程  94-96
    5.3.4 精过滤查询处理方法  96-100
  5.4 仿真实验与结果分析  100-103
    5.4.1 实验的性能指标和数据集  100-101
    5.4.2 结果对比分析  101-103
  5.5 本章小结  103-104
第6章 基于等距离线的近邻查询方法  104-124
  6.1 问题的提出  104-105
  6.2 相关研究  105-110
    6.2.1 BAB 算法  106-108
    6.2.2 BF 算法  108-109
    6.2.3 其他的近邻算法  109-110
  6.3 基于等距离线的近邻查询方法  110-117
    6.3.1 相关概念  110-114
    6.3.2 近邻算法的剪枝规则  114-116
    6.3.3 近邻查询处理过程  116-117
    6.3.4 算法描述  117
  6.4 实例分析  117-120
  6.5 实验结果与性能分析  120-123
  6.6 本章小结  123-124
结论  124-126
参考文献  126-138
攻读博士学位期间发表的论文和取得的科研成果  138-140
致谢  140-141
个人简历  141

相似论文

  1. 牡丹EST-SSR引物开发及其亲缘关系分析,S685.11
  2. 高血压前期证候特征研究,R259
  3. 大学生综合素质测评研究,G645.5
  4. 大豆品种对腐竹品质的影响及其品质评价体系的初步构建,TS214.2
  5. 21个荷花品种遗传多样性的ISSR分析,S682.32
  6. 基于聚类分析的P2P流量识别算法的研究,TP393.02
  7. 桃杂交后代(F1)幼苗光合效能评价,S662.1
  8. 南通市农业面源污染负荷研究与综合评价,X592
  9. 土壤环境功能区划研究,X321
  10. 基因表达谱数据聚类分析方法比较与大豆疫霉基因的网络构建,S435.651
  11. 大豆杂种优势及其遗传基础研究,S565.1
  12. 象草自交后代无性系的饲用价值及生物质能特性初步评价,S543.9
  13. 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
  14. 基于同化能力杂种优势早期评价的桃光合特性研究,S662.1
  15. 云南省直管县改革研究,D630
  16. 基于分治法的聚类方法研究,TP311.13
  17. 三十种中成药元素含量分析及基于元素含量的中成药分类研究,R286.0
  18. 面向社区教育的个性化学习系统的研究与实现,TP391.6
  19. 基于Moodle的高职网络教学系统设计与实现,TP311.52
  20. 重庆文化产业竞争力研究,F224
  21. 草原公路光环境对驾驶员生理指标的影响研究,U491.254

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com