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

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

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

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

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