Viquipèdia

Hashing sensible a la localitat

mètode de reducció de dimensions en què els elements més propers tenen més probabilitats de ser assignats al mateix cub hash

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 modifica

Una família   de funcions   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   i una funció hash   triat uniformement a l'atzar de   :

  • Si, doncs (és a dir, p i q xoquen) amb probabilitat almenys,
  • Si, doncs amb probabilitat com a màxim.

Donat a   - Família sensible  , podem construir noves famílies   mitjançant la construcció AND o la construcció OR de  .[7]

Aplicacions modifica

LSH s'ha aplicat a diversos dominis problemàtics, com ara:

Referències modifica

  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. 
  3. ↑ Complexity Issues in General Purpose Parallel Computing (Tesi) (en anglès), 1991, p. 87–95. 
  4. ↑ Chin, Andrew Algorithmica, 12, 2–3, 1994, pàg. 170–181. DOI: 10.1007/BF01185209.
  5. ↑ Rajaraman, A. «Mining of Massive Datasets, Ch. 3.» (en anglès).
  6. ↑ Gionis, A.; Indyk, P.; Motwani, R. Proceedings of the 25th Very Large Database (VLDB) Conference, 1999.
  7. ↑ Rajaraman, A. «Mining of Massive Datasets, Ch. 3.».
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Hashing_sensible_a_la_localitat&oldid=33370827»