Hadoop上的PageRank算法優(yōu)化.pdf

1、近年來隨著社交網(wǎng)絡(luò)和語義網(wǎng)絡(luò)的興起，海量數(shù)據(jù)挖掘成為學(xué)術(shù)界和工業(yè)界關(guān)注的焦點問題。在大規(guī)模數(shù)據(jù)的分析計算中，單臺服務(wù)器的存儲和計算能力已無法滿足其對數(shù)據(jù)量和計算復(fù)雜度的需求。Apache基金會開發(fā)的開源項目Hadoop作為一種流行的分布式計算平臺，在很多涉及海量數(shù)據(jù)挖掘的產(chǎn)品和應(yīng)用中發(fā)揮著重大作用。
　　在傳統(tǒng)的單機數(shù)據(jù)挖掘算法的實現(xiàn)中，數(shù)據(jù)集中存儲在本地硬盤上，在計算時讀入內(nèi)存中相應(yīng)的數(shù)據(jù)結(jié)構(gòu)里，輔以一些高效的索引。在算法執(zhí)行過

2、程中程序反復(fù)的讀取內(nèi)存中的數(shù)據(jù)進行計算，最終輸出結(jié)果到本地硬盤，控制臺或遠程客戶端。對于單機算法來說，我們只需考慮算法的有效性，時間空間復(fù)雜度，數(shù)據(jù)結(jié)構(gòu)的選擇和結(jié)果的展示。
　　隨著數(shù)據(jù)量的增加，單臺服務(wù)器的硬盤無法存儲全部的輸入輸出數(shù)據(jù)，內(nèi)存也無法容納下計算中所產(chǎn)生的中間數(shù)據(jù)，這時一種行之有效的方法是將單機算法改造成分布式算法，利用多臺機器進行分布式并行計算。在算法的分布式移植過程中需要考慮很多問題，例如數(shù)據(jù)的分布，計算的分布，

3、結(jié)果的收集，各節(jié)點之間的網(wǎng)絡(luò)傳輸，集群節(jié)點的故障恢復(fù)等等。而Hadoop分布式計算平臺使開發(fā)者只需關(guān)注于計算本身，而網(wǎng)絡(luò)通信，故障恢復(fù)都由Hadoop來負責(zé)，這樣極大提高了分布式應(yīng)用的開發(fā)效率。
　　當單機算法擴展到Hadoop分布式平臺上時，即成為Map（本地計算及數(shù)據(jù)再分配）-＞網(wǎng)絡(luò)傳輸-＞Reduce（結(jié)果收集，合并計算）的模式。如何將原有的單機算法在Hadoop平臺上予以實現(xiàn)對學(xué)術(shù)界和工業(yè)界來說都是一個新的挑戰(zhàn)。在算法遷移

4、過程中，數(shù)據(jù)如何分布，Map和Reduce的key，value執(zhí)行單元的選擇，如何節(jié)省網(wǎng)絡(luò)傳輸?shù)拈_銷都是開發(fā)者需要考慮的問題。
　　PageRank算法是谷歌公司提出的網(wǎng)頁排序算法，用于在搜索引擎中對網(wǎng)頁進行打分，隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)頁的數(shù)量以指數(shù)級增長，遠遠超過了單臺機器的存儲和計算能力。如果能將PageRank算法遷移到Hadoop上實現(xiàn)多機并行計算，就可以實現(xiàn)可擴展性，即當網(wǎng)頁數(shù)量不斷增加時，通過動態(tài)增加Hadoop集群中機

5、器的數(shù)量，滿足新的計算需求。
　　但經(jīng)過實驗發(fā)現(xiàn)，將PageRank遷移到Hadoop上雖然滿足了可擴展性的需求，但是計算效率一般，本文提出了一種在Hadoop平臺上PageRank優(yōu)化算法，算法的核心思想是通過圖聚類改變Map和Reduce的key，value執(zhí)行單元的粒度，節(jié)省Map和Reduce之間的網(wǎng)絡(luò)傳輸?shù)拈_銷，平衡MapReduce計算資源，以提高整體的PageRank計算效率?？紤]到PageRank算法的執(zhí)行對象不僅

6、有網(wǎng)頁數(shù)據(jù)，還可能有其他的圖數(shù)據(jù)，當圖本身很稀疏或聚類效果不佳時，優(yōu)化算法可能并不適用，本文針對上述情況建立了一個Cost Model，其目的是在PageRank迭代執(zhí)行前判斷優(yōu)化算法的效果，如果優(yōu)化效果不佳則選擇原算法進行PageRank計算。
　　本文詳細闡述了如何在Hadoop平臺上實現(xiàn)和優(yōu)化PageRank迭代算法。提出了以圖劃分將MapReduce計算單元由圖結(jié)點變?yōu)樽訄D，以降低Map和Reduce之間的網(wǎng)絡(luò)開銷，平衡計