面向大規(guī)模復(fù)雜數(shù)據(jù)處理的超圖并行計(jì)算框架.pdf

1、近年來(lái),大數(shù)據(jù)(Big Data)越來(lái)越多地被提及,人們用它來(lái)描述和定義信息爆炸時(shí)代產(chǎn)生的海量數(shù)據(jù)。隨著云計(jì)算時(shí)代的來(lái)臨,大數(shù)據(jù)才得以充分發(fā)揮其威力。過(guò)去人們采用抽樣的方法,只對(duì)數(shù)據(jù)中的很小部分進(jìn)行計(jì)算。現(xiàn)在,借助大數(shù)據(jù)技術(shù),用戶可以在完整的數(shù)據(jù)上進(jìn)行并行計(jì)算。這從本質(zhì)上要求高效的分布式計(jì)算環(huán)境的支撐。然而,在此之前的研究主要集中在底層方面,它很難提供一個(gè)一致的原語(yǔ),使得用戶不得不為各種應(yīng)用編寫不同的底層程序。
　　MapRedu

2、ce的出現(xiàn)有效地解決了這個(gè)問(wèn)題,其通過(guò)簡(jiǎn)單的編程模型,使得用戶從編寫底層程序中解放出來(lái),只需將注意力放在上層應(yīng)用。MapReduce提供的原語(yǔ)非常簡(jiǎn)單,然而正是這種簡(jiǎn)單,使得用戶很難對(duì)復(fù)雜數(shù)據(jù)進(jìn)行處理,用戶不得不編寫大量的MapReduce任務(wù),結(jié)果往往導(dǎo)致執(zhí)行效率低下。這就要求新的模型,它既能對(duì)復(fù)雜數(shù)據(jù)進(jìn)行有效地表示,提供簡(jiǎn)單的編程模型;同時(shí),又能給底層的優(yōu)化提供擴(kuò)展的空間?；趫D模型的并行計(jì)算框架很好地解決了這個(gè)問(wèn)題,它將數(shù)據(jù)用圖來(lái)

3、表示,通過(guò)對(duì)頂點(diǎn)的操作,提供了簡(jiǎn)單的上層編程模型;同時(shí),底層的優(yōu)化也包括了數(shù)據(jù)表示、圖分區(qū)等等。基于圖模型的框架主要包括Pregel和GraphLab。Pregel基于BSP模型,在計(jì)算時(shí)存在著超級(jí)步的概念,只有在一個(gè)超級(jí)步計(jì)算完成后,才能進(jìn)行下一個(gè)超級(jí)步的計(jì)算,這使得單個(gè)節(jié)點(diǎn)可能成為整個(gè)系統(tǒng)的瓶頸。GraphLab提供了同步和異步的執(zhí)行,異步的執(zhí)行使得不需要超級(jí)步來(lái)同步的算法的運(yùn)行變得高效。然而,這些圖模型框架都是基于簡(jiǎn)單圖,簡(jiǎn)單圖即

4、指圖中的一條邊只能連接兩個(gè)頂點(diǎn),它的缺陷是,針對(duì)社交網(wǎng)絡(luò)等真實(shí)場(chǎng)景中經(jīng)常出現(xiàn)的“組”的概念,其難以表達(dá),而且會(huì)丟失其中的重要信息。
　　因此,為了解決以上問(wèn)題,本文提出了基于超圖的并行計(jì)算框架HGPC,它使用超圖作為數(shù)據(jù)的表示。超圖是指圖中的一條邊能連接兩個(gè)甚至更多的頂點(diǎn),這使得其很自然地支持組的概念。本文對(duì)HGPC中的數(shù)據(jù)表示進(jìn)行了描述,并給出了上層的易于使用的MAN編程模型。本文還對(duì)HGPC中使用的兩種超圖分區(qū)方法進(jìn)行了討論,

5、分別是隨機(jī)貪心策略,以及并行多級(jí)分區(qū)算法。
　　為了驗(yàn)證HGPC框架的有效性,我們從新浪微博獲取了相關(guān)的實(shí)驗(yàn)數(shù)據(jù)。為了高效、靈活地自動(dòng)獲取新浪微博這樣的社交網(wǎng)絡(luò)數(shù)據(jù),本文還同時(shí)設(shè)計(jì)實(shí)現(xiàn)了一個(gè)可擴(kuò)展的分布式數(shù)據(jù)抓取框架COLA。實(shí)驗(yàn)表明,COLA具有較好的效率和可擴(kuò)展性。
　　基于HGPC框架,我們描述并實(shí)現(xiàn)超圖中的鏈路預(yù)測(cè)算法,并在獲取到的數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn),實(shí)驗(yàn)表明,HGPC框架能夠充分描述基于超圖模型的算法,性能方面也能較