面向BSP模型的圖數據劃分算法的設計與實現.pdf

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

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

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

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