El índice de un motor de búsqueda está lleno de páginas replicadas y copiadas, y deduplicarlas de forma ingenua implica comparar cada página con todas las demás: millones al cuadrado.
El trabajo de Broder de 1997 representaba una página como un conjunto de shingles y luego conservaba solo el puñado con el hash más pequeño bajo una permutación. Los conjuntos de dos páginas comparten un valor mínimo en proporción a su semejanza de Jaccard, de modo que un esbozo corto estima la similitud sin comparación por pares.
AltaVista usó el esbozo para agrupar las páginas casi duplicadas de la web y descartar las copias de los resultados. El método convirtió un problema de similitud intratable en una rápida tarea de hashing.
Los mismos hashes pequeños significan que las páginas se parecen
Unos pocos hashes mínimos estiman la similitud de Jaccard sin comparación elemento por elemento.
La firma es de tamaño fijo, por lo que el costo por página es mínimo y se almacena bien.
Es un estimador insesgado, correcto en promedio entre páginas.
El mismo esbozo permite la detección de casi duplicados y el agrupamiento a escala.
No compares dos conjuntos grandes elemento por elemento. Reduce cada uno a unos pocos hashes mínimos, de modo que la probabilidad de que coincidan sea igual a la superposición de los conjuntos, y el problema se vuelve diminuto.
MinHash se convirtió en una base de la detección de casi duplicados a gran escala, la similitud de conjuntos y la deduplicación en búsqueda, publicidad y aprendizaje automático, y más tarde en la familia de hashing sensible a la localidad construida sobre él.
CONSULTA LAS PRUEBAS
Las fuentes
- On the resemblance and containment of documents DEC Systems Research Center Technical Note 1997-015 · bitsavers.org
- MinHash Wikipedia · en.wikipedia.org