# Hashing sensible a la localitat

En informàtica, el hash sensible a la localitat (LSH) és una tècnica hash difusa que agrupa elements d'entrada similars als mateixos "cubs" amb alta probabilitat. (El nombre de cubs és molt més petit que l'univers de possibles elements d'entrada.) Com que els articles similars acaben en els mateixos cubs, aquesta tècnica es pot utilitzar per agrupar dades i cercar el veí més proper. Es diferencia de les tècniques de hash convencionals en què les col·lisions de hash es maximitzen, no es minimitzen. Alternativament, la tècnica es pot veure com una manera de reduir la dimensionalitat de les dades d'alta dimensió; Els elements d'entrada d'alta dimensió es poden reduir a versions de dimensions baixes alhora que es conserven les distàncies relatives entre els elements.
Els algorismes de cerca aproximada del veí més proper basats en hash generalment utilitzen una de les dues categories principals de mètodes de hash: mètodes independents de les dades, com ara el hashing sensible a la localitat (LSH); o mètodes que depenen de les dades, com ara el hashing que preserva la localitat (LPH).
El hashing per preservar la localitat es va idear inicialment com una manera de facilitar la canalització de dades en implementacions d'algorismes massivament paral·lels que utilitzen l'encaminament aleatori i el hash universal per reduir la confusió de memòria i la congestió de la xarxa.

## Definicions

Una família ${\mathcal {F}}$ de funcions $h\colon M\to S$ es defineix com una família de LSH per
* un espai mètric,
* un llindar,
* un factor d'aproximació,
* i probabilitats
si compleix la següent condició. Per dos punts qualsevol $a,b\in M$ i una funció hash $h$ triat uniformement a l'atzar de ${\mathcal {F}}$ :
* Si, doncs (és a dir, p i q xoquen) amb probabilitat almenys,
* Si, doncs amb probabilitat com a màxim.
Donat a $(d_{1},d_{2},p_{1},p_{2})$ - Família sensible ${\mathcal {F}}$, podem construir noves famílies ${\mathcal {G}}$ mitjançant la construcció AND o la construcció OR de ${\mathcal {F}}$.

## Aplicacions

LSH s'ha aplicat a diversos dominis problemàtics, com ara:
* Detecció gairebé duplicada
* Agrupació jeràrquica
* Estudi d'associació a tot el genoma
* Identificació de semblança d'imatges
** VisualRank
* Identificació de semblança d'expressió gènica
* Identificació de semblança d'àudio
* Cerca de veïns més propers
* empremta digital d'àudio
* Impressió digital de vídeo
* Organització de memòria compartida en informàtica paral·lela
* Organització de dades físiques en sistemes de gestió de bases de dades
* Entrenament de xarxes neuronals completament connectades
* Seguretat informàtica

## Referències

* 1 2 Rajaraman, A. «Mining of Massive Datasets, Ch. 3.» (en anglès).
* ↑ Tsai, Yi-Hsuan. «Locality preserving hashing». A: 2014 IEEE International Conference on Image Processing (ICIP) (en anglès), October 2014, p. 2988–2992. DOI 10.1109/ICIP.2014.7025604. ISBN 978-1-4799-5751-4.
* ↑ Complexity Issues in General Purpose Parallel Computing (Tesi) (en anglès), 1991, p. 87–95.
* ↑ Chin, Andrew Algorithmica, 12, 2–3, 1994, pàg. 170–181. DOI: 10.1007/BF01185209.
* ↑ Rajaraman, A. «Mining of Massive Datasets, Ch. 3.» (en anglès).
* ↑ Gionis, A.; Indyk, P.; Motwani, R. Proceedings of the 25th Very Large Database (VLDB) Conference, 1999.
* ↑ Rajaraman, A. «Mining of Massive Datasets, Ch. 3.».