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 !!!