基于bsp的高性能大图迭代计算的研究与实现

《基于bsp的高性能大图迭代计算的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC学位论文基于BSP的高性能大图迭代计算的研究与实现作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：刘金鹏于戈教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答懒蝴：申德荣鲍玉斌夏秀峰东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandImplementationonBSP··BasedHighPerformanceIterativeComputationforLargeG

2、raphsbyLiuJinpengSupervisor：ProfessorYuGeNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名：今1如糯Et期：Ⅵ汁、6。沈学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权

3、保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：两年口导师签名：彳戈签字目期：沙{哏6．巧，万方数据东北大学硕士学位论文摘要基于BSP的高性能大图迭代计算的研究与实现摘要随着信息技术的快速发展与广泛应用，如何有效管理、高效处理大量的信息数据已经成为学术界与工业界面临的重要挑战。如社交网络、传感器网络及电商交易等应用中的数据具有图的结构，并且在科学研究中具有巨大的价值，因此成为了“大数据”研究的热点。Google公司提出的

4、MapReduce分布式计算框架，能够支持各种类型的大数据应用处理，但是对于图应用的算法，如单源最短路径、子图挖掘等，通常需要多次迭代并交换中间结果数据，迭代过程中数据处理并行化的缺失导致MapReduce不适合处理大图计算。以Google提出的Pregel为代表的基于BSP模型的大图处理系统，已经成为目前大图处理的重要手段，但是在消息通信与图迭代磁盘处理等方面仍存在不足。本文以BSP模型为基础，围绕消息通信与磁盘迭代处理两个方面研究如何提高图处理系统的效率。首先，建立一个简单有效的消息传递通信结构，通过控制相关参数保证基本通信性能。其次，在其基础上，结合广播消息

5、类图算法，提出一种基于边聚簇的边界点备份策略(ECBVR)，并建立代价估计模型分析消息通信的优化对系统处理性能的作用效果，同时，围绕ECBVR，提出点．边计算模型，并优化边计算过程，设计Hash索引和多队列并行顺序索引两种机制进一步提高系统的处理效率。再次，在图迭代磁盘处理方面，建立内存分配模型以提高数据内存驻留率，提出数据分组迭代(DGI)与消息有序迭代(MSI)两种迭代处理机制避免磁盘随机访问。对于DGI方式，讨论了两种分组算法：随机Hash分组与均衡分组：对于MSI方式，设计了新的数据存储模型OERSV以保证消息的接收有序，同时为避免对顶点有序表的随机磁盘访

6、问建立分页机制。本文的相关技术在BC．BSP大规模图处理系统的框架下实现，并在合成数据集与真实数据集上完成相关实验。对于ECBVR技术，通过分析边聚簇划分阈值对通信规模、处理速度及数据加载时间的影响，可以确定ECBVR的有效性，通过对三种不同的实现方式的对比，验证了索引的有效性，并发现该技术对高出度图数据较为有效。对于磁盘处理技术，验证内存分配参数对数据内存驻留率的影响，参数的实际最优取值接近理论值，并对比分析本文提出的两类磁盘迭代处理方式处理性能和处理能力的差异。最后将本文提出的相关技术集成到BC．BSP系统中，通过与其他系统进行PageRank实验对比，证明B

7、C—BSP是高性能的，其处理效率是Haloop的10倍以上。关键词：BSP；大图迭代计算；边界点备份；基于磁盘的迭代；高效索弓一II—万方数据东北大学硕士学位论文AbstractResearchandImplementationonBSP—BasedHighPerformanceIterativeComputationforLargeGraphsAbstractWiththerapiddevelopmentandwideapplicationofinformationtechnology,theeffectivemanagementandefficientproc

8、essin