Hadoop で行列ベクトル積

PageRankは本質的に疎行列ベクトル積になる。Jimmy Lin のData-Intensive Text Processingに乗っているアルゴリズムは、Mapの入力として、Nodeを用いている。Nodeは他のノードへのリンクを保持している。 行列的に捉えれば、行列のカラムに相当する。つまり、このアルゴリズムは、カラムの非ゼロ要素数が十分小さく、メモリに乗るという前提で考えられている。Page Rankというアプリケーションの特性を考えれば妥当である。

class Mapper
   method Map(nid n, node N)
       p ← N.PageRank/|N.AdjacencyList|
       Emit(nid n, N ) 
       for all nodeid m ∈ N.AdjacencyList do
         Emit(nid m, p)

class Reducer
   method Reduce(nid m, [p1, p2, . . .])
   M←∅
   for all p ∈ counts [p1,p2,...] do
       if IsNode(p) then 
          M ← p
       else
          s ← s + p 
   M.PageRank ← s
   Emit(nid m, node M )

node のなかに AdjacencyList が含まれているが、これが疎行列のコラム方向の情報に相当する。

CPSYで提案したReduceのみでMatMulを行うアルゴリズムは、ベクトルがメモリに乗ることを前提としている。 ベクトルとカラムは同じ長さだが、ベクトルは密なのでこちらのほうが強い制約となる。

PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations で示されている、naiveな方法では行列ベクトル積はMR2回が必要となるが、サイズの制約はない。かと思ったけど、やっぱり1段めのMRのReduceのところで、一度コラム方向を全部オンメモリに持っているから条件は変わらない。データの持ち方の違いだけか？

map-reduce-mergeのmergeがあれば、merge + reduce で非常に素直に書けそう。