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 in un bucket ;
  • 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 e alla probabilità di collisione in un bucket. Maggiore è la distanza fra i punti minore sarà la loro probabilità di collisione.

Definizione[modifica | modifica wikitesto]

  • è la funzione di distanza fra elementi di un insieme ;
  • indica, per ogni punto , l'insieme di elementi di che stanno all'interno della distanza da .

Consideriamo una funzione di hash scelta a caso dalla famiglia LSH di funzioni di hash disponibili . Una famiglia LSH di funzioni dall'insieme all'insieme è detta -sensitive per se per ogni coppia di punti (che è la rappresentazione dell'interrogazione) e (che è il punto che soddisfa le condizioni sotto riportate) appartenenti all'insieme :

  • se allora
  • se allora

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

  • ;
  • .

Di solito si considera con .

Interpretazione grafica[modifica | modifica wikitesto]

In uno spazio a due dimensioni si hanno due cerchi concentrici centrati sulla rappresentazione dell'interrogazione . Ricordando che e rappresentano dei sottoinsiemi dell'insieme di dati :

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

LSH e distribuzioni stabili[modifica | modifica wikitesto]

La funzione di hash [3] mappa un vettore di d dimensioni in un insieme di interi. Ogni funzione di hash appartenente alla famiglia viene selezionata scegliendo in modo casuale e dove è un vettore di d dimensioni le cui componenti sono scelte in maniera indipendente da una distribuzione stabile e è un numero reale scelto in maniera uniforme nell'intervallo [0,r]. Fissati la funzione di hash si calcola attraverso la relazione .

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 l'algoritmo ha due parametri principali:

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

Cominciamo definendo una nuova famiglia di funzioni di hash , in cui ogni funzione si ottiene concatenando funzioni da , i.e.

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

In altre parole, una funzione di hash presa a random da si ottiene concatenando funzioni di hash prese a random da .

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

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

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

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 (ps), in Proceedings of the Symposium on Computational Geometry, 2004.

Voci correlate[modifica | modifica wikitesto]