MinHash

En ciencia de la computacion, MinHash (o el esquema sensible a localidad que trata permutaciones independientes relativos al mínimo) es una técnica para estimar rápidamente cuan similares son dos conjuntos. El esquema fue inventado por Andrei Broder en 1997​ e inicialmente usado en el motor de búsqueda AltaVista para detectar páginas web duplicadas y eliminarlas de los resultados de búsqueda.​ También ha sido aplicado en problemas de clustering, tales como agrupación de documentos por la similitud de las palabras que contienen.​ En la mayoría de los casos, se utilizan funciones hash para separar y ocultar los datos, de modo que datos similares tengan claves diferentes. Sin embargo, se propone utilizar funciones hash para el propósito opuesto: detectar similitudes entre datos. La detección de similitudes y la clasificación es un problema bien estudiado, pero normalmente se involucran n² comparaciones por pares. Al utilizar una función hash que convierte datos similares en valores similares, la similitud se puede detectar simplemente comparando valores de clave hash preclasificados. El reto es encontrar una función hash de similitud que minimice los falsos positivos. SimHash produce claves hash con valores enteros, se recurrió a datos auxiliares para mejorar las pruebas de similitud. Los valores clave se basaron en contar las ocurrencias de ciertas cadenas binarias dentro de un fichero y combinando estas sumas. No obstante, los valores clave seguían siendo aproximadamente proporcionales al tamaño del fichero, lo que provocaba muchos falsos positivos. Se estableció como objetivo la creación de una "función hash de similitud". Normalmente, las funciones hash se diseñan para minimizar las colisiones (cuando dos entradas diferentes tienen el mismo valor de clave). Con las funciones hash criptográficas, se espera que las colisiones sean casi imposibles, y que los datos casi idénticos correspondan a claves muy distintas. Sin embargo, la función hash de similitud tenía...