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.^[1] (El nombre de cubs és molt més petit que l'univers de possibles elements d'entrada.) ^[1] 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).^[2]

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.^[3]^[4]

Definicions

Una família ${\mathcal {F}}$ de funcions $h\colon M\to S$ es defineix com una família de LSH ^[5]^[6] 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}}$ .^[7]

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,0 ^1,1 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.».

[MOMD-1] 1,0 ^1,1 Rajaraman, A. «Mining of Massive Datasets, Ch. 3.» (en anglès).

[2] 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.

[Chin1991-3] Complexity Issues in General Purpose Parallel Computing (Tesi) (en anglès), 1991, p. 87–95.

[Chin1994-4] Chin, Andrew Algorithmica, 12, 2–3, 1994, pàg. 170–181. DOI: 10.1007/BF01185209.

[MOMD2-5] Rajaraman, A. «Mining of Massive Datasets, Ch. 3.» (en anglès).

[GIM1999-6] Gionis, A.; Indyk, P.; Motwani, R. Proceedings of the 25th Very Large Database (VLDB) Conference, 1999.

[MOMD3-7] Rajaraman, A. «Mining of Massive Datasets, Ch. 3.».

[1]

[2]

[3]

[4]

[5]

[6]

[7]