基于均值和标准差的空间索引方法研究

论文摘要

随着地理信息系统（GIS）、图像识别、计算机辅助设计与制造（CAD/CAM）、通信等行业的发展,空间数据库技术的应用也越来越广泛。空间索引介于空间对象和空间操作之间,是一种辅助性的空间数据结构,通过它的筛选,能够排除大量与特定空间操作不相关的空间对象,减少运算代价,提高空间数据库的整体性能,所以它在整个空间数据库中都占有非常重要的地位。本文在深入分析研究空间索引的方法和相关技术的基础上,重点分析了目前应用最多的四叉树和R-树两类主流技术。然后针对基于四叉树和R-树建立的混合型索引结构QR-树在空间对象更新较频繁的环境中性能下降的不足,从索引建立和结点分裂两个方面对QR-树进行了改进,给出一种新的索引方法——MVQR-树。首先,在索引的建立阶段,QR-树是基于数据的当前值建立的,每当数据变化的时候,都要相应的对索引结构做出调整,势必带来沉重的索引更新代价。而MVQR-树用（均值,标准差）的坐标形式表示空间数据项的每维数据,只有当前值发生变化的程度超过一定的限度时才对索引结构做出相应修改,这样就能明显减少索引更新的次数,从而使索引更新代价得到明显的降低。其次,QR-树中结点的分裂采用的是传统的基于“面积增量最小”的搜索式二路分裂方法,在形成的索引空间中产生大量的空白区域和重叠区域。MVQR-树引入k-means聚类算法对分裂结点进行多路分割,增加了同组对象的相似度,提高了查询过程中的剪枝速度,改善了索引的查询性能。最后,进行了仿真实验,实验结果表明,MVQR-树在空间对象更新频繁的环境中具有较优的整体性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 论文的研究内容
• 1.4 论文的组织结构
• 第2章 空间数据索引技术的研究与分析
• 2.1 空间数据索引技术的理论基础
• 2.1.1 空间数据的概念及特点
• 2.1.2 空间对象近似表示技术
• 2.1.3 空间检索处理的过程
• 2.1.4 空间索引设计相关问题研究
• 2.2 常用空间索引结构的研究
• 2.2.1 点四叉树
• 2.2.2 网格四叉树
• 2.2.3 R-树
• 2.2.4 R*-树
• 2.2.5 QR-树
• 2.3 本章小结
• 第3章 一种基于均值和标准差的空间索引方法
• 3.1 问题的提出
• 3.2 改进方法的基本思想
• 3.3 MVQR-树索引结构的建立
• 3.3.1 MVQR-树的结构
• 3.3.2 确定均值和标准差
• 3.3.3 动态调整均值和标准差
• 3.4 MVQR-树索引结构结点的分裂
• 3.4.1 优化k 值的几个相关概念
• 3.4.2 利用k-means 算法进行多路分裂
• 3.5 MVQR-树索引结构数据更新过程
• 3.6 MVQR-树索引结构数据查询过程
• 3.7 本章小结
• 第4章 实验结果与分析
• 4.1 仿真模型
• 4.2 实验环境
• 4.3 仿真实验及结果分析
• 4.3.1 更新性能的对比
• 4.3.2 查询性能和总体性能的对比
• 4.3.3 更新频率对索引性能的影响
• 4.3.4 标准差扩展因子对索引性能的影响
• 4.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢