「Correlation Clustering in MapReduce」の編集履歴（バックアップ）一覧はこちら

「Correlation Clustering in MapReduce」(2015/05/18 (月) 15:32:23) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* Correlation Clustering in MapReduce
- Flavio Chierichetti, Nilesh Dalvi, Ravi Kumar
- KDD 2014

* Correlation Clustering in MapReduce
- Flavio Chierichetti, Nilesh Dalvi, Ravi Kumar
- KDD 2014

* 概要
- AIlon et al.の手法の効率化
- pivotを並列に選択


* [Ailon, Charikar, Newman]のPivotアルゴリズム
+ v ← Vから一様無作為選択
+ C_i ← v∪Γ+(v)
+ V ← V-C_i
+ E+ ← E+∩(V×V)
- ↑の問題点
-- ストリーム設定だと，走査数が多い，|V|パスもあり得る

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

* まとめ
- グラフ小さくね？

&tags()

2015/05/18 15:30