Massive Graph Triangulation
-
Xiaocheng Hu, Yufei Tao, Chin-Wan Chung
-
In SIGMOD 2013
塩川さん@NTT の発表資料より
目的
-
graph triangulation を高速に解く
貢献
-
CPU & I/O efficient
-
CPU: $$ O(|E|\log |E| \frac{|E|^2}{M} + \alpha |E|) $$
-
I/O: $$ O(\frac{|E|^2}{MB} + \frac{K}{B}) $$
-
worstではoptimal
-
M: メモリサイズ
-
B: ブロックサイズ
-
K: (発見した)△の数
-
既存手法EM-NIの再分析
-
既存手法RGPの再分析
提案手法:MGT
-
oriented graph G* を生成
-
u→v: d(u)<d(v) or d(u)=d(v) and id(u)<id(v)
-
G*上での△(u,v,w)
-
v→w: pivot edge
-
uからはv,wに張る
-
Emem だけメモリに読み込む
-
u の出辺を読み込みEmem中に含まれるノードからpivot edgeを求める
-
O(|E|/B)回読み込み
-
O(K/B)回書き出し
計算量分析
-
完全グラフについて△はΩ(|V|^3)あるのでI/OはΩ(|E|^2/(MB))必要
-
CPUも最悪時を見れば良い
実験
データセット
-
ランダムグラフ
-
recursive matrix graph
-
small world グラフ
-
実データも
実行時間
I/O-efficient algorithm SIGMOD triangle
2013-10-17 14:32:10 (Thu)
最終更新:2013年10月17日 14:32