面向大规模复杂数据处理的超图并行计算框架

摘要

近年来,大数据(Big Data)越来越多地被提及,人们用它来描述和定义信息爆炸时代产生的海量数据。随着云计算时代的来临,大数据才得以充分发挥其威力。过去人们采用抽样的方法,只对数据中的很小部分进行计算。现在,借助大数据技术,用户可以在完整的数据上进行并行计算。这从本质上要求高效的分布式计算环境的支撑。然而,在此之前的研究主要集中在底层方面,它很难提供一个一致的原语,使得用户不得不为各种应用编写不同的底层程序。
　　MapReduce的出现有效地解决了这个问题,其通过简单的编程模型,使得用户从编写底层程序中解放出来,只需将注意力放在上层应用。MapReduce提供的原语非常简单,然而正是这种简单,使得用户很难对复杂数据进行处理,用户不得不编写大量的MapReduce任务,结果往往导致执行效率低下。这就要求新的模型,它既能对复杂数据进行有效地表示,提供简单的编程模型;同时,又能给底层的优化提供扩展的空间。基于图模型的并行计算框架很好地解决了这个问题,它将数据用图来表示,通过对顶点的操作,提供了简单的上层编程模型;同时,底层的优化也包括了数据表示、图分区等等。基于图模型的框架主要包括Pregel和GraphLab。Pregel基于BSP模型,在计算时存在着超级步的概念,只有在一个超级步计算完成后,才能进行下一个超级步的计算,这使得单个节点可能成为整个系统的瓶颈。GraphLab提供了同步和异步的执行,异步的执行使得不需要超级步来同步的算法的运行变得高效。然而,这些图模型框架都是基于简单图,简单图即指图中的一条边只能连接两个顶点,它的缺陷是,针对社交网络等真实场景中经常出现的“组”的概念,其难以表达,而且会丢失其中的重要信息。
　　因此,为了解决以上问题,本文提出了基于超图的并行计算框架HGPC,它使用超图作为数据的表示。超图是指图中的一条边能连接两个甚至更多的顶点,这使得其很自然地支持组的概念。本文对HGPC中的数据表示进行了描述,并给出了上层的易于使用的MAN编程模型。本文还对HGPC中使用的两种超图分区方法进行了讨论,分别是随机贪心策略,以及并行多级分区算法。
　　为了验证HGPC框架的有效性,我们从新浪微博获取了相关的实验数据。为了高效、灵活地自动获取新浪微博这样的社交网络数据,本文还同时设计实现了一个可扩展的分布式数据抓取框架COLA。实验表明,COLA具有较好的效率和可扩展性。
　　基于HGPC框架,我们描述并实现超图中的链路预测算法,并在获取到的数据上进行了实验,实验表明,HGPC框架能够充分描述基于超图模型的算法,性能方面也能较高效地执行。

目录

封面

声明

中文摘要

英文摘要

目录

插图索引

表格索引

第一章绪论

1 .1 研究背景与意义

1 .2 国内外研究现状

1 .3 研究内容

1 .4 论文组织结构

1 .5 本章小结

第二章相关技术研究

2.1 MapReduce

2.2 Pregel

2.3 GraphLab 和PowerGraph

2 .4 本章小结

第三章基于超图的并行计算框架HGPC

3 .1 什么是超图

3 .2 为什么需要超图

3 .3 数据模型

3 .4 超图模型面临的挑战

3 .5 数据表不

3 .6 编程模型

3 .7 超图计算的同步和异步执行

3 .8 超图分区

3.9 HGPC框架的架构与实现

3 .1 0本章小结

第四章实验验证与应用

4.1 应用相关定义

4 .2 数据准备

4 .3 应用实验设计

4 .4 实验结果

4 .5 本章小结

第五章分布式抓取框架COLA

5 .1 系统架构

5 .2 编程模型

5 .3 实验

5 .4 本章小结

第六章总结与展望

参考文献

致谢

攻读学位期间发表的学术论文目录