Lokalitetsfølsom hashing

Lokalitetsfølsom hashing ( LSH ) er en omtrentlig søgemetode i store rum. Dette er en løsning på dimensionens forbandelsesproblem, der vises, når man søger efter de nærmeste naboer i store dimensioner. Hovedideen er at bruge en familie af hash-funktioner valgt således, at tætte punkter i det oprindelige rum har stor sandsynlighed for at have den samme hash-værdi. Metoden har mange anvendelser inden for kunstig vision , automatisk sprogbehandling , bioinformatik ...

Definition

En LSH-familie er defineret for et metrisk rum , en tærskel og en tilnærmelsesfaktor . I praksis har vi det ofte . ${\ mathcal {F}}$ ${\ mathcal M} = (M, d)$ $R> 0$ $c> 1$ ${\ mathcal M} = {\ mathbb {R}} ^ {d}$

${\ mathcal {F}}$ er en familie af funktioner, der opfylder følgende betingelser for to punkter , og en funktion valgt tilfældigt fra familien : $h: {{\ mathcal M}} \ til S$ $p, q \ i {{\ mathcal M}}$ $h$ ${\ mathcal {F}}$

hvis , så $d (p, q) \ leq R$ $Pr _ {{h \ in H}} [h (p) = h (q)] \ geq P_ {1}$
hvis , så $d (p, q) \ geq cR$ $Pr _ {{h \ in H}} [h (p) = h (q)] \ leq P_ {2}$

Ved konstruktion skal hash-funktioner tillade, at nærliggende punkter kolliderer ofte (dvs. ) og omvendt, langt punkter sjældent skal kollidere. For at LSH-familien er interessant, er det nødvendigt . Familien kaldes derefter -følsom . Familien er så meget mere interessant, hvis den er meget større end . $h (p) = h (q)$ $P_ {2} <P_ {1}$ ${\ mathcal {F}}$ $(R, cR, P_ {1}, P_ {2})$ $P_ {1}$ $P_ {2}$

En alternativ definition er defineret med hensyn til et univers, der har en lighedsfunktion . En LSH-familie er derefter et sæt hash-funktioner og en sandsynlighedsfordeling over funktionerne, således at en funktion valgt i henhold til opfylder egenskaben for alle . $U$ $\ phi: U \ gange U \ til [0,1]$ $H$ $D$ $h \ i H$ $D$ $Pr _ {{h \ in H}} [h (a) = h (b)] = \ phi (a, b)$ $a, b \ i U$

Ansøgninger

LSH er blevet anvendt i flere felter, især til søgning efter indholdsbilleder , sammenligning af DNA-sekvenser, søgning efter lyddokumentlighed.

Metoder

Bitvis prøveudtagning til Hamming-afstand

Bitprøveudtagning er en enkel metode til at opbygge en LSH-familie. Denne tilgang er tilpasset Hamming-afstanden i et binært dimension af dimension , dvs. når et punkt i rummet hører til . Familien af hashfunktioner er da det sæt af projektioner på en af de koordinater, det vil sige ,, hvor er det jeg th koordinat for . En tilfældig funktion af vælger derfor kun en tilfældig bit i den oprindelige vektor . $d$ $\ {0,1 \} ^ {d}$ ${\ mathcal {F}}$ $d$ ${{\ mathcal F}} = \ {h: \ {0.1 \} ^ {d} \ to \ {0.1 \} \ mid h (x) = x_ {i}, i = 1 ... d \}$ $x_ {i}$ $x$ $h$ ${{\ mathcal F}}$ $x$

Denne familie har følgende parametre:

$P_ {1} = 1-R / d$
$P_ {2} = 1-cR / d$ .

LSH-algoritmen til at finde nærmeste naboer

Den primære anvendelse af LSH er at tilvejebringe en effektiv nærmeste nabo- søgealgoritme .

Algoritmen giver en metode til at konstruere en brugbar LSH-familie , det vil sige , og dette fra en startende LSH-familie . Algoritmen har to hovedparametre: bredde-parameteren og antallet af hash-tabeller . ${\ mathcal {G}}$ $P_ {1} \ gg P_ {2}$ ${\ mathcal {F}}$ $k$ $L$

Forbehandling

I forbehandling, algoritmen definerer derfor en ny familie af hashfunktioner hvor hver funktion opnås ved sammenkædning funktion af , dvs. . Med andre ord opnås en tilfældig hash-funktion ved sammenkædning af hash-funktioner valgt tilfældigt blandt . ${\ mathcal {G}}$ $g$ $g$ $k$ $h_ {1}, ..., h_ {k}$ ${\ mathcal {F}}$ $g (p) = [h_ {1} (p), ..., h_ {k} (p)]$ $g$ $k$ ${\ mathcal H}$

Algoritmen konstruerer derefter hash-tabeller, der hver svarer til en hash-funktion . J th hash-tabellen indeholder derefter de punkter, der er hakket af funktionen . Kun hash-tabellernes ikke-tomme positioner bevares ved hjælp af en standard-hash af værdierne for . Resultatet hash-tabeller har derefter kun poster (ikke-tomme), hvilket reducerer hukommelsespladsen pr. Tabel til og derfor for den samlede datastruktur. $L$ $g$ ${\ mathcal {M}}$ $g_ {j}$ $g_ {j} (p)$ $ikke$ $Vi)$ $O (nL)$

Søg efter et forespørgsel

q

For et forespørgselspunkt gentages algoritmen over hash-funktionerne . For hver betragtet finder vi de hashede punkter på samme position som forespørgselspunktet i den tilsvarende tabel. Processen stopper, så snart et punkt r findes således, at . $q$ $L$ $g$ $g$ $q$ $d (r, q) \ leq cR$

I betragtning af parametrene og har algoritmen følgende præstationsgarantier: $k$ $L$

forbehandlingstid :, hvor er evalueringstiden for en funktion af et punkt ; $O (nLkt)$ $t$ $h \ i F$ $s$
hukommelse: $O (nL)$
anmodning tid: ; $O (L (kt + dnP_ {2} ^ {k}))$
algoritmen har en sandsynlighed for at finde et punkt i en afstand fra forespørgslen (hvis et sådant punkt findes) med en sandsynlighed . $cR$ $q$ $\ Omega (\ min \ {1, LP_ {1} ^ {k} \})$

Noter og referencer

(in) Gionis , P. Indyk og Rajeev Motwani , " Lighedssøgning i høje dimensioner via Hashing " , Forløb fra den 25. meget store database (VLDB) -konference ,1999( læs online )
(i) Piotr Indyk og Rajeev Motwani , " Anslåede nærmeste naboer: mod fjernelse af dimensionens forbandelse. » , Proceedings of 30th Symposium om Theory of Computing ,1998( læs online )
(i) Moses S. Charikar , " Lighed estimering fra Afrunding Algoritmer " , Proceedings of the 34th Annual ACM Symposium om Theory of Computing i 2002 ,2002, (ACM 1–58113–495–9 / 02/0005) ... ( DOI 10.1145 / 509907.509965 , læs online , adgang til 21. december 2007 )
Jeremy Buhler, Effektiv sammenligning i stor skala efter lokalitetsfølsom hashing , Bioinformatik 17: 419-428.
(i) Alexandr Andoni og Piotr Indyk , " Næsten optimal hashingalgoritme til omtrentlig nærmeste 'nabo i høje dimensioner " , Kommunikation af ACM, bind. 51 ,2008( læs online )

(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen " Lokalitetsfølsom hashing " ( se forfatterliste ) .

Se også

Relaterede artikler

Søg efter nærmeste naboer

eksterne links

Alex Andonis LSH-hjemmeside