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

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

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

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