「I/O Efficient: Computing SCCs in Massive Graphs」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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倍以上
- 色々変えても良いらしい
&tags()
&update()