大規(guī)模圖上的最小生成樹并行算法研究.pdf

1、最小生成樹(MST)作為圖論中最經(jīng)典算法之一，引發(fā)了人們經(jīng)久不衰的關(guān)注。由于MST的性質(zhì)，在規(guī)劃、網(wǎng)絡(luò)和醫(yī)學(xué)等各個領(lǐng)域得到了廣泛的應(yīng)用。同時，基于MST結(jié)構(gòu)的聚類、分類和最短路徑查詢等復(fù)雜圖算法，在效率和結(jié)果質(zhì)量方面均有顯著提高。然而，隨著互聯(lián)網(wǎng)的迅猛發(fā)展，圖規(guī)模也變得越來越大，包含千萬甚至上億個頂點的大規(guī)模圖越發(fā)常見。因此，如何在大規(guī)模圖上實現(xiàn)查詢處理和數(shù)據(jù)挖掘算法已成為了亟待解決的問題之一。除此之外，由于大規(guī)模圖的動態(tài)性特征，即圖的

2、拓?fù)浣Y(jié)構(gòu)可能會發(fā)生改變，如何動態(tài)地維護(hù)算法結(jié)果也勢必成為最受關(guān)注的問題之一。
　　本文提出并行MST算法和MST動態(tài)維護(hù)算法，為上述問題提供了堅實的基礎(chǔ)。
　　首先，本文利用以邊為中心的設(shè)計思想，提出了邊驅(qū)動的并行MST算法。同時，本文設(shè)計了分布式索引、分區(qū)加速和基于直方圖排序等優(yōu)化技術(shù)，提高了算法的執(zhí)行效率。隨后，基于不同的通信模型實現(xiàn)了并行MST算法并分析了算法的時間復(fù)雜度。實驗驗證了算法的有效性，以及分布式索引和基于直

3、方圖排序技術(shù)的高效性。
　　其次，本文從頂點為中心的角度出發(fā)，提出了頂點驅(qū)動的并行MST算法PB，并論證了PB算法的正確性。另外，本文給出了PB算法的終止條件和索引維護(hù)策略。隨后，分別列出了基于MapReduce和BSP框架的PB算法的整體執(zhí)行過程，其中包括啟動作業(yè)和循環(huán)作業(yè)的詳細(xì)處理流程。同時，本文分別針對上述框架剖析了PB算法的時間復(fù)雜度。實驗證明了PB算法的有效性、高效性和可擴(kuò)展性。
　　最后，針對圖的動態(tài)性特征，本文

4、定義了動態(tài)圖的五種操作并提出了MST結(jié)果的分布式動態(tài)維護(hù)算法MTBM。同時，本文給出了二次劃分和分布式MST構(gòu)建等預(yù)處理算法。在預(yù)處理之后，分別針對插入、刪除和修改等操作，設(shè)計了相應(yīng)的維護(hù)策略，并分析了MTBM算法執(zhí)行代價。實驗證明了MTBM算法的可靠性和高效性。
　　總之，本文從大規(guī)模圖角度出發(fā)，針對MST問題展開一系列研究，分別提出了邊驅(qū)動和頂點驅(qū)動的并行MST算法以及MST結(jié)果的分布式動態(tài)維護(hù)算法。本文的研究工作，即大規(guī)模圖