PMR四叉树空间索引的优化研究

摘要

当前地理信息系统正面临着海量空间数据存储及管理的挑战,建立高效的空间数据索引是实现海量空间数据管理的关键技术。对于海量空间数据集,索引的构造采用逐个插入数据对象的方法是不可取的,桶载入引起了越来越多的研究者的兴趣。
　　迄今为止,人们已提出了一些有关空间索引的桶载入方法,但它们大多关注的是R树及其相关结构。对于其它的索引结构,如基于四叉树,B树和空间填充曲线相结合的桶载入问题则还没有真正地解决。本文在探讨一些具有代表性的桶载入方法的基础上,主要对能索引任意空间对象的PMR四叉树的桶载入技术进行了深入研究。
　　由于桶载入方法是基于外存的算法,I/O复杂度和空间复杂度是此类算法性能的评价指标。空间索引通常以B树形式存贮在磁盘数据库中,在论文中,首先提出了同时适用于建库和更新的B+树批量装载方法。与传统的B+树插入算法相比,该方法减少了磁盘读写次数和运行时间,并提高了空间利用率。其次,分析了传统的PMR四叉树的插入算法,发现它采用自顶向下遍历四叉树的方法来确定对象的插入位置,判定过程十分繁琐,于是提出了通过利用最小封闭块来减少了相交测试次数的方法,称之为改进的PMR四叉树插入算法。然后,针对前人批量构造PMR四叉树方法不能总是达到最优目标的缺点,在改进的插入算法的基础上,提出了一个更好的桶载入PMR四叉树的算法。其中心思想通过对对象以z-order预排序,在可用内存使用完时,利用对象的插入顺序来选择将内存中哪些叶结点写入B+树,使叶结点总是以有序的顺序进行刷新,达到了更高的空间利用率和建树速度。接着,探讨了扩展该桶载入方法去处理向一个已存在的PMR四叉树进行桶插入构造索引的问题,并给出了桶插入PMR四叉树的算法。最后,对动态插入方法和桶载入方法在执行时间上进行了实验比较,实验数据包括真实数据和人工数据,实验结果表明桶载入方法使得四叉树的构造速度相对于传统的四叉树构造方法有较大的提高。同时,本文的桶载入方法可运用到许多基于规则划分的空间数据结构上,来加快它们的构造。因此,PMR四分树空间索引的优化研究,对地理信息系统发展和空间数据处理具有一定的理论意义和应用价值。

目录

封面

目录

中文摘要

英文摘要

第一章 引言

§1.1研究背景

§1.2空间索引技术发展概况

§1.3本文研究的目的和研究内容

第二章 桶载入动态存储结构

§2.1关于R树批生成算法的相关研究

§2.2本文的思路来源

§2.3本章小结

第三章 四叉树及其应用

§3.1四叉树索引

§3.2 PMR四叉树索引

§3.3 PMR四叉树在SAND中的应用

§3.4 本章小结

第四章 PMR四叉树插入算法

§4.1 传统PMR四叉树插入算法

§4.2 改进的PMR四叉树插入算法

§4.3本章小结

第五章 桶载入PMR四叉树

§5.1改进桶载入算法的主要思想

§5.2刷新算法

§5.3归并排序

§5.4 本章小结

第六章 桶插入PMR四叉树

§6.1概述

§6.2 桶插入的归并算法

§6.3 归并算法性能分析

§6.4 本章小结

第七章 实验及结果

§7.1 实验评估标准及实验步骤

§7.2 实验数据及参数设置

§7.3 实验分析

§7.4 结论

第八章 结论和展望

致谢

参考文献

攻读硕士学位期间项目研究、论文发表和教学情况

附录 部分主要程序清单