TEPPEI STUDIO

ENJOY RESTRICTION

GraphX Advent Calendar - Day 12 - Pregel 概要

f:id:teppei-studio:20100306105411j:plain

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 を利用した様々な処理を見ていきたいと思います。