基于BSP的高性能大圖迭代計(jì)算的研究與實(shí)現(xiàn).pdf

1、隨著信息技術(shù)的快速發(fā)展與廣泛應(yīng)用，如何有效管理、高效處理大量的信息數(shù)據(jù)已經(jīng)成為學(xué)術(shù)界與工業(yè)界面臨的重要挑戰(zhàn)。如社交網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)及電商交易等應(yīng)用中的數(shù)據(jù)具有圖的結(jié)構(gòu)，并且在科學(xué)研究中具有巨大的價(jià)值，因此成為了“大數(shù)據(jù)”研究的熱點(diǎn)。Google公司提出的MapReduce分布式計(jì)算框架，能夠支持各種類型的大數(shù)據(jù)應(yīng)用處理，但是對(duì)于圖應(yīng)用的算法，如單源最短路徑、子圖挖掘等，通常需要多次迭代并交換中間結(jié)果數(shù)據(jù)，迭代過程中數(shù)據(jù)處理并行化的缺失導(dǎo)

2、致MapReduce不適合處理大圖計(jì)算。以Google提出的Pregel為代表的基于BSP模型的大圖處理系統(tǒng)，已經(jīng)成為目前大圖處理的重要手段，但是在消息通信與圖迭代磁盤處理等方面仍存在不足。
　　本文以BSP模型為基礎(chǔ)，圍繞消息通信與磁盤迭代處理兩個(gè)方面研究如何提高圖處理系統(tǒng)的效率。首先，建立一個(gè)簡(jiǎn)單有效的消息傳遞通信結(jié)構(gòu)，通過控制相關(guān)參數(shù)保證基本通信性能。其次，在其基礎(chǔ)上，結(jié)合廣播消息類圖算法，提出一種基于邊聚簇的邊界點(diǎn)備份策略

3、(ECBVR)，并建立代價(jià)估計(jì)模型分析消息通信的優(yōu)化對(duì)系統(tǒng)處理性能的作用效果，同時(shí)，圍繞ECBVR，提出點(diǎn)-邊計(jì)算模型，并優(yōu)化邊計(jì)算過程，設(shè)計(jì)Hash索引和多隊(duì)列并行順序索引兩種機(jī)制進(jìn)一步提高系統(tǒng)的處理效率。再次，在圖迭代磁盤處理方面，建立內(nèi)存分配模型以提高數(shù)據(jù)內(nèi)存駐留率，提出數(shù)據(jù)分組迭代(DGI)與消息有序迭代(MSI)兩種迭代處理機(jī)制避免磁盤隨機(jī)訪問。對(duì)于DGI方式，討論了兩種分組算法:隨機(jī)Hash分組與均衡分組;對(duì)于MSI方式，設(shè)

4、計(jì)了新的數(shù)據(jù)存儲(chǔ)模型OERSV以保證消息的接收有序，同時(shí)為避免對(duì)頂點(diǎn)有序表的隨機(jī)磁盤訪問建立分頁機(jī)制。
　　本文的相關(guān)技術(shù)在BC-BSP大規(guī)模圖處理系統(tǒng)的框架下實(shí)現(xiàn)，并在合成數(shù)據(jù)集與真實(shí)數(shù)據(jù)集上完成相關(guān)實(shí)驗(yàn)。對(duì)于ECBVR技術(shù)，通過分析邊聚簇劃分閾值對(duì)通信規(guī)模、處理速度及數(shù)據(jù)加載時(shí)間的影響，可以確定ECBVR的有效性，通過對(duì)三種不同的實(shí)現(xiàn)方式的對(duì)比，驗(yàn)證了索引的有效性，并發(fā)現(xiàn)該技術(shù)對(duì)高出度圖數(shù)據(jù)較為有效。對(duì)于磁盤處理技術(shù)，驗(yàn)證內(nèi)存