并行樹和圖計算框架的分布式實現(xiàn).pdf

1、樹(如二叉樹或一般樹)是一種重要的數(shù)據(jù)結構,它經常被用來表示像數(shù)學表達式或結構性文檔(如XML)這樣的分層數(shù)據(jù)結構。雖然樹結構被廣泛應用在串行程序中,但由于其不規(guī)則和不平衡的結構特點,使得開發(fā)有效率的在樹上進行計算的并行程序變得很困難。雖然目前已經存在不少關于樹的并行化研究,但設計高效的適合于分布式系統(tǒng)的樹并行化算法仍然是個挑戰(zhàn)。
　　另一方面,大型的網絡(圖)開始普遍存在于很多領域中,如生物、物理、化學、通訊和社交網絡等。人們日

2、益增長的對大規(guī)模圖數(shù)據(jù)進行分析的需求對圖并行化的研究提出了挑戰(zhàn)。很多圖優(yōu)化問題(如最大權重獨立集問題)是NP困難的。解決這樣的圖問題需要的計算復雜度通常和圖的大小呈指數(shù)關系,即與圖上的頂點數(shù)或邊數(shù)成指數(shù)關系。對于那些大規(guī)模的圖,極高的計算復雜度使得這些圖問題即使利用計算機集群也很難計算出結果。幸運的是,研究者發(fā)現(xiàn),很多圖上的NP困難問題在具有有限樹寬的圖上可以使用動態(tài)規(guī)劃技術和樹分解在多項式時間內進行求解。
　　本課題對國內外樹并

3、行化和圖并行化相關的工作進行了研究。通過擴展第三同態(tài)定理在樹上的應用和zipper結構,提出了適合于分布式環(huán)境并可應用于MapReduce模型上的樹并行框架。由于樹分解從數(shù)據(jù)結構角度來看是樹結構,本課題提出了把樹分解上自底向上的動態(tài)規(guī)劃算法轉化為在zipper結構上的并行算法的方法。通過結合所提出的樹并行化框架和樹分解技術,提出了適用于分布式環(huán)境的圖并行化框架,從而實現(xiàn)了圖優(yōu)化類問題的高效并行化。
　　本論文的主要貢獻有如下幾個方