AltaVista 透過描繪 Jaccard 相似度草圖來找出近乎重複的頁面

搜尋引擎的索引中充滿了鏡像與複製的頁面，而天真地進行去重意味著要將每個頁面與其他所有頁面兩兩比較——數百萬的平方。

Broder 於 1997 年的研究將頁面表示為一組 shingle，然後只保留在某個排列下雜湊值最小的少數幾個。兩個頁面的集合共享最小值的比例，正比於它們的 Jaccard 相似度，因此一段簡短的草圖就能估計相似度，無需進行兩兩比較。

AltaVista 利用該草圖將網路上近乎重複的頁面分群，並從結果中剔除副本。該方法將一個棘手的相似度問題轉變為快速的雜湊工作。

相同的小雜湊值意味著頁面彼此相似

少數最小雜湊值即可估計 Jaccard 相似度，無需逐元素比較。

簽名為固定大小，因此每頁的成本極低且易於儲存。

它是一個不偏估計量，在頁面之間平均而言是正確的。

同一份草圖可支援大規模的近乎重複偵測與分群。

不要逐元素比較兩個大型集合。將每個集合縮減為少數最小雜湊值，使它們一致的概率等於集合的重疊程度，問題便會變得極小。

MinHash 成為大規模近乎重複偵測、集合相似度以及搜尋、廣告與機器學習中去重的基礎，後來建立在它之上的局部敏感雜湊（locality-sensitive hashing）家族亦然。