基于R-树的空间索引并行批量加载算法研究及实现
发布时间：2021-04-17 10:26
随着空间数据的规模急剧增加,空间索引成为影响空间数据检索性能的关键因素。近年来,计算机处理器的发展趋势正从高主频的单核处理器转向片上多处理器（CMP, Chip Multi-Processor）,从依靠指令级的并行转向线程级并行。并行计算模式正越来越受到重视,同时也得到了许多实际应用,为提升空间索引批量加载性能提供了新的硬件环境。研究者对基于R-树的批量加载技术做了大量的研究,面向多核处理器环境对算法并行化的工作也正成为研究热点。本文在深入分析国内外空间索引结构和并行计算技术的基础上,就以下内容进行了研究:1)空间索引并行批量加载代价模型分析了动态R-树的生成过程及算法,并归纳了动态算法在海量数据索引方面的性能问题,然后阐述了R-树静态批量加载的过程及相关算法,分析在面向空间查询应用中该方法的性能优势。建立了空间索引并行批量加载代价模型,为构建高效的查询执行计划提供理论依据。2)空间索引并行批量加载算法基于Hilbert R-树索引构建算法,分析其在多核处理器结构上的可并行性,设计并实现了索引并行批量加载算法,提高了在片上多处理器架构上空间索引的加载效率。通过实验,从运行时间、并行效率...
【文章来源】：国防科技大学湖南省 211工程院校 985工程院校
【文章页数】：73 页
【学位级别】：硕士
【部分图文】：
图1.1两层R-树示例
分调动片上多处理器的计算优势，首先需要根据多核处理器编程模型，并在此基础上分析传统串行算法的可并行性以及数、数据划分、内存和 Cache 大小等因素，建立算法并行优写高效的并行算法。对多核处理器硬件结构，在 Hilbert R-树静态批量加载算法基行批量加载算法，充分利用多核计算资源，提高索引的构建检索速度。2.2 R-树的构建方法前最常用的一种空间数据访问方法，R-树是 B-树在多维空间它也是一颗高度平衡的树。R-树种存储的不是对象本身，而形(MBR)，所有 MBR 的边与一个全局坐标系的轴平行，如图每一个结点都跟磁盘文件中的一页相对应，因此在进行空间对很少的结点进行搜索，而不用对所有结点进行遍历，大大索性能[26]。
图 2.2 两种不同的处理方案本课题基于片上多处理器(CMP)设计空间索引并行批量加载算法，以实现快速高效的索引构建。考虑空间索引并行批量加载的代价模型，需要分析在索引构建过程中多方面因素的影响，如 CPU 核数、CPU 计算效率、I/O 代价、页面大小、内存大小和数据内存交换时间等等。通过对空间索引批量加载算法的研究，索引静态批量加载的时间损耗主要决定于对空间对象的外部排序代价。例如在 Hilbert R-树算法中，空间对象就是依据对应的 Hilbert 值进行排列，然后再一次性的构建 R-树，即首先生成大量最底层的结点，然后再生成倒数第二层结点，直至只剩下最后一个根结点为止。实验证明，系统中能够使用的主存大小非常关键，这也是我们在代价模型中考虑的因素之一。表 2.1 列出了在建立代价模型过程中用到的变量。表 2.1 代价模型中的变量说明变量 定义D 数据空间的维度NcoreCPU 中的核数T磁盘上每个页面的 I/O 时间
【参考文献】：
期刊论文
[1]支持多线程的空间数据GSQL解析器设计与实现[J]. 张震,王超,熊伟,雷霖,景宁. 计算机应用研究. 2011(02)
[2]三维Hilbert曲线在图像置乱中的应用[J]. 万里红,孙燮华,林旭亮. 计算机工程. 2011(02)
[3]应用GPU集群加速计算蛋白质分子场[J]. 张繁,王章野,姚建,吴韬,彭群生. 计算机辅助设计与图形学学报. 2010(03)
[4]空间数据的访问方法与查询技术研究[J]. 朴英花. 电脑知识与技术. 2010(03)
[5]开源GIS进展及其典型应用研究[J]. 胡庆武,陈亚男,周洋,熊成利. 地理信息世界. 2009(01)
[6]基于多核集群系统的并行编程模型的研究[J]. 胡晨骏,王晓蔚. 计算机技术与发展. 2008(04)
[7]多核微机基于OpenMP的并行计算[J]. 蔡佳佳,李名世,郑锋. 计算机技术与发展. 2007(10)
[8]基于SMP集群系统的并行编程模式研究与分析[J]. 宋伟,宋玉. 计算机技术与发展. 2007(02)
[9]R树家族的演变和发展[J]. 张明波,陆锋,申排伟,程昌秀. 计算机学报. 2005(03)
[10]空间数据引擎关键技术与应用分析[J]. 张明波,申排伟,陆锋,程昌秀. 地球信息科学. 2004(04)
硕士论文
[1]空间数据库规则技术研究[D]. 张震.国防科学技术大学 2010
[2]基于空间数据库的栅格数据存储管理关键技术研究[D]. 王超.国防科学技术大学 2009
[3]基于多核系统的内存管理研究[D]. 何进仙.电子科技大学 2009
[4]基于R-树的空间数据索引技术的研究与实现[D]. 周帆.哈尔滨理工大学 2009
[5]空间索引技术研究[D]. 张厅.中南大学 2007
[6]基于Linux的地理空间数据管理系统设计与实现[D]. 朱进.浙江大学 2007
[7]基于R树的空间索引技术的研究与应用[D]. 付伟.四川大学 2006
[8]面向空间数据库引擎的空间索引系统[D]. 陈镇虎.北京工业大学 2002
本文编号：3143290
【文章来源】：国防科技大学湖南省 211工程院校 985工程院校
【文章页数】：73 页
【学位级别】：硕士
【部分图文】：
图1.1两层R-树示例
分调动片上多处理器的计算优势，首先需要根据多核处理器编程模型，并在此基础上分析传统串行算法的可并行性以及数、数据划分、内存和 Cache 大小等因素，建立算法并行优写高效的并行算法。对多核处理器硬件结构，在 Hilbert R-树静态批量加载算法基行批量加载算法，充分利用多核计算资源，提高索引的构建检索速度。2.2 R-树的构建方法前最常用的一种空间数据访问方法，R-树是 B-树在多维空间它也是一颗高度平衡的树。R-树种存储的不是对象本身，而形(MBR)，所有 MBR 的边与一个全局坐标系的轴平行，如图每一个结点都跟磁盘文件中的一页相对应，因此在进行空间对很少的结点进行搜索，而不用对所有结点进行遍历，大大索性能[26]。
图 2.2 两种不同的处理方案本课题基于片上多处理器(CMP)设计空间索引并行批量加载算法，以实现快速高效的索引构建。考虑空间索引并行批量加载的代价模型，需要分析在索引构建过程中多方面因素的影响，如 CPU 核数、CPU 计算效率、I/O 代价、页面大小、内存大小和数据内存交换时间等等。通过对空间索引批量加载算法的研究，索引静态批量加载的时间损耗主要决定于对空间对象的外部排序代价。例如在 Hilbert R-树算法中，空间对象就是依据对应的 Hilbert 值进行排列，然后再一次性的构建 R-树，即首先生成大量最底层的结点，然后再生成倒数第二层结点，直至只剩下最后一个根结点为止。实验证明，系统中能够使用的主存大小非常关键，这也是我们在代价模型中考虑的因素之一。表 2.1 列出了在建立代价模型过程中用到的变量。表 2.1 代价模型中的变量说明变量 定义D 数据空间的维度NcoreCPU 中的核数T磁盘上每个页面的 I/O 时间
【参考文献】：
期刊论文
[1]支持多线程的空间数据GSQL解析器设计与实现[J]. 张震,王超,熊伟,雷霖,景宁. 计算机应用研究. 2011(02)
[2]三维Hilbert曲线在图像置乱中的应用[J]. 万里红,孙燮华,林旭亮. 计算机工程. 2011(02)
[3]应用GPU集群加速计算蛋白质分子场[J]. 张繁,王章野,姚建,吴韬,彭群生. 计算机辅助设计与图形学学报. 2010(03)
[4]空间数据的访问方法与查询技术研究[J]. 朴英花. 电脑知识与技术. 2010(03)
[5]开源GIS进展及其典型应用研究[J]. 胡庆武,陈亚男,周洋,熊成利. 地理信息世界. 2009(01)
[6]基于多核集群系统的并行编程模型的研究[J]. 胡晨骏,王晓蔚. 计算机技术与发展. 2008(04)
[7]多核微机基于OpenMP的并行计算[J]. 蔡佳佳,李名世,郑锋. 计算机技术与发展. 2007(10)
[8]基于SMP集群系统的并行编程模式研究与分析[J]. 宋伟,宋玉. 计算机技术与发展. 2007(02)
[9]R树家族的演变和发展[J]. 张明波,陆锋,申排伟,程昌秀. 计算机学报. 2005(03)
[10]空间数据引擎关键技术与应用分析[J]. 张明波,申排伟,陆锋,程昌秀. 地球信息科学. 2004(04)
硕士论文
[1]空间数据库规则技术研究[D]. 张震.国防科学技术大学 2010
[2]基于空间数据库的栅格数据存储管理关键技术研究[D]. 王超.国防科学技术大学 2009
[3]基于多核系统的内存管理研究[D]. 何进仙.电子科技大学 2009
[4]基于R-树的空间数据索引技术的研究与实现[D]. 周帆.哈尔滨理工大学 2009
[5]空间索引技术研究[D]. 张厅.中南大学 2007
[6]基于Linux的地理空间数据管理系统设计与实现[D]. 朱进.浙江大学 2007
[7]基于R树的空间索引技术的研究与应用[D]. 付伟.四川大学 2006
[8]面向空间数据库引擎的空间索引系统[D]. 陈镇虎.北京工业大学 2002
本文编号：3143290
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3143290.html
