Lokalitetskänslig hashing

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 augusti 2017; kontroller kräver 11 redigeringar .

Lokalitetskänslig hashing ( LSH [1] ) är en probabilistisk metod för att minska flerdimensionell data. Huvudtanken är att välja hashfunktioner för vissa dimensioner så att liknande objekt med hög grad av sannolikhet hamnar i samma korg [2] . Ett av sätten att bekämpa "dimensionalitetens förbannelse" när man söker och analyserar flerdimensionell data, vilket är att när dimensionaliteten hos källdata växer, beter sig indexuppslagningar sämre än sekventiella uppslagningar. Metoden låter dig bygga en struktur för en snabb ungefärlig (probabilistisk) sökning efter n - dimensionella vektorer "liknande" det önskade mönstret.

LSH är en av de mest populära ungefärliga algoritmerna för att hitta närmaste grannar (Approximate Nearest Neighbor, ANN). LSH i detta tillvägagångssätt mappar en uppsättning punkter i ett högdimensionellt utrymme till en uppsättning celler, d.v.s. en hashtabell. Till skillnad från traditionella hash har LSH egenskapen platskänslighet (lokalitetskänslig hash), tack vare vilken den kan placera närliggande punkter i samma cell.

Fördelarna med LSH är: 1) användarvänlighet; 2) en rigorös teori som bekräftar algoritmens goda prestanda; 3) LSH är kompatibel med alla normer vid . LSH kan användas med den euklidiska metriken och med Manhattan-avståndet . Det finns även alternativ för Hamming-avstånd och cosinusfaktor [3] .

Anteckningar

  1. ↑ Piotr Indyk; Rajeev Motwani. Ungefärliga närmaste grannar: mot att ta bort dimensionalitetens förbannelse   // Proc . av 30:e STOC'98 Proceedings of the trettionth 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 och J. Ullman. Utvinning av massiva datamängder, kap. 3.4 (2010). Hämtad 17 september 2013. Arkiverad från originalet 18 augusti 2013.
  3. ↑ M. Slaney; M. Casey. Lokalitetskänslig hashning för att hitta närmaste grannar   : journal . — 2008.

Länkar