乱択データ構造の最新事情 −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.