Locality-sensitive Hashing

Da Wikipedia, l'enciclopedia libera.

Il Locality-sensitive Hashing (LSH) [1] [2] è un metodo per la riduzione delle dimensioni dello spazio vettoriale di un insieme di dati.

Motivazioni[modifica | modifica wikitesto]

La grossa mole di dati da elaborare, principalmente il calcolo della distanza fra gli oggetti (item) di un insieme di dati, è un grosso vincolo allo sviluppo di applicazioni real-time per soddisfare interrogazioni quali la similarità fra (parti di) immagini o (estratti di) brani musicali.

L'idea principale è di applicare una funzione di hash agli item in input in modo da far collidere, con alta probabilità, item simili negli stessi contenitori (bucket). Il numero di bucket è molto più ridotto dell'universo dei possibili item in input. L'obiettivo è di arrivare ad un hashing a due livelli:

  • la funzione LSH mappa un item p in un bucket g_j(p);
  • una funzione di hash standard mappa il contenuto di questi bucket in una hash table di lunghezza M.

La dimensione massima del bucket della seconda hash table verrà chiamato B.

Assunzioni[modifica | modifica wikitesto]

Con il metodo LSH si vuole fare in modo di correlare la distanza di due punti p e q alla probabilità di collisione in un bucket. Maggiore è la distanza fra i punti minore sarà la loro probabilità di collisione.

Definizione[modifica | modifica wikitesto]

  • D(.,.) è la funzione di distanza fra elementi di un insieme S;
  • B(p,r) indica, per ogni punto p \in S, l'insieme di elementi di S che stanno all'interno della distanza r da p.

Consideriamo una funzione di hash h scelta a caso dalla famiglia LSH di funzioni di hash disponibili \mathcal H. Una famiglia LSH \mathcal H di funzioni dall'insieme S all'insieme U è detta (r_1,r_2,p_1,p_2)-sensitive per D(.,.) se per ogni coppia di punti q (che è la rappresentazione dell'interrogazione) e p (che è il punto che soddisfa le condizioni sotto riportate) appartenenti all'insieme S:

  • se p \in B(q,r_1) allora Pr_\mathcal H [h(q)=h(p)] \ge p_1
  • se p \notin B(q,r_2) allora Pr_\mathcal H [h(q)=h(p)] \le p_2

Affinché la famiglia LSH sia utile per gli scopi che ci si è prefissi devono valere le due condizioni:

  • p_1 > p_2;
  • r_1 < r_2.

Di solito si considera r_2 = c \cdot r_1 con c > 1.

Interpretazione grafica[modifica | modifica wikitesto]

In uno spazio a due dimensioni si hanno due cerchi concentrici centrati sulla rappresentazione dell'interrogazione q. Ricordando che B(q,r_1) e B(q,r_2) rappresentano dei sottoinsiemi dell'insieme di dati S:

  • Il cerchio più interno di raggio r_1 contiene i punti p dell'insieme di dati B(q,r_1) che hanno, come precedentemente descritto, una probabilità maggiore della soglia p_1 di subire un hash nello stesso bucket.
  • Il cerchio più esterno di raggio r_2 esclude i punti p dell'insieme di dati B(q,r_2) che hanno, come precedentemente descritto, una probabilità minore della soglia p_2 di subire un hash nello stesso bucket.

LSH e distribuzioni stabili[modifica | modifica wikitesto]

La funzione di hash [3] h_{\mathbf{a},b} (\boldsymbol{\upsilon}) : 
\mathcal{R}^d
\to \mathcal{N} mappa un vettore di d dimensioni \boldsymbol{\upsilon} in un insieme di interi. Ogni funzione di hash appartenente alla famiglia viene selezionata scegliendo in modo casuale \mathbf{a} e b dove \mathbf{a} è un vettore di d dimensioni le cui componenti sono scelte in maniera indipendente da una distribuzione stabile e b è un numero reale scelto in maniera uniforme nell'intervallo [0,r]. Fissati \mathbf{a},b la funzione di hash h_{\mathbf{a},b} si calcola attraverso la relazione h_{\mathbf{a},b} (\boldsymbol{\upsilon}) = \left \lfloor \frac{\mathbf{a}\cdot \boldsymbol{\upsilon}+b}{r} \right \rfloor .

Ricerca dei Nearest Neighbor[modifica | modifica wikitesto]

Una delle principali applicazioni di LSH è quella di fornire un algoritmo efficiente per il problema della ricerca del nearest neighbor. Data una qualsiasi famiglia LSH \mathcal F l'algoritmo ha due parametri principali:

  • la larghezza k;
  • il numero di tabelle di hash L.

Cominciamo definendo una nuova famiglia \mathcal G di funzioni di hash g, in cui ogni funzione g si ottiene concatenando k funzioni h_1,...,h_k da \mathcal F, i.e.

g(p)=[h_1(p), ...,h_k(p)]

La scelta di concatenare k funzioni di hash per ottenere g è giustificata dal fatto che si vuole amplificare la differenza tra la alta probabilità p_1 e la bassa probabilità p_2.

In altre parole, una funzione di hash g presa a random da \mathcal G si ottiene concatenando k funzioni di hash prese a random da \mathcal H.

Successivamente l'algoritmo costruisce L tabelle di hash, ognuna corrispondente a una diversa funzione di hash g.

Nella fase di preprocessing facciamo un hash di tutti gli n punti del data-set S in ognuna delle L tabelle di hash. Dato che le tabelle di hash risultanti hanno solo n entry diverse da zero, si può ridurre l'utilizzo di memoria per ogni funzione di hash a O(n) usando funzioni di hash standard.

Considerando l'interrogazione q (query) al sistema così creato, l'algoritmo itera sulle L funzioni di hash g. Per ogni g, reperisce i punti del data-set che sono stati mappati dall'hash nello stesso bucket in cui è stata mappata q. Il processo si conclude quando viene reperito un punto di distanza cR da q.

Note[modifica | modifica wikitesto]

  1. ^ Gionis, A., Indyk, P., Motwani, R., , Similarity Search in High Dimensions via Hashing in Proceedings of the 25th Very Large Database (VLDB) Conference, 1999.
  2. ^ Indyk, Piotr., Motwani, Rajeev., , Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. in Proceedings of 30th Symposium on Theory of Computing, 1998.
  3. ^ Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S., Locality-Sensitive Hashing Scheme Based on p-Stable Distributions in Proceedings of the Symposium on Computational Geometry, 2004.

Voci correlate[modifica | modifica wikitesto]