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

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

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

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

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

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

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