分布式并行时空索引技术研究

发布时间：2018-03-19 06:24

  本文选题：时空查询　切入点：时空索引　出处：《中国地质大学》2014年博士论文　论文类型：学位论文

【摘要】：现实世界是一个永恒变化的四维时空,每时每刻都在持续不断地产生着大量的时空数据。时空数据可以帮助人类了解历史、掌握现在、预测将来,有助于提高人类对四维时空中各种存在与状态演变的洞察、感知与预测能力。如何有效地存储和管理这些大规模的时空数据集,是以分布式协同、高性能计算、时空数据流处理为核心的新一代空间信息系统必须解决的关键技术问题之一。新一代空间信息系统中的四维时空数据库问题刚刚引起关注,各种研究也刚刚开始,海量时空数据管理中还存在着诸如多层次时空缓存、四维时空数据快速检索、调度等技术瓶颈问题,而高效时空索引是这些问题有效解决的基础。在当前多核计算机已经成为常规计算设备的情况下,时空数据库领域亟需解决的关键科学技术问题之一,是如何在分布式多核计算环境中构建合理的分布式时空索引架构、降低时空索引的并发控制成本。 目前,时空索引的研究大多针对的是集中式索引,分布式时空索引和并行时空索引两个方面的研究都较少,并且是作为两个独立的内容进行研究的。未见直接针对分布式并行时空索引的一体化研究。为降低时空索引的并发控制成本,现有的研究成果多专注于并发控制算法本身,而缺乏对时空索引结构本身的可并行化进行研究。常用的树型时空索引的层次结构不具并行性,不利于并行算法的实现,存在并行计算瓶颈。在频繁更新的时空数据库中,并行时空索引的一体化与时空索引结构并行化缺失的问题,严重阻碍了大数据时代时空数据库中分布式并行缓存机制、并行预调度与调度机制、大规模时空分析等一系列问题的有效解决,成为该领域亟需解决的重大难题。因此,亟需设计具有可并行化结构的时空索引方法,并对时空索引的分布式和并行化进行一体化研究。 为此,本文以国家高技术研究发展计划(863计划)“十二五”主题项目课题“实时GIS关键技术及软件平台”(2012AA121401)、“十一五”重点项目课题“三维空间数据管理系统与分析组件研发”(2008AA121602)和国家自然科学基金项目“地上下一体化三维动态广义表空间索引方法”(41101368)相关研究成果为基础,对时空索引的分布式和并行化进行了一体化研究,提出了适合分布式并行计算环境的分布式并行时空索引DPSI多层次理论架构；对时空索引结构本身并行化机制进行了研究,提出了具有可并行化结构、适用于DPSI局部索引的基于间隔关系算子的并行时空索引IPSI方法,突破了高维度下(本文主要针对四维时空)树形索引的层次结构对并行算法实现的局限性,在细化时空索引并行粒度的同时降低了并发控制开销。设计实现了主从模式下的分布式并行时空索引MSDPSI和对等模式下的分布式并行时空索引PPDPSI。实验表明,本文研究成果有效提升了分布式并行计算环境下并行时空索引性能。论文的主要研究工作如下：(1)综述并剖析了与分布式并行时空索引技术相关的前人研究工作。本文首先探讨了分布式并行时空索引的研究目标与意义,梳理了分布式并行时空索引的技术脉络,然后按其技术发展脉络,分别评述了集中式时空数据索引、并行时空数据索引和分布式时空数据索引等三类时空索引的发展现状及存在问题。针对所存在的问题,提出了本文的主要研究内容、研究方法和技术路线。同时,分析、讨论了与时空索引相关的地学时空及其表达方法、时空对象的主要特征、时空查询的分类等相关因素。(2)提出了多层次分布式并行时空索引架构(DPSI),设计实现了主从模式和对等模式下的分布式并行时空索引方法。提出了DPSI的时空数据划分方法以及基于此划分的DPSI的形式化描述。DPSI的全局架构支持主从和对等两种模式。设计实现了主从模式下的DPSI (MSDPSI)和对等模式下的DPSI (PPDPSI)的查询算法和更新维护算法。实验表明,MSDPSI和PPDPSI都具备良好的分布式时空查询性能。两者比较而言,MSDPSI比PPDPSI具有更好的更新维护性能。但是,MSDPSI的网络自治性和可扩展性弱于PPDPSI。随着数据规模的增大,MSDPSI的主控服务器存在性能瓶颈。(3)提出了基于间隔关系算子的并行时空索引(IPSI)方法。对IPSI中的时空数据与间隔数据的表达方法进行了理论、系统研究,给出了时空数据到间隔数据的转换关系。基于该转换关系,提出了时空查询到可并行的间隔关系算子的转换方法,实现了基于间隔关系算子的时空查询表达,为基于间隔关系算子的并行时空索引和并行时空查询奠定了理论基础。研究提出了IPSI的算法原理和数据结构,设计实现了IPSI的更新算法和查询算法。实验结果表明,在多核并行计算环境下,IPSI具有优良的查询、更新性能。(4)基于DPSI设计开发了一个分布式并行时空数据引擎(DPSDE)和一个时空数据库管理系统的原型系统。提出了分布式并行时空数据引擎(DPSDE)的系统架构,讨论了该架构中缓存、索引及调度策略之间的关系,设计并实现了基于该架构的时空数据调度策略。基于DPSDE设计开发了一个时空数据库管理原型系统。该原型系统已经在多个城市级别的时空数据管理中使用,证明了DPSI的有效性和实用性。 分布式并行时空索引主要有两个突破方向,一个是采用先进高效的并发控制技术实现索引的分布式并行特征,另一个就是尽量使索引本身成为可分布式并行结构,从而以尽可能少的并发控制成本实现尽可能多的分布式并行特征。本文的研究工作主要集中在第二个方面。在上述研究工作中,主要有以下创新性成果：(1)提出了多层次自适应分布式并行时空索引DPSI架构及算法 针对不同的网络环境和并行计算环境大规模时空数据管理难点问题,设计提出了多层次的自适应分布式并行时空索引DPSI架构。该架构将网络计算资源分为全局网络、网络节点、CPU、内核等多个层次。以并行间隔关系算子为底层构建的DPSI架构,具备高效调度管理上至全局网络下至并行计算内核的能力,可以根据网络节点的并行计算能力、承载数据量等信息自适应地调整网络节点动态选择,充分发挥了分布式环境下单个节点的并行计算能力,提高了分布式并行时空索引整体性能。针对现有分布式时空索引大多只顾及到了网络分布式特征,而往往忽略了网络节点的并行计算能力的充分利用问题。在DPSI架构下,进行了分布式并行一体化研究,提出了主从分布式并行时空索引MSDPSI方法和对等分布式并行时空索引PPDPSI方法。这两种方法针对不同网络环境,采取主从结构和对等结构分别构建分布式全局索引,局部索引则采用IPSI方法,具备节点动态管理能力,将网络的分布性与节点的并行计算能力有机整合,增强了分布式并行时空索引的自治性和可扩展性,提高了分布式并行时空索引的整体性能。(2)提出了基于间隔关系算子的并行时空索引IPSI方法 针对多核并行计算环境下树形时空索引对细粒度并行计算的限制,提出了具有并行化结构的基于间隔关系算子的并行时空索引IPSI方法。IPSI的时空查询与并行间隔关系算子转换方法将时空数据查询转化为可并行的间隔关系算子操作,然后将间隔数据集映射到可并行的不同维度的间隔点集平面。IPSI采用统一的二维平面元素求交运算实现各种间隔关系算子,从而在多核计算环境下以统一接口实现多种时空查询。IPSI根据间隔点集平面递归三角化方法构建不同维度的间隔数据虚拟二叉树索引。该二叉树只记录叶子结点,减少了节点访问次数,提高了二叉树索引查询性能。同时,由于间隔数据的结束值恒大于或等于其开始值,间隔点集平面只需要考虑上三角区域而不用考虑整个平面范围,这也大大缩减了平面元素求交计算量。基于多棵虚拟二叉树构建的IPSI,有效解决了时空数据耦合度高、可并行性差的问题,可充分发挥了多核并行计算优势,提高了并行时空索引性能。 本文的研究成果为分布式并行计算环境下的海量三维、四维或更高维的时空数据的快速检索提供了可行、通用、高效的并行时空索引解决方案。后续研究将专注于分布式并行计算环境下时空索引的代价模型研究和时空数据安全问题研究。
[Abstract]:......
【学位授予单位】：中国地质大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：P208

【参考文献】

中国期刊全文数据库 前10条

1 何珍文;郑祖芳;刘刚;吴冲龙;;动态广义表空间索引方法[J];地理与地理信息科学;2011年05期

2 郑文武;李先绪;黄执勤;;云计算中的并行计算技术分析[J];电信科学;2011年12期

3 刘义;陈荦;景宁;熊伟;;基于R-树索引的Map-Reduce空间连接聚集操作[J];国防科技大学学报;2013年01期

4 张，

本文编号：1633188