GraphX Advent Calendar - Day 12 - Pregel 概要
GraphX Advent Calendar 2014 - Adventar 12日目です。ページランクアルゴリズムに予想以上に苦戦しているので、できるところから見ていきます ^^; 今日は Pregel です。
Pregel とは
Pregel は Google が開発したグラフアルゴリズムを実装する ためのスケーラブルなプラットフォーム実装です。 Google のページランクアルゴリズムはこの Pregel というソフトウェアで稼働しているそうです。しかし、 Pregel のソースコード⾃自体は公開されておらず、論文が発表 されているのみです。GraphX は、この論文の内容を実装した関数を用意していて、利用可能な状態になっています。
GraphX で用意されている、ページランクアルゴリズムや、連結グラフ分類( Connected Components ) 等も Pregel が使われています。グラフ理論の各アルゴリズムは行列計算で実現するのですが、行列計算では並列分散環境でスケールすることはできません。この Pregel を使うことによって、グラフ処理を並列分散環境上で実装することが可能になり、大量のグラフデータについても扱うことができるようになります。実用的なグラフ処理は、全てこの Pregel を活用するといっても過言ではなく、GraphX を理解する上で、この Pregel API を理解することは最も重要なことになります。
Pregel API
Pregel API は、このようになっています。
Pregel( // 処理対象グラフデータ graph, // 最初のイテレーションで送信するメッセージ initialMsg : A, // 最大何回イテレーションするか maxIter : Int, // どちら方向にメッセージ送信するか activeDir:EdgeDirection ) ( // イテレーション毎に頂点で稼動させる処理(A:受信したメッセージ) vprog : (VertexId, VD, A) => VD, // イテレーション毎に辺上に何を流すか決定する処理 sendMsg : (EdgeTriplet[VD, ED]) => Iterator[(VertexId, A)], // 複数Edgeからメッセージを受信した時処理 mergeMsg: (A, A) => A // 処理結果として新しいGraphデータを返す ) : Graph[VD, ED]
これだけ見ても、何がなんだかわかりませんね。
Pregel 処理概要
Pregel ではどういう風に処理されるのか見てみましょう。
これは文章で説明しても分かりづらいので、スライドにまとめてみました。
次回予告
明日からは、この Pregel を利用した様々な処理を見ていきたいと思います。