MapReduce在搜索引擎中一些應用

IT技術武館 2014-07-17

展開全文

word-doc矩陣

在進行文件分類或文檔檢索的時候，我們通常需要建立一個word-doc矩陣，來記錄每個詞在每篇文檔中出現(xiàn)的次數(shù)。

class Mapper

method map(docid id,doc d)

foreach term in d

Emit(pair(term,id),1)

一種更高效的方法是在mapper側進行聚合。

class Mapper

method map(docid id,doc d)

H := new AssociativeArray

foreach term in d

H{term} := H{term}+1

foreach term in H

Emit(pair(term,id),H{term})

圖的寬度優(yōu)先遍歷

現(xiàn)代的爬蟲一般采用寬度優(yōu)先的規(guī)則來遍歷網(wǎng)絡。還有在Dijkstra算法中也是一種寬度優(yōu)先的規(guī)則--每發(fā)再一個新的最近點，就更新與之相鄰的節(jié)點的dist。我們可以用MapReduce迭代的方式來實現(xiàn)Dijkstra算法。每輪迭代運行一次Map-Reduce，最多迭代N次，N是圖中節(jié)點的個數(shù)。用鄰接鏈表來存儲圖。算法開始時，起始節(jié)點的dist賦0，其余的節(jié)點dist賦無窮大。先考慮簡單的情形--每條邊的權值都是1。

class Mapper

method map(nid n,node N)

d := N.distance

Emit(nid n,N) //pass along graph structure

foreach nodeid m in N.AdjacencyList

Emit(nid m,d+1) //Emit distances to reachable nodes

class Reducer

method reduce(nid m,[d1,d2,...])

minDist := infinite

M := NULL

foreach d in [d1,d2,...]

if IsNode(d)

M := d //recover graph structure

else if d<minDist //lookup for shortest distance

minDist := d

M.distance := minDist //update shortest distance

Emit(nid m,node M)

在迭代式的Map-Reduce程序設計中，需要有一個driver來控制迭代的進行，檢查終止條件是否滿足。在reducer中如果所有node的minDist都沒有更新，更迭代終止。

上面的代碼只算出了源節(jié)點到其他節(jié)點的最短路程，并沒有記錄下最短路徑，所以我們需要在更新minDist的同時記錄下它的上一個節(jié)點，mapper在輸出(nid,dist)時也應該輸出與dist對應的是哪個節(jié)點。

上面假設任意節(jié)點間的距離都是1，當是任意值r時，只需要在mapper中輸出(nid m,d+r)就可以了。

跟單進程的Dijkstra算法比起來，這種Map-Reduce版的算法顯然計算量大了許多，因為它每次迭代都要去檢查每一個節(jié)點的鄰居的dist是否需要更新；而單進程的Dijkstra算法通過維持一個優(yōu)先隊列，它每次迭代只需要檢查隊首元素的鄰居的dist是否需要更新。在Hadoop中，mapper和reducer通信方式非常受限，我們無法維持一個像優(yōu)先隊列這樣一種全局的數(shù)據(jù)結構。正因如此，Map-Reduce不適合于處理大規(guī)則，稠密圖。

Page Rank

在網(wǎng)頁排序算法中Page Rank可謂鼎鼎有名--雖然它只是Google對網(wǎng)頁進行排序的上千種因素中的一個。該算法認為一個網(wǎng)頁的重要度，由它鏈接到它的的網(wǎng)頁的重要度來決定。網(wǎng)頁重要度公式為：

|G|中整個網(wǎng)絡當中節(jié)點的總個數(shù)，α是隨機跳轉因子，L(n)是所有鉸接到網(wǎng)頁n的網(wǎng)頁的集合，C(m)是網(wǎng)頁m的出度。在網(wǎng)頁m上的一個沖浪者它以1/C(m)的概率進入網(wǎng)頁n。如何理解加式的第1項呢？一個沖浪者在瀏覽網(wǎng)頁時并不總是點擊超鏈接進行下去的，他也有可能在地址欄隨機地輸入了一個網(wǎng)址，一下子跳轉到了一個完全不相關的網(wǎng)頁。

Page Rank算法迭代地計算每個網(wǎng)頁的重要度，實際上就是一種寬度優(yōu)先遍歷的方法。一個網(wǎng)頁從它的所有incoming網(wǎng)頁中“收集”重要度，很自然地用reducer來完成。開始時給網(wǎng)絡圖上的每個節(jié)點賦一個服從[0,1]的均勻分布的隨機值作為其重要度。Map-Reduce不斷地迭代，直到每個網(wǎng)頁的重要度都不再變化為止。

下面的代碼簡化起見，沒有考慮公式中的第一項。

class Mapper

method map(nid n,node N)

p := N.PageRank/|N.AdjacencyList|

Emit(nid n,N) //pass along graph structure

foreach nodeid m in N.AdjacencyList

Emit(nid m,p)

class Reducer

method reduce(nid m,[p1,p2,...])

M := NULL

s := 0

foreach p in [p1,p2,...]