案例库 · 软件与 IT · 技术决策 · 1997
AltaVista通过草图估算Jaccard相似度来发现近重复页面
Broder在1997年提出的MinHash草图通过几个最小哈希值估算大规模页面的Jaccard相似度，使AltaVista能够廉价地聚类近重复页面。
AltaVista · Digital Equipment Corporation
那一手
搜索引擎的索引中充满了镜像和复制页面，而先删除重复的朴素方法是把每个页面与其他所有页面进行比较——即数百万的平方。
Broder在1997年的工作将页面表示为一系列shingle，然后只保留在排列下具有最小哈希值的少数几个。两个页面的集合共享一个最小值，其比例与它们的Jaccard相似度成正比，因此一个简短的草图就能估计相似度，无需成对比较。
AltaVista使用该草图对网络上的近重复页面进行聚类，并从结果中删除副本。这种方法将棘手的相似性问题转化为快速的哈希处理。
为什么管用
- 几个最小哈希值就能估算Jaccard相似度，无需逐元素比较。
- 签名大小固定，因此每页的成本极小，且存储方便。
- 这是一个无偏估计器，在页面间平均而言是正确的。
- 同样的草图支持大规模近重复检测和聚类。
值了多少相同的小哈希值意味着页面相似聪明
可以搬走什么
不要逐元素地比较两个大的集合。将每个集合减少为几个最小哈希，使得它们一致的概率等于集合的重叠程度，这样问题就变得微不足道。
后来呢
MinHash成为大规模近重复检测、集合相似度和去重的基础，在搜索、广告和机器学习中广泛应用，后来基于它的局部敏感哈希家族也建立在它之上。
资料来源
发现哪里写错了？告诉我们。