云环境下空间大数据连接查询处理算法的研究与实现

《云环境下空间大数据连接查询处理算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文云环境下空间大数据连接查询处理算法的研究与实现作者姓名：陈洋指导教师：乔百友副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机软件与理论论文提交日期：2014年6月日论文答辩日期：2014年6月21日学位授予日期：2014年7月日答辩委员黼：乔建忠教授评阅人：王波涛教授陈廷伟教授东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandImplementationoftheBi

2、gSpatialDataJoinQueryProcessingAlgorithmsinCloudEnvironmentByChenYangSupervisor：AssociateProfessorQiaoBaiyouNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导F完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何

3、贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：傅许日期：2Dl眵／。6／f寥学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时问为作者获得学位后：导师签名：／豸tz丕／／签字日期：7∥／，。．f．f少吖轧限钳豫∽～弘．o：卅万方数据东北大学硕士学位论文摘要云环境下空间

4、大数据连接查询处理算法的研究及实现摘要随着对地观测技术和位置服务技术的快速发展，空间数据规模急剧增加，已成为大空间数据，如何利用云计算对这类数据进行高效的空间连接查询处理，是当前空间数据管理领域的研究热点之一。现有的基于MapReduce的空间连接查询处理算法，如PPBSM等存在过滤能力弱、数据过度复制等问题，并且计算后还需要进行重复避免，这样带来了额外的CPU和I／O代价。为此，本文针对空间连接查询存在的问题，进行了深入研究，主要做了以下几方面的工作。首先，针对现有MapReduce空间连接查询处理算

5、法存在的过度复制等问题，提出了两种空间连接查询优化算法，即基于过滤的空间连接查询优化算法(FBSJ)和基于网格扩充的空间连接优化算法(GEBSJ)。FBSJ算法利用经过收缩的内部网格的MBR过滤掉部分无用的跨分区单元对象，降低了Reduce阶段的计算代价。GEBSJ算法采用基于R-tree的网格索引来过滤无用连接对象，并减少连接对象的多余复制。该算法利用一类数据预处理扩充原始网格并构建网格索引，另外一类数据搜索网格索引进行数据复制，这样会降低数据的复制量同时无需重复避免，分别从CPU和I／O角度优化了算

6、法。其次，提出了一种改进的基于分布式R木树索引的空间连接查询处理算法。本文引入分布式R木树并对其进行了改进，首先按照Hilbert空间填充曲线编码使得空间区域数据实现均匀划分，并在每个分区中构建局部R枣树索引，然后利用这些分布式R木树索引构建一个全局索引信息文件。在进行连接计算时，如果两类数据集都存在索引，则利用全局索引信息文件生成任务队列，然后执行基于R木树的连接查询处理；如果只有一类数据集存在索引，则充分利用该索引信息将无索引数据复制分配到各个子索引所在的Reducer任务上并行构建索引，然后再执行

7、基于R枣树的连接查询处理。由于分布式索引的存在，相对于处理无索引数据的PPBSM算法，查询性能最高能提升38．5％。最后，通过实际数据集和合成数据集上的大量实验，对本文所提出的两类空间连接查询处理算法进行了测试分析。实验结果表明，本文所提出的两种无数据索引空间连接查询优化算法的性能要明显优于PPBSM算法；而采用分布式索引的空间连接查询处理算法能够大大加快空间连接查询处理速度，具有良好的性能和适应性。关键词：空间连接查询；分布式R*-tree；复制优化；MapReduce；云计算一II—万方数据东北大学

8、硕士学位论文AbstractResearchandImplementationoftheBigSpatialDataJoinQueryProcessingAlgorithmsinCloudEnvironmentAbstractWiththerapiddevelopmentofearthobservationandlocation—basedservicetechnology，thevolumeofspatialdatahasgreatlyi