"頂点のように考える"から"グラフのように考える"へ

現代のアプリケーションによって生成される急速に成長するグラフおよびネットワークデータを処理する課題に対処するため、PregelやGraphLabなどの分散グラフ処理システムがいくつか登場しました。これらのシステムはすべて、入力グラフをパーティションに分割し、反復的なグラフ計算をサポートするために「頂点のように考える」プログラミングモデルを採用しています。この頂点中心のモデルはプログラミングが容易で、多くのグラフアルゴリズムにとって有用であることが証明されています。しかし、このモデルはパーティション情報をユーザーから隠すため、多くのアルゴリズム特有の最適化を妨げます。この結果、過剰なネットワークメッセージ（例：Pregel）やデータの整合性を確保するための重いスケジューリングのオーバーヘッド（例：GraphLab）による長い実行時間を引き起こすことがよくあります。この制限に対処するために、新しい「グラフのように考える」プログラミングパラダイムを提案します。このグラフ中心のモデルでは、パーティション構造がユーザーに開放され、パーティション内での通信が重いメッセージパッシングやスケジューリング機構をバイパスできるように利用できます。このモデルはApache Giraphに基づく新しいシステム、Giraph++に実装しました。グラフ中心のモデルの三つのカテゴリのグラフアルゴリズムへの適用可能性を探求し、その柔軟性と優れたパフォーマンス、特によくパーティションされたデータにおいての優位性を示します。たとえば、1億1800万の頂点と8億5500万のエッジを持つウェブグラフでは、グラフ中心の連結成分検出アルゴリズムが頂点中心のバージョンよりも63倍速く、ネットワークメッセージを204倍少なく使用します。