Massive Graph Triangulation

Massive Graph Triangulation

  • Xiaocheng Hu, Yufei Tao, Chin-Wan Chung
  • In SIGMOD 2013

塩川さん@NTT の発表資料より

目的

  • graph triangulation を高速に解く
    • 全てのtriangleを列挙

貢献

  1. 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: (発見した)△の数
  2. 既存手法EM-NIの再分析
  3. 既存手法RGPの再分析

提案手法:MGT

  1. oriented graph G* を生成
    • u→v: d(u)<d(v) or d(u)=d(v) and id(u)<id(v)
      • ようするに、次数に高い方に辺を張る
  2. G*上での△(u,v,w)
    • v→w: pivot edge
    • uからはv,wに張る
  3. Emem だけメモリに読み込む
    • O(|E|/M)回やる
  4. u の出辺を読み込みEmem中に含まれるノードからpivot edgeを求める
    • O(|E|/B)回読み込み
    • O(K/B)回書き出し

計算量分析

  • 完全グラフについて△はΩ(|V|^3)あるのでI/OはΩ(|E|^2/(MB))必要
    • だからMGTは最適
  • CPUも最悪時を見れば良い

実験

データセット

  • ランダムグラフ
  • recursive matrix graph
    • ??
  • small world グラフ
  • 実データも

実行時間

  • 最強
  • ロバスト

I/O-efficient algorithm SIGMOD triangle

2013-10-17 14:32:10 (Thu)

最終更新:2013年10月17日 14:32