iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

Streaming Graph Partitioning for Large Distributed Graphs (KDD'12)

  • 問題
    • 複数台でグラフを分割して格納・処理
    • どのようにグラフを分割するか
    • 頂点集合を分ける,サイズは |V|/K の (1+ε) 倍まで OK
    • またがる辺の本数を最小化
    • ストリーミング;v が1つず渡されるので,その近傍の情報から答える
  • ヒューリスティクス
    • balanced: 現在最小のやつに
    • chunking: 端から順に
    • hashing: ランダム
    • deterministic greedy: 近傍に多いパーティションを選ぶ
    • randomized greedy: 近傍に多いパーティションを選びやすい
      • unweighted, linear, exponential
    • triangle:自分を足したら三角形が最も増えるパーティション
    • balance big:次数をしきい値により分ける,でかいやつは blanced
    • Buffering:C 個まで貯める
      • Prefer Big: でかいのを優先して balanced
      • Avoid big: ひくいのを優先
      • Greedy EvoCut:C 個を sparsest cut !!!