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

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

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

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

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