乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−
本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります．
Ustream の録画もあります．
内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました．
- 集合の類似度の推定 (Jaccard 係数)
- 集合異なり数の推定 (distinct counting)
どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続けに発表されました．
今日の発表ではこれを踏まえ，まず MinHash の基礎を復習し，次に今まで最も有力な手法であった b-bit MinHash，HyperLogLog の説明をし，最後にこれらの新しい手法を紹介しました．新しい手法は両方とも，新しいアイディアに基づく本質的な改善ながら，手法自体はかなりシンプルなので，実装も困難ではないと思います．是非使ってみて下さい．
今日の発表は主に以下の 2 つの論文に基づいています．より詳しい情報は論文をご参照下さい．
- Michael Mitzenmacher, Rasmus Pagh, and Ninh Pham. Efficient estimation for high similarities using odd sketches. In WWW 2014.
- Edith Cohen. All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis. In PODS 2014.
