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.
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.
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.
No obstante, los valores clave seguían siendo aproximadamente proporcionales al tamaño del fichero, lo que provocaba muchos falsos positivos.
Normalmente, las funciones hash se diseñan para minimizar las colisiones (cuando dos entradas diferentes tienen el mismo valor de clave).
Para estimar J(A,B) usando esta versión del esquema, sea y el número de funciones hash para las cuales hmin(A) = hmin(B), y usamos y/k como el estimado.
La diferencia entre este estimador y el estimador producido por múltiples funciones hash es que X siempre tiene exactamente k miembros, mientras que las múltiples funciones de hash pueden dar lugar a un menor número de elementos incluidos en la muestra debido a la posibilidad de que dos funciones hash diferentes pueden tener los mismos mínimos.
Sin embargo, cuando k es pequeño en relación con los tamaños de los conjuntos, esta diferencia es insignificante.
permutaciones distintas, se requerirían Ω(n log n) bits sólo para especificar una permutación verdaderamente aleatoria, un gran número impracticable, incluso para valores moderados de n. Debido a este hecho, por analogía con la teoría de hashing universal, ha habido un trabajo significativo en la búsqueda de una familia de permutaciones que es "independiente relativo al mínimo, lo que significa que para cualquier subconjunto del dominio, cualquier elemento es igualmente probable que sea el mínimo.
Para que dos les sean similares según la métrica, deben contener un gran número de piezas comunes.
[10] Una evaluación a gran escala fue realizada por Google en 2006[11] para comparar el rendimiento de Minhash y Simhash[12] algorithms.