Correlation Clustering in MapReduce - todo314 @ ウィキ

Correlation Clustering in MapReduce

• Flavio Chierichetti, Nilesh Dalvi, Ravi Kumar
• KDD 2014

概要

• AIlon et al.の手法の効率化
• pivotを並列に選択

[Ailon, Charikar, Newman]のPivotアルゴリズム

1. v ← Vから一様無作為選択
2. C_i ← v∪Γ+(v)
3. V ← V-C_i
4. E+ ← E+∩(V×V)

• ↑の問題点
  • ストリーム設定だと，走査数が多い，|V|パスもあり得る

提案手法

• 完全グラフ: 3近似に近い
• 一般のグラフ: 次数制限あっても近似難しい
• 最大正次数のpolylogラウンド

まとめ

• グラフ小さくね？

KDD クラスタリング 相関クラスタリング

2015/05/18 15:30