抄訳 GraphChi: Large-Scale Graph Computation on Just a PC(2012)

November 12, 2022

商業規模の有向グラフを一般PCで計算できるデータ構造とプログラミングモデルであり、任意のひとつのノードとそのノードに接続する全てのエッジを読み込めるメモリがあればよい。 順序つきのノードを互いに素なP個の集合に分け、それぞれをintervalをよぶ。 interval内のノードに向うエッジを根のノード順にソートし、エッジをP個のshardに分けて保存する。 1つのshardをディスクの連続領域に保存することで、あるノードとノードに接続するエッジを、高々P回のディスクへのアクセスでメモリに読み込める。

エッジの追加や削除もできる。 メモリ上のバッファに追加されたエッジを追加し、バッファが満杯になるときにディスクに書き込む。 1つのshardごとにP個のバッファをもち、追加したエッジの根があるintervalで保存先のバッファを変える。 エッジを削除するときは、エッジに削除されたフラグを与え、shardをディスクに書き戻すときにそのエッジを無視する。

計算のモデルは、各ノードとそのエッジの現在の値から次の状態を計算するものであり、開発者は以下のf, gを実装する。 ガウス=ザイデル法を応用し、非同期に各ノードをUpdate(vertex)によってグラフの状態が収束するまで非同期に更新する。

Update(vertex) begin
  x[] ← read values of in- and out-edges of vertex ;
  vertex.value ← f(x[]) ;
    foreach edge of vertex do
  edge.value ← g(vertex.value, edge.value);
end

論文のリンク

雑記

単一のPCで動かすので、ネットワーク上の通信の失敗を考えなくてよいため、論文中で比較されたBulk-Synchromous Parall(BSP model) にある同期やフォールトトレランスの仕組みが省かれているようにみえる。 実験の比較対象がクラスタを使った場合なので、単一のPCで動かす同様の目的の手法と比べたときの評価がわからない。