学位论文 > 优秀研究生学位论文题录展示
面向空间数据库引擎的空间索引系统
作 者: 陈镇虎
导 师: 郑玉明
学 校: 北京工业大学
专 业: 计算机软件与理论
关键词: 空间索引 空间查询 R树 BucketFile
分类号: TP399
类 型: 硕士论文
年 份: 2002年
下 载: 443次
引 用: 7次
阅 读: 论文下载
内容摘要
关系数据库能够支持空间数据的存储,却无法支持对其高效的访问,这是因为空间数据的多维特性与关系数据库中的一般索引不相适应。一般索引只适合对一维数据进行索引,因为其索引项是一维线性且严格有序的。空间数据的多维特性在任何方向上并不存在优先级问题,因此需要研究特殊的另类“索引”以适应多维特性的空间数据。空间索引由此应运而生,空间索引主要依靠空间对象之间的邻接性对数据进行组织,它的索引项通常是多维空间下的点或区域。 空间索引作为空间数据库中的重要组成部分,可以加快对空间对象的检索。空间索引的直接需求来自于大量空间对象上的空间运算,本文认为在空间数据库中空间运算应该分两步进行:第一步是筛选步骤,通过空间索引缩小进行比较的空间对象的个数;第二步为细化步骤,对从第一步中筛选出的空间对象进行精确的空间运算操作。本文总结出空间索引系统应提供的三类空间查询:空间范围查询、最近邻居查询、空间连接查询。空间范围查询在某图层内找出与给定查询窗口满足一定空间关系的所有空间对象;最近邻居查询在某图层内找出距离某点最近的空间对象;空间连接查询往往涉及对两个或两个以上图层中空间对象之间的操作。这三类空间查询经常出现在GIS、CAD/CAM等应用系统中。 本文重点讨论了R树、BucketFile两种空间索引的基本结构及三类空间查询在其上的算法实现。基本空间对象类型包括点对象、面对象、线对象。基于R树的空间索引结构主要对点对象和面对象进行索引;BucketFile空间索引结构主要对线对象进行索引。R树是一种类似于B~+树的动态平衡树,其索引项基于空间对象的最小外接矩形。空间对象的外接矩形能够粗略反映出空间对象的空间特性,从而加速空间对象的定位过程。BucketFile空间索引结构利用Z-ordering曲线对空间进行分区,并将线对象映射到相应的分区中。选用Z-ordering曲线的理由在于其对分区的编号方式能使编号连续的分区较好的反映它们之间的空间邻接性。
|
全文目录
中文摘要 3-4 英文摘要 4-7 第1章 绪论 7-13 1.1 研究背景 7-9 1.2 空间索引技术发展概况 9-11 1.2.1 空间索引结构概况 9-10 1.2.2 研究高效的空间查询算法 10 1.2.3 建立空间索引的效率分析模型 10-11 1.3 本文主要研究内容 11-13 第2章 空间索引的作用 13-21 2.1 空间运算与空间索引 13-15 2.2 空间数据库引擎 15-16 2.3 空间数据库引擎与空间索引 16-19 2.4 本章小节 19-21 第3章 总体框架设计 21-33 3.1 存储体系结构 21-22 3.2 主要类设计 22-24 3.3 空间索引编程接口说明 24-27 3.3.1 CIdxManr提供的接口 24-25 3.3.2 CSpaIdx提供的接口 25-27 3.4 空间索引结构的选择 27-29 3.5 并行处理 29-30 3.6 更新的一致性 30-31 3.7 本章小节 31-33 第4章 基于R树的空间索引结构 33-49 4.1 R树的基本结构 33-36 4.1.1 R树的定义 33-34 4.1.2 结点的定义 34-36 4.2 R树的插入算法 36-38 4.3 R树的删除算法 38-39 4.4 R*树对R树的改进 39-41 4.5 空间范围查询 41 4.6 最近邻居查询 41-43 4.7 空间连接查询: 43-46 4.8 本章小节 46-49 第5章 BucketFile空间索引结构 49-61 5.1 空间分割曲线 49-50 5.2 BucketFile的基本结构 50-55 5.3 插入算法 55-56 5.4 删除算法 56-57 5.5 空间范围查询 57 5.6 最近邻居查询 57-58 5.7 空间连接查询 58 5.8 本章小结 58-61 第6章 测试与分析 61-75 6.1 性能测试 61-68 6.1.1 空间范围查询 62-64 6.1.2 最近邻居查询 64-65 6.1.3 空间连接查询 65-67 6.1.4 更新操作 67-68 6.2 功能测试 68-70 6.2.1 空间范围查询 69 6.2.2 最近邻居查询 69-70 6.2.3 空间连接查询 70 6.3 空间索引结构选择原则探讨 70-73 6.4 本章小节 73-75 结论 75-77 参考文献 77-81 致谢 81-82
|
相似论文
- 卫星光通信粗瞄控制系统的设计及故障诊断,V443.1
- 病险水库溃坝概率分析方法研究,TV697
- 支持XML数据查询的F&B索引结构的研究,TP311.13
- 多邮件自动文摘的关键技术研究,TP391.1
- 基于串核的蛋白质分类算法的研究与实现,TP301.6
- 基于支持向量机的故障诊断方法研究,TP18
- 紫金山树木菌根多样性的调查分析,S718.81
- 新疆油田地面工程造价指标和管理信息系统的研究与应用,F284
- 鸡传染性支气管炎病毒河南地方株分离鉴定及HN104株与HN091株全基因组序列测定,S852.65
- 树鼩和猕猴精子冷冻保存工艺的创建和优化的研究,S865.1
- 果胶高效降解菌株的紫外诱变选育、生物特性及其生物脱胶应用研究,TS713
- 古树名木综合价值评价研究,S788
- 树突状细胞在多柔比星诱导的大鼠肾纤维化模型中的作用,R692.5
- ATN中敏感信息保护技术研究,TP309
- P-选择蛋白对人单核细胞源性树突状细胞分化和免疫功能成熟的影响,R543.5
- 危险品道路运输的安全问题及对策研究,U492.81
- 喹啉环取代喜树碱的定量构效关系研究,R914
- 海人酸致痫大鼠神经元树突棘的可塑性变化,R742.1
- C++静态代码检测语法树构建方法研究,TP311.53
- SAR干涉像对优化选取方法研究,P225.2
- 教学质量评估数据挖掘系统设计与开发,TP311.13
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 在其他方面的应用
© 2012 www.xueweilunwen.com
|