AltaVista encontrava páginas quase duplicadas esboçando sua semelhança de Jaccard

O índice de um mecanismo de busca está repleto de páginas espelhadas e copiadas, e desduplicá-las de forma ingênua significa comparar cada página com todas as outras — milhões ao quadrado.

O trabalho de Broder, de 1997, representava uma página como um conjunto de shingles e então mantinha apenas o punhado com o menor hash sob uma permutação. Os conjuntos de duas páginas compartilham um valor mínimo em proporção à sua semelhança de Jaccard, de modo que um esboço curto estima a similaridade sem nenhuma comparação aos pares.

O AltaVista usou o esboço para agrupar as páginas quase duplicadas da web e remover as cópias dos resultados. O método transformou um problema de similaridade intratável em uma rápida tarefa de hashing.

Hashes mínimos iguais significam que as páginas são parecidas

Alguns hashes mínimos estimam a similaridade de Jaccard sem comparação elemento por elemento.

A assinatura tem tamanho fixo, então o custo por página é ínfimo e ela se armazena bem.

É um estimador não enviesado, correto em média entre as páginas.

O mesmo esboço sustenta a detecção de quase duplicatas e o agrupamento em escala.

Não compare dois grandes conjuntos elemento por elemento. Reduza cada um a alguns hashes mínimos, de modo que a probabilidade de coincidirem seja igual à sobreposição dos conjuntos, e o problema se torna minúsculo.

O MinHash tornou-se um fundamento da detecção de quase duplicatas em larga escala, da similaridade entre conjuntos e da desduplicação em busca, publicidade e aprendizado de máquina, e mais tarde da família de hashing sensível à localidade construída sobre ele.