MapReduceってこういうことか

こんにちは。PigeonRank 作成作業員です (ウソ)。

Googleでは、並列計算の枠組みMapReduceを使って、ページのインデックスを作ったり、ページランクを計算している。

ページのインデックスを作るというのは、
・Webページ群の各ページにある単語 (実際はNgram) の並びを抜き出して、
・単語から、その単語をもつページ群を割り出す (これを保持する)
ということ。

また、ページランクを計算する時には逆リンクを求める必要がある。あるページからリンクがはってあるページ群の逆で、あるページへのリンクをもつページの集合。これはWeb全体を見なければ分らない。これを被参照ページごとに行うのではなく、まとめて行う。
・Webページ群の各ページにあるリンク先を抜き出して、
・リンク先ページから、そのページへのリンクをもつページを全て抜きだす。

これらの共通点は、行列の計算をそれぞれの軸で行っているということ。すなわち、
インデックス： ページ軸 → 単語ベクトル、単語軸 → ページベクトル
逆リンク： リンクページ軸 → 被リンクページベクトル、被リンクページ → リンクページベクトル
[補足] 実際はベクトルではなくハッシュ表なのだが、ここではベクトルで説明する。

この最初のステップをMapで、次のステップをReduceで並列計算する。その間にMapの計算結果 (ベクトルのベクトル = 行列) をスライスしてReduce用の計算機に分配するShuffleのフェーズが入る。

図解にするとこんな感じ。

アニメーションをつけたPowerPointプレゼンテーションを置きました。



次に、インデックス抽出の事例をここにあてはめてみる。

ここでは単純化のため、形態素解析で分割された文字列を単語として扱うが、Googleでは任意の文字列で検索できるのでNgramを用いていると考えられる。もちろん英単語をカタカナで検索できたりするということは単語がわかっているということなので、形態素解析も併用していると考えられる。また「バイオリン」でも「ヴァイオリン」でも検索できるので表記違いもあわせてインデックス化しているかもしれない (検索時に展開する方法もあるのでGoogleが実際にどちらを採用しているかは分らない)。

1) Map: Webページ群をプロセッサの数に応じて割り当てる。WebページURLとそのコンテンツ (テキスト) を入力として、単語の並びを抽出する。ここでは存在することを●で示しているが、個数を記録しておけば、その単語を多く含むページを優先させる処理が可能になる。

2) Shuffle: Mapの結果をベクトルの要素ごとに決めたプロセッサに分配する。ここではベクトルと書いたが、ある単語を処理するプロセッサが特定できれば良いので、実際はハッシュを用いている。

3) Reduce: 各単語ごとの処理を行う。ここではその単語を含むページ (URL) のリストを作成する。Mapの段階で単語の個数を記録していた場合は、URLと単語個数の対のリストを返す。あわせてURLの個数を計算することで、その単語がどれだけ多くの文書で使われる一般性の高い用語なのかの尺度DF (Document Frequency) を得ることができる。

アルゴリズムによってはMapとReduceの組み合わせではなく、Mapの結果は既に入力として持っていてReduce処理だけ必要というものもでてくるだろう。またアルゴリズムによっては1段のMapReuceでは足りず、複数回適用する必要があるものも出ると思われる。

以上、誤解等ご指摘いただければ幸いです。

参考文献
Radium Software Development: MapReduce
  -- 「フィルター」と「アグリゲーター」の2段階から構成されると考える
原論文 (すみません読んでません) MapReduce: Simplified Data Processing on Large Clusters