基于新型R*Q-树空间数据索引结构的研究

论文摘要

随着信息技术不断渗透到各个领域,它们对信息处理的需求也不断提高,因此,对空间数据库索引技术的研究愈发热门。其中,空间数据库索引技术是研究如何提高空间数据库的信息处理和信息管理性能的一种技术,目前它正处于趋于探索完善的重要阶段。本文从当前比较流行的空间数据库索引技术着手。第一,详细阐述了各种空间数据库索引技术的基本原理,而且又分析了各种空间数据库索引结构的特点和优缺点。第二,在对典型四叉树、R*-树和常规R*Q-树详细研究的基础上,本人设计出了一种新型R*Q-树空间数据库索引技术。新型R*Q-树通过在父结点加入VR*-树和HR*-树,使新型R*Q-树的数据集在分割线附近形成窄带,新型R*-树的子树重叠范围大大减小并且整个数据空间被分成一条条的窄带,查找效率显著提高。新型R*Q-树的分裂技术也有所改进,具体思路是新型R*Q-树在对象插入结点导致溢出时不立即进行分裂,而是将该数据项插入到邻近未满的兄弟结点中,如果该结点邻近的兄弟结点全部已满时,才利用聚类技术进行结点分裂,在邻近兄弟结点和分裂结点之间重新组合空间数据项。新型R*Q-树在确保查询性能的前提下,大大降低了构造代价,还大幅度提高了空间利用率。第三,实验分析证明了新型R*Q-树查询性能和检索效率的高效性。在新型R*Q-树之间以及子区域之间,不存在空间数据项的重复,使新型R*Q-树结构简单化。论文在采用Java开发技术实现了对新型R*Q-树索引索引方法的仿真测试。然后依照该领域公认的有关索引算法性能评价标准,运用了大量随机性仿真空间数据库测试数据集,实现了对R*-树、新型R*Q-树索引算法与常规R*Q-树索引算法的仿真与比较。实验结果显示:新型R*Q-树有两棵R*-树即HR*-树和VR*-树,使其所划分子区的MBR面积最小,所以效率较高。另外,新型quad-tree不受固定分割极限的限制,它可以动态自适应地划分它的层次数,所以新型R*Q-树更具灵活性。

论文目录

• 致谢
• 摘要
• Abstract
• 目录
• 1 引言
• 2 空间数据库索引技术的基础理论
• 2.1 空间数据库的基础理论
• 2.2 空间数据库索引技术的理论基础
• 2.2.1 空间数据库索引技术的基本概念
• 2.2.2 空间关系
• 2.2.3 空间检索
• 2.2.4 空间目标近似
• 2.2.5 基于目标近似的空间检索过程
• 2.3 本章小结
• 3 主流空间数据库索引技术
• 3.1 基于四叉树的空间数据库索引技术
• 3.1.1 点四叉树
• 3.1.2 区域四叉树
• 3.1.3 PR 四叉树
• 3.2 基于 B-树的空间数据库索引技术
• 3.2.1 R-树
• *-树'>3.2.2 R^*-树
• 3.3 常规 RQ-树
• *Q-树的提出'>3.3.1 常规R^*Q-树的提出
• *Q-树的结构'>3.3.2 常规R^*Q-树的结构
• *Q-树查找算法'>3.3.3 常规R^*Q-树查找算法
• *Q-树插入算法'>3.3.4 常规R^*Q-树插入算法
• *Q-树动态指导机制'>3.3.5 常规R^*Q-树动态指导机制
• *Q-树结点分裂算法'>3.3.6 常规R^*Q-树结点分裂算法
• *Q-树结点删除算法'>3.3.7 常规R^*Q-树结点删除算法
• 3.4 本章小结
• *Q-树：基于常规R^*Q-树的索引结构'>4 新型R^*Q-树：基于常规R^*Q-树的索引结构
• *Q-树的设计'>4.1 新型R^*Q-树的设计
• *Q-树算法'>4.2 新型R^*Q-树算法
• 4.2.1 插入算法
• 4.2.2 聚类分裂技术
• 4.2.3 删除算法
• 4.2.4 查询算法
• 4.3 算法实现
• *Q-树算法实现中主模块设计与实现'>4.3.1 新型R^*Q-树算法实现中主模块设计与实现
• *Q-树算法实现中基本操作模块的设计与实现'>4.3.2 新型R^*Q-树算法实现中基本操作模块的设计与实现
• *Q-树索引基本操作的部分核心代码'>4.3.3 新型R^*Q-树索引基本操作的部分核心代码
• 4.4 本章小结
• *Q-树算法性能测试、分析'>5 新型R^*Q-树算法性能测试、分析
• *Q-树算法的实验测试平台'>5.1 新型R^*Q-树算法的实验测试平台
• 5.2 性能评估
• 5.3 本章小结
• 6 总结与展望
• 参考文献
• 作者简历
• 学位论文数据集
• 详细摘要