Hashing sensibil la localitate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 11 august 2017; verificările necesită 11 modificări .

Hashingul sensibil la localitate ( LSH [1] ) este o metodă probabilistică pentru reducerea dimensiunii datelor multidimensionale. Ideea principală este de a selecta funcții hash pentru unele dimensiuni, astfel încât obiecte similare cu un grad mare de probabilitate să cadă în același coș [2] . Una dintre modalitățile de a combate „blestemul dimensionalității” atunci când se caută și se analizează date multidimensionale, și anume că atunci când dimensionalitatea datelor sursă crește, căutările de index se comportă mai rău decât căutările secvențiale. Metoda vă permite să construiți o structură pentru o căutare rapidă aproximativă (probabilistă) a vectorilor n -dimensionali „similari” modelului dorit.

LSH este unul dintre cei mai populari algoritmi aproximativi pentru găsirea celor mai apropiați vecini (Approximate Nearest Neighbor, ANN). LSH în această abordare mapează un set de puncte dintr-un spațiu de dimensiuni mari într-un set de celule, adică un tabel hash. Spre deosebire de hashurile tradiționale, LSH are proprietatea de sensibilitate la locație (hash sensibil la localitate), datorită căreia este capabil să plaseze puncte învecinate în aceeași celulă.

Avantajele LSH sunt: ​​1) ușurință în utilizare; 2) o teorie riguroasă care confirmă buna performanță a algoritmului; 3) LSH este compatibil cu orice normă la . LSH poate fi folosit cu metrica euclidiană și cu distanța Manhattan . Există, de asemenea, opțiuni pentru distanța Hamming și factorul cosinus [3] .

Note

  1. ↑ Piotr Indyk; Rajeev Motwani. Cei mai apropiați vecini aproximativi: spre înlăturarea blestemului dimensionalității   // Proc . din 30th STOC'98 Proceedings of the30th annual ACM symposium on Theory of computing : journal. - 1998. - P. 604-613 . - ISBN 0-89791-962-9 . doi : 10.1145 / 276698.276876 .
  2. ↑ A. Rajaraman și J. Ullman. Exploatarea seturilor de date masive, cap. 3.4 (2010). Consultat la 17 septembrie 2013. Arhivat din original la 18 august 2013.
  3. ↑ M. Slaney; M. Casey. Hashing sensibil la localitate pentru găsirea celor mai apropiați vecini   : jurnal . — 2008.

Link -uri