AltaVistaはJaccard類似度をスケッチすることで近似重複ページを発見した

検索エンジンのインデックスはミラーやコピーのページで溢れており、それらを素朴に重複排除しようとすれば、すべてのページを他のすべてのページと比較することになる——数百万の二乗である。

Broderの1997年の研究は、ページをシングルの集合として表現し、その後、ある順列の下で最小のハッシュ値を持つごく少数だけを保持した。二つのページの集合が最小値を共有する割合は、それらのJaccard類似度に比例するため、短いスケッチでペアごとの比較なしに類似度を推定できる。

AltaVistaはこのスケッチを用いてウェブ上の近似重複ページをクラスタリングし、結果からコピーを除外した。この手法は、扱いにくい類似度問題を迅速なハッシュ処理へと変えた。

同じ小さなハッシュが一致すれば、ページは似ている

少数の最小ハッシュが、要素ごとの比較なしにJaccard類似度を推定する。

シグネチャは固定サイズであるため、ページあたりのコストはごく小さく、保存にも適している。

これは不偏推定量であり、ページ全体で平均すれば正しい。

同じスケッチが、大規模な近似重複検出とクラスタリングを支える。

二つの大きな集合を要素ごとに比較してはならない。それぞれを少数の最小ハッシュに縮約すれば、それらが一致する確率は集合の重なりに等しくなり、問題はごく小さくなる。

MinHashは、検索、広告、機械学習における大規模な近似重複検出、集合類似度、重複排除の基盤となり、後にその上に構築された局所性鋭敏ハッシュの一族の基礎となった。