【正文】 tent BURL， Bcontent CURL， Ccontent DURL， Dcontent 輸出為： BURL， AURL， 1/12 CURL， AURL， 1/12 DURL， AURL， 1/12 AURL， BURL， CURL， DURL AURL， BURL， 1/8 CURL， BURL， 1/8 BURL， AURL， CURL DURL， CURL， 1/4 CURL， DURL AURL， DURL， 1/8 BURL， DURL， 1/8 DURL， AURL， BURL 2. 階段 2： PageRank分配 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 PageRank算法在 MapReduce中的實(shí)現(xiàn) ? 然后，在該階段的 Reduce階段， Reduce任務(wù)會(huì)獲得 URL， url_list和 u， URL, cur_rank/|url_list|， Reduce任務(wù)對(duì)于具有相同 key值的 value進(jìn)行匯總，并把匯總結(jié)果乘以 d，得到每個(gè)網(wǎng)頁的新的 PageRank值 new_rank，然后輸出 URL，new_rank， url_list，作為下一次迭代過程的輸入。 Reduce任務(wù)把第一次迭代后 Map任務(wù)的輸出作為自己的輸入，經(jīng)過處理后，階段 2的 Reduce輸出為： AURL， ， BURL， CURL， DURL BURL， ， AURL， CURL CURL， ， DURL DURL， ， AURL， BURL 經(jīng)過本輪迭代，每個(gè)網(wǎng)頁都計(jì)算得到了新的 PageRank值。下次迭代階段 2的 Reduce輸出為： AURL， ， BURL， CURL， DURL BURL， ， AURL， CURL CURL， ， DURL DURL， ， AURL， BURL 2. 階段 2： PageRank分配（ Reduce階段） 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 PageRank算法在 MapReduce中的實(shí)現(xiàn) Mapper函數(shù)的偽碼： input PageN, RankN PageA,PageB,PageC ... // PageN外鏈指向 PageA,PageB,PageC ... begin Nn := the number of outlinks for PageN。 for each outlink PageK output PageK PageN, RankN/Nn output PageN PageA, PageB, PageC ... // 同時(shí)輸出鏈接關(guān)系，用于迭代 end /************************** Mapper輸出如下（已經(jīng)排序，所以 PageK的數(shù)據(jù)排在一起，最后一行則是鏈接關(guān)系對(duì)）： PageK PageN1, RankN1/Nn1 PageK PageN2, RankN2/Nn2 ... PageK PageAk, PageBk, PageCk Reducer函數(shù)的偽碼： input mapper39。s output begin RankK :=(1beta)/N。 //N為整個(gè)網(wǎng)絡(luò)的網(wǎng)頁總數(shù) for each inlink PageNi RankK += RankNi/Nni * beta //輸出 PageK及其新的 PageRank值用于下次迭代 output PageK, RankK PageAk, PageBk, PageCk... end 該階段 是一個(gè) 多次迭代過程，迭代多次后，當(dāng) PageRank值趨于穩(wěn)定 時(shí)，就得出了較為精確的PageRank值。 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 PageRank算法在 MapReduce中的實(shí)現(xiàn) ? 該階段的任務(wù)就是由一個(gè)非并行組件決定是否達(dá)到收斂，如果達(dá)到收斂，就寫出 PageRank生成的列表。否則，回退到 PageRank分配階段的輸出，作為新一輪迭代的輸入，開始新一輪 PageRank分配階段的迭代 ? 一般判斷是否收斂的條件是所有網(wǎng)頁的 PageRank值不再變化，或者運(yùn)行 30次以后我們就認(rèn)為已經(jīng)收斂了 3. 階段 3：收斂階段 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 ? PageRank算法在 Pregel和 MapReduce中實(shí)現(xiàn)方式的區(qū)別主要表現(xiàn)在以下幾個(gè)方面： ? （ 1） Pregel將 PageRank處理對(duì)象看成是連通圖，而 MapReduce則將其看成是鍵值對(duì) ? （ 2） Pregel將計(jì)算細(xì)化到頂點(diǎn)，同時(shí)在頂點(diǎn)內(nèi)控制循環(huán)迭代次數(shù)，而MapReduce則將計(jì)算批量化處理，按任務(wù)進(jìn)行循環(huán)迭代控制 ? （ 3）圖算法如果用 MapReduce實(shí)現(xiàn)，需要一系列的 MapReduce的調(diào)用。從一個(gè)階段到下一個(gè)階段，它需要傳遞整個(gè)圖的狀態(tài)，會(huì)產(chǎn)生大量不必要的序列化和反序列化開銷。而 Pregel使用超步簡(jiǎn)化了這個(gè)過程 PageRank算法在 Pregel和 MapReduce中實(shí)現(xiàn)的比較 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 本章小結(jié) ? 本章內(nèi)容介紹了圖計(jì)算框架 Pregel的相關(guān)知識(shí)。傳統(tǒng)的圖計(jì)算解決方案無法解決大型的圖計(jì)算問題，包括 Pregel在內(nèi)的各種圖計(jì)算框架脫穎而出。 ? Pregel并沒有采用遠(yuǎn)程數(shù)據(jù)讀取或者共享內(nèi)存的方式，而是采用了純消息傳遞模型，來實(shí)現(xiàn)不同頂點(diǎn)之間的信息交換。 Pregel的計(jì)算過程是由一系列被稱為“超步”的迭代組成的，每次迭代對(duì)應(yīng)了 BSP模型中的一個(gè)超步。 ? Pregel已經(jīng)預(yù)先定義好一個(gè)基類 —— Vertex類，編寫 Pregel程序時(shí)，需要繼承Vertex類，并且覆寫 Vertex類的虛函數(shù) Compute()。在 Pregel執(zhí)行計(jì)算過程時(shí)，在每個(gè)超步中都會(huì)并行調(diào)用每個(gè)頂點(diǎn)上定義的 Compute()函數(shù)。 ? Pregel是為執(zhí)行大規(guī)模圖計(jì)算而設(shè)計(jì)的，通常運(yùn)行在由多臺(tái)廉價(jià)服務(wù)器構(gòu)成的集群上。一個(gè)圖計(jì)算任務(wù)會(huì)被分解到多臺(tái)機(jī)器上同時(shí)執(zhí)行， Pregel采用檢查點(diǎn)機(jī)制來實(shí)現(xiàn)容錯(cuò)。 ? Pregel作為分布式圖計(jì)算的計(jì)算框架，主要用于圖遍歷、最短路徑、PageRank計(jì)算等等。 ? 本章最后通過對(duì) PageRank算法在 MapReduce和 Pregel上執(zhí)行方式的不同進(jìn)行比較，說明了 Pregel解決圖計(jì)算問題的優(yōu)勢(shì)。 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 主講教師和助教 主講教師：林子雨 單位：廈門大學(xué)計(jì)算機(jī)科學(xué)系數(shù)據(jù)庫實(shí)驗(yàn)室 2023級(jí)碩士研究生（導(dǎo)師：林子雨） Email: 助教：蔡珉星 歡迎訪問 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 —— 概念、存儲(chǔ)、處理、分析與應(yīng)用 》 教材官方網(wǎng)站： 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 Department of Computer Science, Xiamen University, June, 2023 《 大數(shù)據(jù)技術(shù)原理與應(yīng)用 》 廈門大學(xué)計(jì)算機(jī)科學(xué)系 林子雨 演講完畢，謝謝觀看！