I/O Efficient: Computing SCCs in Massive Graphs - todo314 @ ウィキ

I/O Efficient: Computing SCCs in Massive Graphs

• Zhiwei Zhang, Jeffrey Xu Yu, Lu Qin, Lijun Chang, Xuemin Lin
• In SIGMOD 2013

• 駒水（筑波大）さんの資料

概要

• SCCしたい
• グラフがメモリに乗らない

既存手法

EM-SCC

• Contraction-based
• グラフを適当に分割する
  • メモリ乗らないサイズのSCCは発見できない

DFS-SCC

• semi-external
• DFS木を2回
• 逆グラフ作って…ってやつ
  • よくやるSCCアルゴリズムだと思う多分

提案手法

• 木の構築は一度

2フェイズアプローチ

• BR木: 2種類のedge
  • tree-edge: 木を構成する
  • up-edge: 逆方向に向かう（サイクルを構成する）
• BR木内のサイクルをまとめて1ノードにする

BR木の構築

• 面白い操作をする
• 適当な全域木から始める
• pushdown(v,u)
  • remove(parent(u), v) then add(u,v)
• 張替えと削除
  • non-up-edgeを削除する
• merge
  • up-edgeの端点を結ぶパス上のノードを併合
• この操作をしまくって、SCCを出す

1フェイズアプローチ

• early acceptance: 早めに併合ｼﾏｰｽ
• early rejection: 早めに判定・出力ｼﾏｰｽ

実験

• 2フェイズはそんなに速くない
  • 既存手法の2倍くらい
  • I/O 効率は良くなった
• 1フェイズはかなり強い
• 10倍以上
• 色々変えても良いらしい

I/O-efficient algorithm SCC SIGMOD

2013-10-17 23:12:22 (Thu)