SimHash

En informática , SimHash es una técnica para estimar rápidamente la similitud entre dos conjuntos de datos. El algoritmo es utilizado por el rastreador de Google para encontrar páginas casi idénticas. Fue creado por Moses Charikar . En 2021, Google anunció su intención de utilizar también el algoritmo en su sistema FLoC (Federated Learning of Cohorts) , de reciente creación. ^{[ 1 ]}

Una función hash asigna datos arbitrarios a salidas de tamaño fijo. Al aplicar la función hash a los mismos datos, se obtiene el mismo resultado cada vez; una salida hash diferente implica una entrada distinta. Esto, junto con su tamaño fijo, hace que las funciones hash sean útiles para comparar grandes conjuntos de datos. Sin embargo, pequeñas diferencias en los datos de entrada pueden generar hashes significativamente diferentes. La comparación de hashes es una señal binaria (diferente o no), en lugar de una medida de similitud continua .

En cambio, SimHash crea hashes que producen hashes similares para datos de entrada similares, medidos como la distancia de Hamming bit a bit entre valores. Esto significa que SimHash no solo indica si dos entradas son diferentes o no, sino también su grado de diferencia, a diferencia de otras funciones de hash.

La función opera dividiendo primero los datos de entrada en un conjunto de características . Cada característica del conjunto se somete a una función hash. El hash final se define restando, para cada bit dentro de los hashes de entrada, el número de hashes donde el bit no está activado (0) del número de hashes donde el bit está activado (1). Para los índices del hash donde la diferencia es positiva, el bit está activado. Para los índices con un mayor número de bits no activados, el bit en ese índice del hash final no está activado. ^{[ 2 ]}

En otras palabras, cada bit del SimHash de un dato se activa si, para cada hash del conjunto de características de ese dato, la suma de los bits en ese índice es mayor que la suma de la negación bit a bit de los bits en ese índice.

Como resultado, dos conjuntos de datos con conjuntos de características similares tendrán hashes que difieren menos que los datos donde los conjuntos de características divergen más. Además, "si la distancia de Hamming bit a bit de SimHash de dos frases es baja, entonces su coeficiente de Jaccard es alto". ^{[ 3 ]} Esto permite eficiencias que incluyen una clasificación más eficiente (al comparar los SimHashes de los objetos, en lugar del objeto completo) y un descubrimiento más rápido de objetos similares al ordenar una lista y comparar objetos adyacentes en lugar del cálculo O(n^2) de cada comparación en la lista. ^{[ 4 ]}

Google realizó una evaluación a gran escala en 2006 ^{[ 5 ]} para comparar el rendimiento de los algoritmos Minhash y Simhash ^{[ 6 ]} . En 2007, Google informó del uso de Simhash para la detección de duplicados en el rastreo web ^{[ 7 ]} y del uso de Minhash y LSH para la personalización de Google News ^{[ 8 ]} .

• MinHash
• tejas w
• Boceto de conteo-min
• Hashing sensible a la localidad

• Documento de Simhash Princeton
• Simhash explicó
• Comparación de MinHash vs. Simhash