AltaVista通过草图估算Jaccard相似度来发现近重复页面

搜索引擎的索引中充满了镜像和复制页面，而先删除重复的朴素方法是把每个页面与其他所有页面进行比较——即数百万的平方。

Broder在1997年的工作将页面表示为一系列shingle，然后只保留在排列下具有最小哈希值的少数几个。两个页面的集合共享一个最小值，其比例与它们的Jaccard相似度成正比，因此一个简短的草图就能估计相似度，无需成对比较。

AltaVista使用该草图对网络上的近重复页面进行聚类，并从结果中删除副本。这种方法将棘手的相似性问题转化为快速的哈希处理。

相同的小哈希值意味着页面相似

几个最小哈希值就能估算Jaccard相似度，无需逐元素比较。

签名大小固定，因此每页的成本极小，且存储方便。

这是一个无偏估计器，在页面间平均而言是正确的。

同样的草图支持大规模近重复检测和聚类。

不要逐元素地比较两个大的集合。将每个集合减少为几个最小哈希，使得它们一致的概率等于集合的重叠程度，这样问题就变得微不足道。

MinHash成为大规模近重复检测、集合相似度和去重的基础，在搜索、广告和机器学习中广泛应用，后来基于它的局部敏感哈希家族也建立在它之上。