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

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

作者:师大云端图书馆 时间:2015-12-28 分类:参考文献 喜欢:3670
师大云端图书馆

【摘要】现实世界是一个永恒变化的四维时空,每时每刻都在持续不断地产生着大量的时空数据。时空数据可以帮助人类了解历史、掌握现在、预测将来,有助于提高人类对四维时空中各种存在与状态演变的洞察、感知与预测能力。如何有效地存储和管理这些大规模的时空数据集,是以分布式协同、高性能计算、时空数据流处理为核心的新一代空间信息系统必须解决的关键技术问题之一。新一代空间信息系统中的四维时空数据库问题刚刚引起关注,各种研究也刚刚开始,海量时空数据管理中还存在着诸如多层次时空缓存、四维时空数据快速检索、调度等技术瓶颈问题,而高效时空索引是这些问题有效解决的基础。在当前多核计算机已经成为常规计算设备的情况下,时空数据库领域亟需解决的关键科学技术问题之一,是如何在分布式多核计算环境中构建合理的分布式时空索引架构、降低时空索引的并发控制成本。目前,时空索引的研究大多针对的是集中式索引,分布式时空索引和并行时空索引两个方面的研究都较少,并且是作为两个独立的内容进行研究的。未见直接针对分布式并行时空索引的一体化研究。为降低时空索引的并发控制成本,现有的研究成果多专注于并发控制算法本身,而缺乏对时空索引结构本身的可并行化进行研究。常用的树型时空索引的层次结构不具并行性,不利于并行算法的实现,存在并行计算瓶颈。在频繁更新的时空数据库中,并行时空索引的一体化与时空索引结构并行化缺失的问题,严重阻碍了大数据时代时空数据库中分布式并行缓存机制、并行预调度与调度机制、大规模时空分析等一系列问题的有效解决,成为该领域亟需解决的重大难题。因此,亟需设计具有可并行化结构的时空索引方法,并对时空索引的分布式和并行化进行一体化研究。为此,本文以国家高技术研究发展计划(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,有效解决了时空数据耦合度高、可并行性差的问题,可充分发挥了多核并行计算优势,提高了并行时空索引性能。本文的研究成果为分布式并行计算环境下的海量三维、四维或更高维的时空数据的快速检索提供了可行、通用、高效的并行时空索引解决方案。后续研究将专注于分布式并行计算环境下时空索引的代价模型研究和时空数据安全问题研究。
【作者】郑祖芳;
【导师】吴冲龙;
【作者基本信息】中国地质大学,地学信息工程,2014,博士
【关键词】时空查询;时空索引;分布式计算;并行计算;间隔关系算子;

【参考文献】
[1]贾丽.洪湖湿地自然生态补偿研究[D].华中师范大学,自然地理学,2013,硕士.
[2]王琳琳.某市三级甲等医院医护人员疲劳现状及措施研究[D].大连医科大学,社会医学与卫生事业管理,2012,硕士.
[3]杨雪.试论中国古代法律的人性化关怀及当代借鉴[D].苏州大学,法律(专业学位),2014,硕士.
[4]岳德顺.社会管理创新的自组织路径研究[D].重庆大学,行政管理,2014,硕士.
[5]高凯.数字开关电源的研究与设计[D].华东交通大学,交通信息工程及控制,2013,硕士.
[6]王丹.废弃钢化玻璃微粉作矿物掺合料的研究[D].重庆大学,材料科学与工程,2014,硕士.
[7]赵琳琳.青海地区藏、汉族女性乳腺癌组织中VEGF-C和COX-2的表达及其意义[D].青海大学,外科学,2013,硕士.
[8]李世勇.滋癸安神汤治疗围绝经期肝肾阴虚型失眠症的临床研究[D].福建中医药大学,中医内科学(专业学位),2014,硕士.
[9]王磊.清热解毒除湿通痹法治疗原发性急性痛风性关节炎的临床观察[D].北京中医药大学,中医学,2014,硕士.
[10]张金水,王博,王心晨.氮化碳聚合物半导体光催化[J].化学进展,2014,01:19-29.
[11]丁丽曼.GSP的企业实施与国家监管差距问题的研究[D].黑龙江中医药大学,药剂学,2004,硕士.
[12]李穹.唐代日本人的汉语文化学习[D].曲阜师范大学,汉语国际教育(专业学位),2013,硕士.
[13]苑书金.鄂尔多斯盆地大牛地气田下石盒子组地震储层预测技术的研究和应用[J].石油地球物理勘探,2008,01:48-52+5+4+130.
[14]曹兴.热力系统动态过程故障神经网络诊断方法研究[D].华北电力大学,控制理论与控制工程,2012,硕士.
[15]王静.动词在口语中的表情性研究[D].首都师范大学,俄语语言文学,2014,硕士.
[16]池步云.革新开放后越南共产党执政党建设初探[D].华中师范大学,国际关系,2014,硕士.
[17]王一然.布的折叠语言在室内纺织品设计中的应用[D].西南交通大学,设计艺术学,2013,硕士.
[18]达桑.略谈藏族古代民间传说[D].西藏大学,藏语言文学,2014,硕士.
[19]熊少锋1,王卫红1,刘晓东2,3,王森1,武亮1.考虑导弹自动驾驶仪动态特性的带攻击角度约束制导律[J].控制与决策.
[20]于薇.上海国际航运中心的发展模式研究[D].大连海事大学,产业经济学,2014,硕士.
[21]孙焕良,李彤,吕立,张晓山.基于XML技术的数据仓库多维数据模型[J].小型微型计算机系统,2002,11:1306-1309.
[22]于浩.金属半导体接触界面的调制研究[D].复旦大学,2013.
[23]刘飞.我国房地产企业的核心竞争力研究[D].厦门大学,2001.
[24]孙志英.城市化对土壤质量演变的影响研究——以郑州市为例[D].河南农业大学,土壤学,2004,硕士.
[25]吴志华.色彩通感在审美活动中具有的价值[D].南昌大学,美术学,2012,硕士.
[26]王春花.无线闭塞中心的测试方法研究[D].北京交通大学,2008.
[27]张楠,夏禾,郭薇薇,夏超逸.京沪高速铁路南京大胜关长江大桥风—车—桥耦合振动分析[J].中国铁道科学,2009,01:41-48.
[28]郭海洋.GPS网平差应注意的几个问题[J].石油地球物理勘探,2003,01:95-101+119-112.
[29]吴瑞芳.分数阶微分在图像增强中的应用研究[D].广西民族大学,计算机应用技术,2013,硕士.
[30]伍强.风险厌恶及信息不对称假设下供应链契约协调机制研究[D].武汉纺织大学,企业管理,2013,硕士.
[31]赵宏波.相移数字全息显微术的相位畸变校正[D].苏州大学,光学,2014,硕士.
[32]沈一静.跨国财务会计外包风险识别、评价与应对[D].上海外国语大学,企业管理,2014,硕士.
[33]张英朝,邓苏,张维明,刘青宝.智能数据挖掘引擎的设计与实现[J].计算机科学,2002,10:11-13.
[34]欧海英,张为华,李晓斌,刘春梅.平行坐标可视化技术在固体火箭发动机优化设计中的应用[J].固体火箭技术,2004,04:255-259.
[35]欧珍.结核分枝杆菌TB10.4蛋白单克隆抗体研制与鉴定[D].扬州大学,预防兽医学,2011,硕士.
[36]杨敏芳.不同耕作措施与秸秆还田对稻麦两熟制农田土壤养分、微生物及碳库的影响[D].南京农业大学,生态学,2013,硕士.
[37]张秋华.企业部门内部控制制度的运用研究[D].首都经济贸易大学,会计(专业学位),2014,硕士.
[38]左琪.肾间质纤维化miR-21的表达及三芪口服液的调控研究[D].广州中医药大学,中医内科学(专业学位),2014,博士.
[39]李瑛.农村中小学教师教育责任感、职业认同与职业倦怠关系研究[D].河北师范大学,心理健康教育,2012,硕士.
[40]李志华.XHL家用电器有限公司供应链协同管理应用研究[D].山东大学,工商管理(专业学位),2013,硕士.
[41]孙鹏宇.人细胞色素P450 2C9和尖镰孢菌细胞色素P450 55A1在毕赤酵母中的表达[D].中南民族大学,生物化学与分子生物学,2013,硕士.
[42]苏韶生,杜宜.基于HIS的CDSS的探讨[J].医学信息,2005,12:1610-1611.
[43]邱艳敏.完善新型农村合作医疗制度的对策研究[D].东北大学,马克思主义中国化研究,2010,硕士.
[44]刘慧敏.论作为一种存在方式的网络虚拟存在[D].华侨大学,哲学,2014,硕士.
[45]孙杏丽.北京市新能源公交车产业竞争力研究[D].北京交通大学,2015.
[46]冯为国,田宏,刘志国.WBV系列微机补偿式单/三相稳压器[J].铁道通信信号.2003(04)
[47]朱璞.转玉米高光效C_4型pepc基因小麦群体光合生理特性研究[D].南京农业大学,作物遗传育种,2013,硕士.
[48]杨宜芳.我国食品添加剂安全问题的政府管制研究[D].湖北大学,行政管理,2012,硕士.
[49]陈志军,严海宇,蓝国钧,刘化章.助催化剂对Fe_(1-x)O基氨合成催化剂性能的影响[J].工业催化,2013,05:41-45.
[50]宋巍涛.船舶交流电力系统短路电流计算方法研究[D].东北电力大学,电气工程,2013,硕士.

相关推荐
更多