【摘要】：近年來隨著社交網(wǎng)絡和語義網(wǎng)絡的興起,海量數(shù)據(jù)挖掘成為學術(shù)界和工業(yè)界關注的焦點問題。在大規(guī)模數(shù)據(jù)的分析計算中,單臺服務器的存儲和計算能力已無法滿足其對數(shù)據(jù)量和計算復雜度的需求。Apache基金會開發(fā)的開源項目Hadoop作為一種流行的分布式計算平臺,在很多涉及海量數(shù)據(jù)挖掘的產(chǎn)品和應用中發(fā)揮著重大作用。 在傳統(tǒng)的單機數(shù)據(jù)挖掘算法的實現(xiàn)中,數(shù)據(jù)集中存儲在本地硬盤上,在計算時讀入內(nèi)存中相應的數(shù)據(jù)結(jié)構(gòu)里,輔以一些高效的索引。在算法執(zhí)行過程中程序反復的讀取內(nèi)存中的數(shù)據(jù)進行計算,最終輸出結(jié)果到本地硬盤,控制臺或遠程客戶端。對于單機算法來說,我們只需考慮算法的有效性,時間空間復雜度,數(shù)據(jù)結(jié)構(gòu)的選擇和結(jié)果的展示。 隨著數(shù)據(jù)量的增加,單臺服務器的硬盤無法存儲全部的輸入輸出數(shù)據(jù),內(nèi)存也無法容納下計算中所產(chǎn)生的中間數(shù)據(jù),這時一種行之有效的方法是將單機算法改造成分布式算法,利用多臺機器進行分布式并行計算。在算法的分布式移植過程中需要考慮很多問題,例如數(shù)據(jù)的分布,計算的分布,結(jié)果的收集,各節(jié)點之間的網(wǎng)絡傳輸,集群節(jié)點的故障恢復等等。而Hadoop分布式計算平臺使開發(fā)者只需關注于計算本身,而網(wǎng)絡通信,故障恢復都由Hadoop來負責,這樣極大提高了分布式應用的開發(fā)效率。 當單機算法擴展到Hadoop分布式平臺上時,即成為Map(本地計算及數(shù)據(jù)再分配)-網(wǎng)絡傳輸Reduce(結(jié)果收集,合并計算)的模式。如何將原有的單機算法在Hadoop平臺上予以實現(xiàn)對學術(shù)界和工業(yè)界來說都是一個新的挑戰(zhàn)。在算法遷移過程中,數(shù)據(jù)如何分布,Map和Reduce的key,value執(zhí)行單元的選擇,如何節(jié)省網(wǎng)絡傳輸?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集群中機器的數(shù)量,滿足新的計算需求。 但經(jīng)過實驗發(fā)現(xiàn),將PageRank遷移到Hadoop上雖然滿足了可擴展性的需求,但是計算效率一般,本文提出了一種在Hadoop平臺上PageRank優(yōu)化算法,算法的核心思想是通過圖聚類改變Map和Reduce的key,value執(zhí)行單元的粒度,節(jié)省Map和Reduce之間的網(wǎng)絡傳輸?shù)拈_銷,平衡MapReduce計算資源,以提高整體的PageRank計算效率�？紤]到PageRank算法的執(zhí)行對象不僅有網(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)絡開銷,平衡計算資源,實現(xiàn)整體性能提升的優(yōu)化方法,為其他涉及迭代的圖挖掘迭代算法在Hadoop上的優(yōu)化提出了一種新的思路。
【圖文】：

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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前10條

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

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

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

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

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

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

7 李洋濤;李川;許超;雷曉;徐洪宇;唐常杰;楊寧;;空間評分:基于PageRank的信息網(wǎng)絡可視化中節(jié)點重要性度量[A];第29屆中國數(shù)據(jù)庫學術(shù)會議論文集（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)絡的關鍵詞抽取[A];第三屆全國信息檢索與內(nèi)容安全學術(shù)會議論文集[C];2007年

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

相關碩士學位論文 前10條

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

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

3 王磊;PageRank的算法改進[D];上海交通大學;2009年

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

5 姜sバ

本文編號：2544141