【摘要】：近年來隨著社交網(wǎng)絡(luò)和語義網(wǎng)絡(luò)的興起,海量數(shù)據(jù)挖掘成為學(xué)術(shù)界和工業(yè)界關(guān)注的焦點(diǎn)問題。在大規(guī)模數(shù)據(jù)的分析計(jì)算中,單臺(tái)服務(wù)器的存儲(chǔ)和計(jì)算能力已無法滿足其對(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í)行過程中程序反復(fù)的讀取內(nèi)存中的數(shù)據(jù)進(jìn)行計(jì)算,最終輸出結(jié)果到本地硬盤,控制臺(tái)或遠(yuǎn)程客戶端。對(duì)于單機(jī)算法來說,我們只需考慮算法的有效性,時(shí)間空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)的選擇和結(jié)果的展示。 隨著數(shù)據(jù)量的增加,單臺(tái)服務(wù)器的硬盤無法存儲(chǔ)全部的輸入輸出數(shù)據(jù),內(nèi)存也無法容納下計(jì)算中所產(chǎn)生的中間數(shù)據(jù),這時(shí)一種行之有效的方法是將單機(jī)算法改造成分布式算法,利用多臺(tái)機(jī)器進(jìn)行分布式并行計(jì)算。在算法的分布式移植過程中需要考慮很多問題,例如數(shù)據(jù)的分布,計(jì)算的分布,結(jié)果的收集,各節(jié)點(diǎn)之間的網(wǎng)絡(luò)傳輸,集群節(jié)點(diǎn)的故障恢復(fù)等等。而Hadoop分布式計(jì)算平臺(tái)使開發(fā)者只需關(guān)注于計(jì)算本身,而網(wǎng)絡(luò)通信,故障恢復(fù)都由Hadoop來負(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è)界來說都是一個(gè)新的挑戰(zhàn)。在算法遷移過程中,數(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ī)器的數(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ì)象不僅有網(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ì)算資源,實(shí)現(xiàn)整體性能提升的優(yōu)化方法,為其他涉及迭代的圖挖掘迭代算法在Hadoop上的優(yōu)化提出了一種新的思路。
【圖文】：

MapReduce 任務(wù)中有兩種主要的進(jìn)程：JobTracker 和 TaskTracker。JobTracker運(yùn)行在 Namenode 上，TaskTracker 運(yùn)行在 Datanode 上：客戶端會(huì)向JobTracker提交計(jì)算任務(wù)JobTracker從NameNode上得到需要的數(shù)據(jù)在HDFS上存儲(chǔ)的具體節(jié)點(diǎn)和位置。JobTracker找到有空閑或離所需數(shù)據(jù)最近的TaskTracker，用來執(zhí)行相應(yīng)的計(jì)算任務(wù)。執(zhí)行中的TaskTracker會(huì)被監(jiān)控，如果其沒有及時(shí)向JobTracker發(fā)送心跳信息，就會(huì)被JobTracker認(rèn)為該節(jié)點(diǎn)巖機(jī)，JobTracker會(huì)在其他的TaskTracker上重啟任務(wù)。當(dāng)執(zhí)行失敗時(shí)，TaskTracker會(huì)通知JobTracker，，JobTracker會(huì)決定如何應(yīng)對(duì)：JobTracker可能會(huì)在其他TaskTracker上重啟任務(wù)，甚至可能將此TaskTracker列入黑名單。當(dāng)計(jì)算任務(wù)完成后，JobTracker會(huì)更新狀態(tài)，客戶端從JobTracker得到返回

對(duì)比兩種方法在不同階段產(chǎn)生的數(shù)據(jù)量圖18的橫坐標(biāo)代表每輪PageRank迭代中的3個(gè)階段，1代表Map開始時(shí)，
【學(xué)位授予單位】：復(fù)旦大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 戚華春,黃德才,鄭月鋒;具有時(shí)間反饋的PageRank改進(jìn)算法[J];浙江工業(yè)大學(xué)學(xué)報(bào);2005年03期

2 黃德才;戚華春;;PageRank算法研究[J];計(jì)算機(jī)工程;2006年04期

3 楊彬;康慕寧;;基于概念的權(quán)重PageRank改進(jìn)算法[J];情報(bào)雜志;2006年11期

4 張麗;;PageRank算法的改進(jìn)[J];科學(xué)技術(shù)與工程;2007年05期

5 孔娟;馬亨冰;;PageRank算法的原理與解析[J];福建電腦;2007年01期

6 姜鑫維;趙岳松;;Topic PageRank——一種基于主題的搜索引擎[J];計(jì)算機(jī)技術(shù)與發(fā)展;2007年05期

7 劉松彬;都云程;施水才;;基于分解轉(zhuǎn)移矩陣的PageRank迭代計(jì)算方法[J];中文信息學(xué)報(bào);2007年05期

8 田甜;倪林;;基于PageRank算法的權(quán)威值不均衡分配問題[J];計(jì)算機(jī)工程;2007年18期

9 劉彤彤;伍小芹;;融入權(quán)威性與相關(guān)性的PageRank算法[J];信息技術(shù);2008年11期

10 李吉平;吳陳;曾慶軍;;基于轉(zhuǎn)移概率的PageRank算法研究[J];科學(xué)技術(shù)與工程;2008年08期

相關(guān)會(huì)議論文 前10條

1 ;Key Nodes Mining in Transport Networks Based on PageRank Algorithm[A];2009中國(guó)控制與決策會(huì)議論文集（3）[C];2009年

2 劉松彬;都云程;施水才;;基于分解轉(zhuǎn)移矩陣的PageRank迭代計(jì)算方法[A];內(nèi)容計(jì)算的研究與應(yīng)用前沿——第九屆全國(guó)計(jì)算語言學(xué)學(xué)術(shù)會(huì)議論文集[C];2007年

3 藺繼國(guó);徐錫山;;一種基于用戶點(diǎn)擊數(shù)據(jù)的個(gè)性化PageRank算法[A];第六屆全國(guó)信息檢索學(xué)術(shù)會(huì)議論文集[C];2010年

4 李文;李淼;張建;朱海;陳雷;;基于混淆網(wǎng)絡(luò)和PageRank的Nbest重排序[A];少數(shù)民族青年自然語言處理技術(shù)研究與進(jìn)展——第三屆全國(guó)少數(shù)民族青年自然語言信息處理、第二屆全國(guó)多語言知識(shí)庫(kù)建設(shè)聯(lián)合學(xué)術(shù)研討會(huì)論文集[C];2010年

5 陳小飛;王軼彤;馮小軍;;一種基于網(wǎng)頁(yè)質(zhì)量的PageRank算法改進(jìn)[A];第26屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）[C];2009年

6 劉菁菁;林鴻飛;楊志豪;;基于PageRank和錨文本的網(wǎng)頁(yè)排序研究[A];第三屆學(xué)生計(jì)算語言學(xué)研討會(huì)論文集[C];2006年

7 李洋濤;李川;許超;雷曉;徐洪宇;唐常杰;楊寧;;空間評(píng)分:基于PageRank的信息網(wǎng)絡(luò)可視化中節(jié)點(diǎn)重要性度量[A];第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

8 Jonathan J.H.Zhu;;PPS Sampling of Web Graph Using Preferential Jumping Strategy[A];Proceedings 2010 IEEE 2nd Symposium on Web Society[C];2010年

9 劉建毅;王菁華;王樅;;基于語言網(wǎng)絡(luò)的關(guān)鍵詞抽取[A];第三屆全國(guó)信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議論文集[C];2007年

10 ;Thinking with simple computer models:Modeling of social-economic systems[A];全國(guó)復(fù)雜系統(tǒng)研究論壇論文集（一）[C];2005年

相關(guān)碩士學(xué)位論文 前10條

1 蔡建超;基于PageRank算法的搜索引擎優(yōu)化研究[D];江南大學(xué);2008年

2 邵晶晶;基于PageRank排序算法改進(jìn)的若干研究[D];華中師范大學(xué);2009年

3 王磊;PageRank的算法改進(jìn)[D];上海交通大學(xué);2009年

4 張巍;基于PageRank算法的搜索引擎優(yōu)化策略研究[D];四川大學(xué);2005年

5 姜sバ

本文編號(hào)：2544141