読者です 読者をやめる 読者になる 読者になる

Massive Graph Triangulation (SIGMOD'13)

  • 問題:三角形を全列挙
  • M: size of memory, B: size of disk block, K: #triangles
  • 既存手法
    • em-cf, em-ni, graph partition [james cheng]
  • 提案手法:MGT
    1. 次数が小さいグラフに変換
      • 次数が cM/2 より大きい頂点を発見
    2. 次数の大きさで順番づけ,DAG になる
      • cM 本ぐらいメモリに一気に読み込む