「I/O Efficient: Computing SCCs in Massive Graphs」の編集履歴（バックアップ）一覧はこちら

「I/O Efficient: Computing SCCs in Massive Graphs」(2013/10/17 (木) 23:12:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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()