Hashing sensible a la localidad

---

En informática , el hash sensible a la localidad ( LSH ) es una técnica algorítmica que codifica elementos de entrada similares en los mismos "depósitos" con alta probabilidad. ^[1] (El número de depósitos es mucho menor que el universo de posibles elementos de entrada). ^[1] Dado que 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 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 datos de alta dimensión; Los elementos de entrada de alta dimensión se pueden reducir a versiones de baja dimensión preservando al mismo tiempo las distancias relativas entre los elementos.

Los algoritmos de búsqueda del 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 datos, como el hash que preserva la localidad (LPH). ^{[2] [3]}

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

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

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

Una familia es interesante cuando . Una familia así se llama -sensible .${\ Displaystyle P_ {1}> P_ {2}}$${\displaystyle {\mathcal {F}}}$${\ Displaystyle (R, cR, P_ {1}, P_ {2})}$

---