非基本 MapReduce 模式

迭代消息傳遞 （圖處理）

問題陳述：

假設一個實體網絡，實體之間存在著關系。 需要按照與它比鄰的其他實體的屬性計算出一個狀態。這個狀態可以表現為它和其它節點之間的距離， 存在特定屬性的鄰接點的跡象， 鄰域密度特征等等。

解決方案：

網絡存儲為系列節點的結合，每個節點包含有其所有鄰接點ID的列表。按照這個概念，MapReduce 迭代進行，每次迭代中每個節點都發消息給它的鄰接點。鄰接點根據接收到的信息更新自己的狀態。當滿足了某些條件的時候迭代停止，如達到了最大迭代次數（網絡半徑）或兩次連續的迭代幾乎沒有狀態改變。從技術上來看，Mapper 以每個鄰接點的ID為鍵發出信息，所有的信息都會按照接受節點分組，reducer 就能夠重算各節點的狀態然后更新那些狀態改變了的節點。下面展示了這個算法：

class Mapper

method Map（id n， object N）

Emit（id n， object N）

for all id m in N.OutgoingRelations do

Emit（id m， message getMessage（N））

class Reducer

method Reduce（id m， ［s1， s2，。..］）

M = null

messages = ［］

for all s in ［s1， s2，。..］ do

if IsObject（s） then

M = s

else // s is a message

messages.add（s）

M.State = calculateState（messages）

Emit（id m， item M）

一個節點的狀態可以迅速的沿著網絡傳全網，那些被感染了的節點又去感染它們的鄰居，整個過程就像下面的圖示一樣：

?

案例研究： 沿分類樹的有效性傳遞

問題陳述：

這個問題來自于真實的電子商務應用。將各種貨物分類，這些類別可以組成一個樹形結構，比較大的分類（像男人、女人、兒童）可以再分出小分類（像男褲或女裝），直到不能再分為止（像男式藍色牛仔褲）。這些不能再分的基層類別可以是有效（這個類別包含有貨品）或者已無效的（沒有屬于這個分類的貨品）。如果一個分類至少含有一個有效的子分類那么認為這個分類也是有效的。我們需要在已知一些基層分類有效的情況下找出分類樹上所有有效的分類。

解決方案：

這個問題可以用上一節提到的框架來解決。我們咋下面定義了名為 getMessage和 calculateState 的方法：

class N

State in {True = 2， False = 1， null = 0}，

initialized 1 or 2 for end-of-line categories， 0 otherwise

method getMessage（object N）

return N.State

method calculateState（state s， data ［d1， d2，。..］）

return max（ ［d1， d2，。..］ ）

案例研究：廣度優先搜索

問題陳述：需要計算出一個圖結構中某一個節點到其它所有節點的距離。

解決方案： Source源節點給所有鄰接點發出值為0的信號，鄰接點把收到的信號再轉發給自己的鄰接點，每轉發一次就對信號值加1：

class N

State is distance，

initialized 0 for source node， INFINITY for all other nodes

method getMessage（N）

return N.State + 1

method calculateState（state s， data ［d1， d2，。..］）

min（ ［d1， d2，。..］ ）

案例研究：網頁排名和 Mapper 端數據聚合

這個算法由Google提出，使用權威的PageRank算法，通過連接到一個網頁的其他網頁來計算網頁的相關性。真實算法是相當復雜的，但是核心思想是權重可以傳播，也即通過一個節點的各聯接節點的權重的均值來計算節點自身的權重。

class N

State is PageRank

method getMessage（object N）

return N.State / N.OutgoingRelations.size（）

method calculateState（state s， data ［d1， d2，。..］）

return （ sum（［d1， d2，。..］） ）

要指出的是上面用一個數值來作為評分實際上是一種簡化，在實際情況下，我們需要在Mapper端來進行聚合計算得出這個值。下面的代碼片段展示了這個改變后的邏輯 （針對于 PageRank 算法）：

class Mapper

method Initialize

H = new AssociativeArray

method Map（id n， object N）

p = N.PageRank / N.OutgoingRelations.size（）

Emit（id n， object N）

for all id m in N.OutgoingRelations do

H{m} = H{m} + p

method Close

for all id n in H do

Emit（id n， value H{n}）

class Reducer

method Reduce（id m， ［s1， s2，。..］）

M = null

p = 0

for all s in ［s1， s2，。..］ do

if IsObject（s） then

M = s

else

p = p + s

M.PageRank = p

Emit（id m， item M）

應用：

圖分析，網頁索引