Hashing sensible a la localidad

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

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

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

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

Una de las formas más sencillas de construir una familia LSH es mediante el muestreo de bits. ^{[ 7 ]} Este enfoque funciona para la distancia de Hamming sobre vectores de d dimensiones.${\displaystyle \{0,1\}^{d}}$Aquí, la familia${\displaystyle {\mathcal {F}}}$de funciones hash es simplemente la familia de todas las proyecciones de puntos en uno de los${\displaystyle d}$coordenadas, es decir,${\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\}\}}$, dónde${\displaystyle x_{i}}$es el${\displaystyle i}$la coordenada de${\displaystyle x}$Una función aleatoria${\displaystyle h}$de${\displaystyle {\mathcal {F}}}$Simplemente selecciona un bit aleatorio del punto de entrada. Esta familia tiene los siguientes parámetros:${\displaystyle P_{1}=1-R/d}$,${\displaystyle P_{2}=1-cR/d}$. Es decir, cualesquiera dos vectores${\displaystyle x,y}$con distancia de Hamming como máximo${\displaystyle R}$colisionar bajo una fuerza aleatoria${\displaystyle h}$con probabilidad al menos${\displaystyle P_{1}}$. Cualquier${\displaystyle x,y}$con distancia de Hamming al menos${\displaystyle cR}$colisionar con probabilidad como máximo${\displaystyle P_{2}}$.

Supongamos que U está compuesto por subconjuntos de algún conjunto base 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${\displaystyle A\subseteq S}$dejar${\displaystyle h(A)=\min _{a\in A}\{\pi (a)\}}$Cada posible elección de π define una única función hash h que asigna conjuntos de entrada a elementos de S.

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

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

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

El método de proyección aleatoria de LSH debido a Moses Charikar ^{[ 8 ]} llamado SimHash (también llamado a veces arccos ^{[ 27 ]} ) utiliza una aproximación de la distancia 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 consiste en elegir inicialmente un hiperplano aleatorio (definido por un vector unitario normal r ) y utilizar dicho hiperplano para aplicar una función hash a los vectores de entrada.

Dado un vector de entrada v y un hiperplano definido por r , dejamos${\displaystyle h(v)=\operatorname {sgn}(v\cdot r)}$. Eso es, ${\displaystyle h(v)=\pm 1}$dependiendo de en 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)}$.

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

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

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

La función hash ^{[ 29 ]}${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$mapea un vector d -dimensional${\displaystyle {\boldsymbol {\upsilon }}}$en el conjunto de enteros. Cada función hash de la familia está indexada por una elección aleatoria.${\displaystyle \mathbf {a} }$y ${\displaystyle b}$dónde${\displaystyle \mathbf {a} }$es un vector d -dimensional con entradas elegidas independientemente de una distribución estable y ${\displaystyle b}$es un número real elegido uniformemente del intervalo [0,r]. Para un fijo ${\displaystyle \mathbf {a} ,b}$la función hash${\displaystyle h_{\mathbf {a} ,b}}$es dado por${\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 para funciones hash para que se ajusten mejor a los datos. ^{[ 30 ]} En particular, las funciones hash k-means son mejores en la práctica que las funciones hash basadas en proyección, pero sin ninguna garantía teórica.

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

Para generalizar el algoritmo anterior sin que el radio R sea fijo, podemos tomar el algoritmo y realizar una especie de búsqueda binaria sobre R. Se ha demostrado ^{[ 32 ]} que existe una estructura de datos para el vecino más cercano aproximado con las siguientes garantías de rendimiento:

• espacio:${\displaystyle O(n^{1+\rho }P_{1}^{-1}d\log ^{2}n)}$;
• tiempo de consulta:${\displaystyle O(n^{\rho }P_{1}^{-1}(kt+d)\log n)}$;
• El algoritmo logra encontrar al vecino más cercano con una probabilidad de al menos${\displaystyle 1-((1-P_{1}^{k})^{L}\log n)}$;

Cuando t es grande, es posible reducir el tiempo de hash de${\displaystyle O(n^{\rho })}$Esto fue demostrado por ^{[ 33 ]} y ^{[ 34 ]} , que dieron

• 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 es a veces el caso que el factor${\displaystyle 1/P_{1}}$puede ser muy grande. Esto sucede, por ejemplo, con los datos de similitud de Jaccard , donde incluso el vecino más similar a menudo tiene una similitud de Jaccard bastante baja con la consulta. En ^{[ 35 ]} se mostró cómo reducir el tiempo de consulta a${\displaystyle O(n^{\rho }/P_{1}^{1-\rho })}$(sin incluir los costos de hash) y de manera similar el uso del espacio.