Hashing sensible a la localidad

En informática , el hash sensible a la localidad ( LSH ) es una técnica de hash difuso que divide elementos de entrada similares en los mismos "cubos" con alta probabilidad. ^[1] (La cantidad de cubos es mucho menor que el universo de posibles elementos de entrada). ^[1] Dado que los elementos similares terminan en los mismos cubos, esta técnica se puede utilizar para la agrupación de datos y la búsqueda del vecino más cercano . Se diferencia de las técnicas de hash convencionales en que las colisiones de hash se maximizan, no se minimizan. Alternativamente, la técnica puede verse como una forma de reducir la dimensionalidad de los datos de alta dimensión; los elementos de entrada de alta dimensión se pueden reducir a versiones de baja dimensión mientras se preservan las distancias relativas entre los elementos.

Los algoritmos de búsqueda de vecino más cercano aproximado basados ​​en hash generalmente utilizan una de dos categorías principales de métodos de hash: métodos independientes de los datos, como el hash sensible a la localidad (LSH); o métodos dependientes de los datos, como el hash que preserva la localidad (LPH). ^{[2] [3]}

El hash con preservación de localidad fue inicialmente concebido como una forma de facilitar la canalización de datos en implementaciones de algoritmos masivamente paralelos que utilizan enrutamiento aleatorio y hash universal para reducir la contención de memoria y la congestión de la red . ^{[4] [5]}

Una familia finita de funciones se define como una familia LSH ^{[1] [6] [7]} para ${\displaystyle {\mathcal {F}}}$${\displaystyle h\colon M\to S}$

• un espacio métrico ,${\displaystyle {\mathcal {M}}=(M,d)}$
• un umbral ,${\displaystyle r>0}$
• un factor de aproximación ,${\displaystyle c>1}$
• y probabilidades$estilo de visualización p_{1}>p_{2}}$

Si se cumple la siguiente condición: Para dos puntos cualesquiera y una función hash elegida de manera uniforme al azar entre :${\displaystyle a,b\en M}$${\estilo de visualización h}$${\displaystyle {\mathcal {F}}}$

• Si , entonces (es decir, a y b chocan) con una probabilidad de al menos ,${\displaystyle d(a,b)\leq r}$${\displaystyle h(a)=h(b)}$$estilo de visualización p_{1}}$
• Si , entonces con probabilidad como máximo .${\displaystyle d(a,b)\geq cr}$${\displaystyle h(a)=h(b)}$$estilo de visualización p_{2}$

A una familia así se le llama -sensible.${\displaystyle {\mathcal {F}}}$${\displaystyle (r,cr,p_{1},p_{2})}$

Alternativamente ^[8] es posible definir una familia LSH en un universo de elementos U dotados de una función de similitud . En este contexto, un esquema LSH es una familia de funciones hash H acopladas a una distribución de probabilidad D sobre H tal que una función elegida según D satisface para cada .${\displaystyle \phi \colon U\times U\to [0,1]}$ ${\displaystyle h\en H}$${\displaystyle Pr[h(a)=h(b)]=\phi (a,b)}$${\displaystyle a,b\en U}$

Dada una familia sensible , podemos construir nuevas familias mediante la construcción AND o la construcción OR de . ^[1]${\displaystyle (d_{1},d_{2},p_{1},p_{2})}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle {\mathcal {F}}}$

Para crear una construcción AND, definimos una nueva familia de funciones hash g , donde cada función g se construye a partir de k funciones aleatorias de . Entonces decimos que para una función hash , si y solo si todas para . Dado que los miembros de se eligen independientemente para cualquier , es una familia sensible a .${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle g(x)=g(y)}$${\displaystyle h_{i}(x)=h_{i}(y)}$${\displaystyle i=1,2,\lpuntos ,k}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}$

Para crear una construcción OR, definimos una nueva familia de funciones hash g , donde cada función g se construye a partir de k funciones aleatorias de . Entonces decimos que para una función hash , si y solo si para uno o más valores de i . Dado que los miembros de se eligen independientemente para cualquier , es una familia sensible a .${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle g(x)=g(y)}$${\displaystyle h_{i}(x)=h_{i}(y)}$${\displaystyle {\mathcal {F}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}$

LSH se ha aplicado a varios dominios problemáticos, entre ellos:

• Detección de duplicados cercanos ^[9]
• Agrupamiento jerárquico ^{[10] [11]}
• Estudio de asociación de todo el genoma ^[12]
• Identificación de similitud de imágenes
  • VisualRank
• Identificación de similitud de expresión genética ^{[ cita requerida ]}
• Identificación de similitud de audio
• Búsqueda de vecino más cercano
• Huella de audio ^[13]
• Huella digital de vídeo
• Organización de la memoria compartida en computación paralela ^{[4] [5]}
• Organización física de datos en sistemas de gestión de bases de datos ^[14]
• Entrenamiento de redes neuronales completamente conectadas ^{[15] [16]}
• Seguridad informática ^[17]
• Aprendizaje automático ^[18]

Una de las formas más sencillas de construir una familia LSH es mediante muestreo de bits. ^[7] Este enfoque funciona para la distancia de Hamming sobre vectores d -dimensionales . Aquí, la familia de funciones hash es simplemente la familia de todas las proyecciones de puntos en una de las coordenadas, es decir, , donde es la coordenada ésima de . Una función aleatoria de simplemente selecciona un bit aleatorio del punto de entrada. Esta familia tiene los siguientes parámetros: , . Es decir, dos vectores cualesquiera con distancia de Hamming como máximo colisionan bajo un aleatorio con probabilidad de al menos . Cualquiera con distancia de Hamming como mínimo colisiona con probabilidad de como máximo .${\displaystyle \{0,1\}^{d}}$${\displaystyle {\mathcal {F}}}$${\estilo de visualización d}$${\displaystyle {\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ para algún }}i\in \{1,\ldots ,d\}\}}$$Estilo de visualización x_{i}}$${\estilo de visualización i}$${\estilo de visualización x}$${\estilo de visualización h}$${\displaystyle {\mathcal {F}}}$$Estilo de visualización P_{1}=1-R/d$${\displaystyle P_{2}=1-cR/d}$${\estilo de visualización x,y}$${\estilo de visualización R}$${\estilo de visualización h}$$Estilo de visualización P_{1}$${\estilo de visualización x,y}$${\estilo de visualización cR}$$Estilo de visualización P_{2}$

Supongamos que U está compuesto de subconjuntos de un conjunto básico de elementos enumerables S y que la función de similitud de interés es el índice de Jaccard J. Si π es una permutación de los índices de S , para sea . Cada posible elección de π define una única función hash h que asigna conjuntos de entrada a elementos de S.${\displaystyle A\subseteq S}$${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$

Defina la familia de funciones H como el conjunto de todas esas funciones y sea D la distribución uniforme . Dados dos conjuntos, el evento que corresponde exactamente al evento de que el minimizador de π sobre se encuentre dentro de . Como h se eligió de manera uniforme al azar, defina un esquema LSH para el índice de Jaccard.${\displaystyle A,B\subseteq S}$${\displaystyle h(A)=h(B)}$${\displaystyle A\copa B}$${\displaystyle A\cap B}$${\displaystyle Pr[h(A)=h(B)]=J(A,B)\,}$${\displaystyle (H,D)\,}$

Como el grupo simétrico de n elementos tiene un tamaño n !, la elección de una permutación verdaderamente aleatoria del grupo simétrico completo es inviable incluso para n de tamaño moderado . Debido a este hecho, se ha trabajado mucho para encontrar una familia de permutaciones que sea "min-independiente" —una familia de permutaciones para la que cada elemento del dominio tenga la misma probabilidad de ser el mínimo bajo un π elegido aleatoriamente . Se ha establecido que una familia de permutaciones independiente min-independiente tiene al menos un tamaño , ^[19] y que este límite es estricto. ^[20]${\displaystyle \operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{n-o(n)}}$

Debido a que las familias independientes en función de los valores mínimos son demasiado grandes para aplicaciones prácticas, se introducen dos nociones variantes de independencia en función de los valores mínimos: familias de permutaciones independientes en función de los valores mínimos restringidas y familias independientes en función de los valores mínimos aproximadas. La independencia en función de los valores mínimos restringida es la propiedad de independencia en función de los valores mínimos restringida a ciertos conjuntos de cardinalidad como máximo k . ^{[21] La independencia en función de los valores mínimos aproximada difiere de la propiedad en como máximo un} ε fijo . ^[22]

Nilsimsa es un algoritmo de hash sensible a la localidad que se utiliza en iniciativas antispam . ^[23] El objetivo de Nilsimsa es generar un resumen de hash de un mensaje de correo electrónico de modo que los resúmenes de dos mensajes similares sean similares entre sí. El artículo sugiere que Nilsimsa satisface tres requisitos:

1. El resumen que identifica cada mensaje no debe variar significativamente por los cambios que se pueden producir automáticamente.
2. La codificación debe ser robusta contra ataques intencionales.
3. La codificación debe soportar un riesgo extremadamente bajo de falsos positivos.

Las pruebas realizadas en el documento sobre una variedad de tipos de archivos identificaron que el hash Nilsimsa tiene una tasa de falsos positivos significativamente mayor en comparación con otros esquemas de resumen de similitud como TLSH, Ssdeep y Sdhash. ^[24]

TLSH es un algoritmo hash sensible a la localidad diseñado para una variedad de aplicaciones forenses digitales y de seguridad. ^[17] El objetivo de TLSH es generar resúmenes hash para mensajes de modo que las distancias bajas entre los resúmenes indiquen que es probable que sus mensajes correspondientes sean similares.

Una implementación de TLSH está disponible como software de código abierto . ^[25]

El método de proyección aleatoria de LSH creado por Moses Charikar ^[8] , llamado SimHash (también llamado a veces arccos ^[26] ), utiliza una aproximación de la distancia del coseno entre vectores. La técnica se utilizó para aproximar el problema de corte máximo NP-completo . ^[8]

La idea básica de esta técnica es elegir un hiperplano aleatorio (definido por un vector unitario normal r ) desde el principio y utilizar el hiperplano para generar hash en los vectores de entrada.

Dado un vector de entrada v y un hiperplano definido por r , hacemos que . Es decir, depende de qué lado del hiperplano v se encuentre. De esta manera, cada posible elección de un hiperplano aleatorio r puede interpretarse como una función hash .${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$${\displaystyle h(v)=\pm 1}$${\displaystyle h(v)}$

Para dos vectores u,v con ángulo entre ellos, se puede demostrar que${\displaystyle \theta (u,v)}$

${\displaystyle Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}.}$

Dado que la relación entre y es al menos 0,87856 cuando , ^{[8] [27]} la probabilidad de que dos vectores estén en el mismo lado del hiperplano aleatorio es aproximadamente proporcional a la distancia del coseno entre ellos.${\displaystyle {\frac {\theta (u,v)}{\pi }}}$${\displaystyle 1-\cos(\theta (u,v))}$${\displaystyle \theta (u,v)\in [0,\pi ]}$

La función hash ^[28] asigna un vector d -dimensional al conjunto de números enteros. Cada función hash de la familia está indexada por una elección aleatoria de y donde es un vector d -dimensional con entradas elegidas independientemente de una distribución estable y es un número real elegido uniformemente del rango [0,r]. Para un fijo la función hash está dada por .${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$${\displaystyle {\boldsymbol {\upsilon }}}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\displaystyle \mathbf {a} }$${\displaystyle b}$${\displaystyle \mathbf {a} ,b}$${\displaystyle h_{\mathbf {a} ,b}}$${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor }$

Se han propuesto otros métodos de construcción de funciones hash para ajustar mejor los datos. ^[29] En particular, las funciones hash k-means son mejores en la práctica que las funciones hash basadas en proyecciones, pero sin ninguna garantía teórica.

El hash semántico es una técnica que intenta asignar elementos de entrada a direcciones de modo que las entradas más cercanas tengan una mayor similitud semántica . ^[30] Los códigos hash se encuentran mediante el entrenamiento de una red neuronal artificial o un modelo gráfico . ^{[ cita requerida ]}

Una de las principales aplicaciones de LSH es proporcionar un método para algoritmos eficientes de búsqueda aproximada del vecino más próximo . Consideremos una familia LSH . El algoritmo tiene dos parámetros principales: el parámetro de ancho k y el número de tablas hash L.${\displaystyle {\mathcal {F}}}$

En el primer paso, definimos una nueva familia de funciones hash g , donde cada función g se obtiene concatenando k funciones de , es decir, . En otras palabras, una función hash aleatoria g se obtiene concatenando k funciones hash elegidas aleatoriamente de . A continuación, el algoritmo construye L tablas hash, cada una correspondiente a una función hash diferente elegida aleatoriamente g .${\displaystyle {\mathcal {G}}}$${\displaystyle h_{1},\ldots ,h_{k}}$${\displaystyle {\mathcal {F}}}$${\displaystyle g(p)=[h_{1}(p),\ldots ,h_{k}(p)]}$${\displaystyle {\mathcal {F}}}$

En el paso de preprocesamiento, convertimos todos los puntos n d -dimensionales del conjunto de datos S en cada una de las L tablas hash. Dado que las tablas hash resultantes tienen solo n entradas distintas de cero, se puede reducir la cantidad de memoria utilizada por cada tabla hash utilizando funciones hash estándar .${\displaystyle O(n)}$

Dado un punto de consulta q , el algoritmo itera sobre las L funciones hash g . Para cada g considerado, recupera los puntos de datos que están codificados en el mismo contenedor que q . El proceso se detiene tan pronto como se encuentra un punto dentro de la distancia cR desde q .

Dados los parámetros k y L , el algoritmo tiene las siguientes garantías de rendimiento:

• tiempo de preprocesamiento: , donde t es el tiempo para evaluar una función en un punto de entrada p ;${\displaystyle O(nLkt)}$${\displaystyle h\in {\mathcal {F}}}$
• espacio: , más el espacio para almacenar puntos de datos;${\displaystyle O(nL)}$
• tiempo de consulta: ;${\displaystyle O(L(kt+dnP_{2}^{k}))}$
• el algoritmo logra encontrar un punto dentro de la distancia cR desde q (si existe un punto dentro de la distancia R ) con una probabilidad al menos ;${\displaystyle 1-(1-P_{1}^{k})^{L}}$

Para una razón de aproximación fija y probabilidades y , se puede establecer y , donde . Entonces se obtienen las siguientes garantías de rendimiento:${\displaystyle c=1+\epsilon }$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle k=\left\lceil {\tfrac {\log n}{\log 1/P_{2}}}\right\rceil }$${\displaystyle L=\lceil P_{1}^{-k}\rceil =O(n^{\rho }P_{1}^{-1})}$${\displaystyle \rho ={\tfrac {\log P_{1}}{\log P_{2}}}}$

• tiempo de preprocesamiento :;${\displaystyle O(n^{1+\rho }P_{1}^{-1}kt)}$
• espacio: , más el espacio para almacenar puntos de datos;${\displaystyle O(n^{1+\rho }P_{1}^{-1})}$
• tiempo de consulta: ;${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d))}$

Cuando t es grande, es posible reducir el tiempo de hash de . Esto se demostró en ^[31] y ^[32], que dieron${\displaystyle O(n^{\rho })}$

• tiempo de consulta: ;${\displaystyle O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1}))}$
• espacio: ;${\displaystyle O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})}$

También ocurre a veces que el factor puede ser muy grande. Esto sucede, por ejemplo, con los datos de similitud Jaccard , donde incluso el vecino más similar suele tener una similitud Jaccard bastante baja con la consulta. En ^[33] se mostró cómo reducir el tiempo de consulta (sin incluir los costos de hash) y, de manera similar, el uso del espacio.${\displaystyle 1/P_{1}}$${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$

• Filtro Bloom  : estructura de datos para la pertenencia aproximada a un conjunto
• La maldición de la dimensionalidad  : dificultades que surgen al analizar datos con muchos aspectos ("dimensiones")
• Hashing de características  : vectorización de características mediante una función hash
• Transformadas relacionadas con Fourier
• Geohash  : geocodificación de dominio público inventada en 2008
• Aprendizaje de subespacios multilineales  : enfoque para la reducción de la dimensionalidad
• Análisis de componentes principales  – Método de análisis de datos
• Indexación aleatoria ^[34]
• Rolling hash  – Tipo de función hash
• Descomposición en valores singulares  – Descomposición matricial
• Memoria distribuida dispersa  : modelo matemático de la memoria
• Compresión wavelet  : técnica matemática utilizada en la compresión y análisis de datos.Pages displaying short descriptions of redirect targets

• Samet, H. (2006) Fundamentos de estructuras de datos multidimensionales y métricas . Morgan Kaufmann. ISBN 0-12-369446-9 
• Indyk, Piotr ; Motwani, Rajeev ; Raghavan, Prabhakar; Vempala, Santosh (1997). "Hash con preservación de localidad en espacios multidimensionales". Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación . STOC '97 . págs. 618–625. CiteSeerX  10.1.1.50.4927 . doi :10.1145/258533.258656. ISBN 978-0-89791-888-6.S2CID 15693787  .
• Chin, Andrew (1994). "Funciones hash que preservan la localidad para computación paralela de propósito general" (PDF) . Algorithmica . 12 (2–3): 170–181. doi :10.1007/BF01185209. S2CID  18108051.

• Página de inicio de LSH de Alex Andoni
• LSHKIT: una biblioteca de hash sensible a la localidad de C++
• Una biblioteca de hash sensible a la localidad de Python que admite opcionalmente la persistencia a través de redis
• Caja de herramientas de búsqueda de imágenes a gran escala de Caltech: una caja de herramientas de Matlab que implementa varias funciones hash LSH, además de algoritmos de búsqueda de árboles Kd, K-medias jerárquicas y archivos invertidos.
• Slash: una biblioteca LSH de C++ que implementa LSH esférico por Terasawa, K., Tanaka, Y.
• LSHBOX: una caja de herramientas C++ de código abierto de hash sensible a la localidad para la recuperación de imágenes a gran escala. También compatible con Python y MATLAB.
• SRS: Una implementación en C++ de un algoritmo de procesamiento de consultas de vecino más cercano aproximado y eficiente en el uso del espacio, basado en una proyección aleatoria p-estable
• TLSH de código abierto en Github
• Puerto JavaScript de TLSH (Trend Micro Locality Sensitive Hashing) incluido como módulo node.js
• Puerto Java de TLSH (Trend Micro Locality Sensitive Hashing) incluido como paquete maven