読者です 読者をやめる 読者になる 読者になる

乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−

本日,PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました.スライドは以下になります.

Ustream の録画もあります.

内容としては,以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました.

  • 集合の類似度の推定 (Jaccard 係数)
  • 集合異なり数の推定 (distinct counting)

どちらも重要かつ基礎的な操作で,b-bit MinHashHyperLogLog など,既に実用的な手法が提案されており,実際にも使われています.しかし,2014 年になって,Odd SketchHIP 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.