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

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

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

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

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

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

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