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