基于MapReduce的PageRank計算系統(tǒng)的設(shè)計與實現(xiàn).pdf

1、隨著信息化時代的到來，各種信息以爆炸模式增長，導(dǎo)致圖的規(guī)模日益增大。以互聯(lián)網(wǎng)為例，近十幾年來，隨著互聯(lián)網(wǎng)的普及和Web2.0技術(shù)的推動，網(wǎng)頁排名計算和社交網(wǎng)絡(luò)分析日趨成為圖處理的熱點問題，由網(wǎng)頁和社交網(wǎng)絡(luò)構(gòu)成的大規(guī)模圖，動輒有數(shù)十億的頂點和上萬億的邊。以PageRank為例，按鄰接表形式存儲100億個圖頂點，每個頂點的存儲開銷為100字節(jié)，那么這個圖的存儲開銷將達到900GB左右。即便是傳統(tǒng)的圖處理應(yīng)用，如最優(yōu)運輸路線的確定，也隨著GP

2、RS技術(shù)的發(fā)展和網(wǎng)絡(luò)的日趨復(fù)雜而導(dǎo)致數(shù)據(jù)規(guī)模以幾何倍數(shù)增長。如此大規(guī)模的數(shù)據(jù)量，給圖的有效處理帶來了挑戰(zhàn)，也提供了機遇?？焖儆行У靥幚泶笠?guī)模圖，已經(jīng)成為經(jīng)濟社會發(fā)展的迫切需求。
　　本文針對以上的背景情況，以Hadoop下的MapReduce作為編程框架，以PageRank為例，構(gòu)建了一個基于MapReduce的PageRank計算系統(tǒng)，主要內(nèi)容包括：⑴采用開源工具Heritrix爬取了節(jié)點URL以及URL與URL的關(guān)系，并以特定

3、的數(shù)據(jù)格式進行存儲。⑵針對使用MapReduce計算PageRank過程中出現(xiàn)的數(shù)據(jù)傳輸量太大影響計算效率的問題，本文在數(shù)據(jù)預(yù)處理部分設(shè)計了圖鄰接表的生成算法，使用圖鄰接表來表示圖節(jié)點的信息，針對實現(xiàn)中存在的問題，提出了算法改進。⑶采用三種方案計算PageRank，分別是樸素的PageRank算法(Native-PR)，一次迭代啟動一次Job的PageRank算法(OIOJ-PR)、以及基于子圖劃分的PageRank算法(SGPB-PR

4、)。其中樸素的PageRank算法迭代計算一次PageRank值需要啟動兩個Job，執(zhí)行效率并不高，但相對于直接使用URL還是存在著很大的優(yōu)勢。一次迭代啟動一次Job計算PageRank算法是針對樸素PageRank算法的改進，在MapReduce過程中保持著圖節(jié)點的外鏈信息，減少了作業(yè)的啟動開銷，并在本地節(jié)點做了數(shù)據(jù)歸約，即使用Combiner?；谧訄D劃分的PageRank算法對圖頂點進行了范圍劃分，每個Map函數(shù)處理一個子圖，提高