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

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

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

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

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

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