面向BSP模型的圖數(shù)據(jù)劃分算法的設(shè)計與實現(xiàn).pdf

1、隨著社會的發(fā)展，各種各樣的圖數(shù)據(jù)集變的越來越大，如微博、Twitter、人人網(wǎng)等社交網(wǎng)絡(luò)及通信網(wǎng)絡(luò)等。傳統(tǒng)的圖處理工具很難完成這些基于大數(shù)據(jù)集上的計算，因此，急需開發(fā)一種新的處理系統(tǒng)用于海量圖數(shù)據(jù)的計算。Google基于BSP模型提出的Pregel大圖處理系統(tǒng)，為設(shè)計和開發(fā)大規(guī)模圖處理系統(tǒng)提供了思路，著名的云計算為此提供了技術(shù)支持。圖數(shù)據(jù)劃分對基于BSP編程模型的大規(guī)模圖處理系統(tǒng)是一個不能避免的問題。特別在云計算環(huán)境下，更需要將圖數(shù)據(jù)劃

2、分為多個分區(qū)，交由集群中的計算節(jié)點并行處理。然而，傳統(tǒng)的圖劃分技術(shù)大多需要多次迭代，時間復(fù)雜度過高，且結(jié)果不保留頂點到分區(qū)的映射，所以并不適用于BSP模型下的圖數(shù)據(jù)劃分。因此，如何實現(xiàn)一個好的快速的劃分，具有極大的挑戰(zhàn)。
　　為此，在之前的工作中，項目組基于BSP模型、借鑒云計算編程模型Hadoop，開發(fā)了一個可以進行大圖計算的圖處理系統(tǒng)BC-BSP。本文主要設(shè)計并實現(xiàn)系統(tǒng)的數(shù)據(jù)劃分模塊下的數(shù)據(jù)劃分算法。主要貢獻如下：(1)提出一

3、個BSP作業(yè)運行代價模型，據(jù)此分析了作業(yè)運行時各個階段的時間開銷由哪些因素決定。(2)設(shè)計實現(xiàn)了三個算法:一，基于采樣直方圖的數(shù)據(jù)劃分算法(S amp le)。提交作業(yè)時，從輸入數(shù)據(jù)集采樣一定數(shù)量的記錄，并據(jù)此建立直方圖。劃分數(shù)據(jù)時，將落在相應(yīng)直方圖中的數(shù)據(jù)放到直方圖對應(yīng)的分區(qū)中。這樣，近似保證了分區(qū)內(nèi)頂點數(shù)的均衡。這種劃分算法能將同一網(wǎng)站的所有頁面劃分到一個分區(qū)。二，針對出度的均衡Hash數(shù)據(jù)劃分算法(BHP)。該算法引入了虛擬桶的概

4、念，使用貪心算法將虛擬桶重組為分區(qū)，保證了每個分區(qū)負載均衡。同時，本地化算法減小了數(shù)據(jù)加載時的數(shù)據(jù)遷移開銷。三，邊聚簇的BHP數(shù)據(jù)劃分算法(ECBHP)。該算法使用EC啟發(fā)式規(guī)則，評估了虛擬桶到各分區(qū)的拓撲密度，據(jù)此進行虛擬桶的重組，保證分區(qū)內(nèi)的圖頂點具有較高的耦合度，分區(qū)間具有較低的耦合度。
　　將本文提出的三種數(shù)據(jù)劃分算法應(yīng)用于BC-BSP系統(tǒng)中，通過實驗證明，三種算法完成了BC-BSP系統(tǒng)中圖劃分模塊的功能，具有良好的可擴展