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

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:uan998
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,大数据(Big Data)越来越多地被提及,人们用它来描述和定义信息爆炸时代产生的海量数据。随着云计算时代的来临,大数据才得以充分发挥其威力。过去人们采用抽样的方法,只对数据中的很小部分进行计算。现在,借助大数据技术,用户可以在完整的数据上进行并行计算。这从本质上要求高效的分布式计算环境的支撑。然而,在此之前的研究主要集中在底层方面,它很难提供一个一致的原语,使得用户不得不为各种应用编写不同的底层程序。MapReduce的出现有效地解决了这个问题,其通过简单的编程模型,使得用户从编写底层程序中解放出来,只需将注意力放在上层应用。MapReduce提供的原语非常简单,然而正是这种简单,使得用户很难对复杂数据进行处理,用户不得不编写大量的MapReduce任务,结果往往导致执行效率低下。这就要求新的模型,它既能对复杂数据进行有效地表示,提供简单的编程模型;同时,又能给底层的优化提供扩展的空间。基于图模型的并行计算框架很好地解决了这个问题,它将数据用图来表示,通过对顶点的操作,提供了简单的上层编程模型;同时,底层的优化也包括了数据表示、图分区等等。基于图模型的框架主要包括Pregel和GraphLab。Pregel基于BSP模型,在计算时存在着超级步的概念,只有在一个超级步计算完成后,才能进行下一个超级步的计算,这使得单个节点可能成为整个系统的瓶颈。GraphLab提供了同步和异步的执行,异步的执行使得不需要超级步来同步的算法的运行变得高效。然而,这些图模型框架都是基于简单图,简单图即指图中的一条边只能连接两个顶点,它的缺陷是,针对社交网络等真实场景中经常出现的“组”的概念,其难以表达,而且会丢失其中的重要信息。因此,为了解决以上问题,本文提出了基于超图的并行计算框架HGPC,它使用超图作为数据的表示。超图是指图中的一条边能连接两个甚至更多的顶点,这使得其很自然地支持组的概念。本文对HGPC中的数据表示进行了描述,并给出了上层的易于使用的MAN编程模型。本文还对HGPC中使用的两种超图分区方法进行了讨论,分别是随机贪心策略,以及并行多级分区算法。为了验证HGPC框架的有效性,我们从新浪微博获取了相关的实验数据。为了高效、灵活地自动获取新浪微博这样的社交网络数据,本文还同时设计实现了一个可扩展的分布式数据抓取框架COLA。实验表明,COLA具有较好的效率和可扩展性。基于HGPC框架,我们描述并实现超图中的链路预测算法,并在获取到的数据上进行了实验,实验表明,HGPC框架能够充分描述基于超图模型的算法,性能方面也能较高效地执行。
其他文献
为揭示南方红豆杉种子休眠及其解除的机理,为农林业生产上种子休眠的解除提供科学依据,将南方红豆杉种子用300mg/L的赤霉素浸泡2d,浓硫酸处理1min后与湿沙混匀,先在4℃下低温
德拉克洛瓦是19世纪浪漫主义绘画的领军人物,这位才华横溢的画家,有着丰富的想象力和炽热的情感,生性豪迈,画风气场强大,被称为“浪漫派的狮子”。本文就从他的家世与性格,艺
家具板材优化排料,是家具在产品设计、制造和使用过程中如何节约人造板材、优化利用资源的问题,有重要经济意义和社会效益。它在计算上非常复杂和困难,目前还不能从理论上精
《圣经》是一部博大精深的文本,20世纪中叶以来对它的文学阐释涉及了意识形态、社会、历史、政治和文化等丰富的内容。本文就《圣经》的文学阐释所引发的认知方面问题进行了
中原传统民居装饰艺术源远流长,具有鲜明的地域性及原生的景观环境优越性,深刻地影响到现代生活的各个方面。在现代语境下,室内设计作为社会文化的构成部分,如何传承传统文化
非线性压缩感知是指仅利用信号的非线性测量值恢复原始信号,而相位恢复问题是一种特殊的非线性压缩感知问题,即利用信号傅里叶变换或其它线性变换的幅值恢复原始信号。由于观
进入新世纪以来,英语已经成为人们对外交流的主要语言。高职院校的目标是培养具有综合素质的技术人才,直接服务于社会建设。在工作中,这些人才需要进行国际交流,学习外国的先
目的探讨细胞色素P450 2C19 (CYP2C19)基因多态性与老年人脑梗死的相关性。方法采用基因芯片技术对浙江医院72例新发的老年急性脑梗死患者(病例组)和77例同期住院体检者(对照
<正>1月28日,农历腊月十二,室外白雪皑皑,厅内却是融融暖冬。"新春遇见茶"———中茶博戊戌雅集,在主持人的欢声笑语中拉开序幕,开启了温馨的下午时光。雅集以禅舞开场,后有
探讨郁证性泄泻的病脉证治。由情志因素导致或加重的泄泻,且从郁论治或辅以从郁论治有效者,概为郁证性泄泻,主要包括怒泄、惊泻、肝泄以及心劳、脾劳、肺劳泄泻等类型。其病