Hashing sensible a la localidad

En informática , el hashing sensible a la localidad ( LSH ) es una técnica algorítmica que convierte elementos de entrada similares en los mismos "cubos" con alta probabilidad. ^[1] (La cantidad de depósitos es mucho menor que el universo de posibles elementos de entrada). ^[1] Dado que los elementos similares terminan en los mismos depósitos, 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 convencionales de hash en que las colisiones hash se maximizan, no se minimizan. Alternativamente, la técnica puede verse como una forma de reducir la dimensionalidad .de datos de alta dimensión; los elementos de entrada de alta dimensión se pueden reducir a versiones de baja dimensión mientras se conservan las distancias relativas entre los elementos.

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

Se define una familia LSH ^{[1] [4] [5]} para ${\displaystyle {\mathcal {F}}}$

Esta familia es un conjunto de funciones que mapean elementos del espacio métrico a cubos . Una familia LSH debe satisfacer las siguientes condiciones para dos puntos cualquiera y cualquier función hash elegida uniformemente al azar de :${\displaystyle {\mathcal {F}}}$${\displaystyle h\dos puntos M\to S}$${\ estilo de visualización s \ en S}$${\ estilo de visualización p, q \ en M}$${\ estilo de visualización h}$${\displaystyle {\mathcal {F}}}$

Una familia es interesante cuando . Tal familia se llama -sensible .${\displaystyle P_{1}>P_{2}}$${\displaystyle {\mathcal {F}}}$${\ estilo de visualización (R, cR, P_{1}, P_{2})}$

Alternativamente ^[6] se define con respecto a un universo de elementos U que tienen una función de similitud . Un esquema LSH es una familia de funciones hash H junto con una distribución de probabilidad D sobre las funciones tal que una función elegida de acuerdo con D satisface la propiedad de que para cualquier .${\displaystyle \phi \colon U\times U\to [0,1]}$ ${\ estilo de visualización h \ en H}$${\displaystyle Pr_{h\in H}[h(a)=h(b)]=\phi (a,b)}$${\ estilo de visualización a, b \ en U}$

Para ángulos pequeños (no demasiado cerca de los ortogonales), es una aproximación bastante buena a .${\displaystyle 1-{\frac {\theta}{\pi}}}$${\ estilo de visualización \ cos (\ theta)}$