# Locality-sensitive hashing

Il locality-sensitive hashing (LSH) è un metodo per la riduzione della dimensionalità dello spazio vettoriale di un insieme di dati.

## Motivazioni

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 sistema real-time per soddisfare interrogazioni quali la similarità fra (parti di) immagini o (estratti di) brani musicali.
L'idea principale è applicare una funzione 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 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

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

* $D(\cdot ,\cdot )$ è 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 hash $h$ scelta a caso dalla famiglia LSH di funzioni 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(\cdot ,\cdot )$ 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 $\mathrm {Pr} _{\mathcal {H}}[h(q)=h(p)]\geq p_{1};$
* se $p\notin B(q,r_{2})$ allora $\mathrm {Pr} _{\mathcal {H}}[h(q)=h(p)]\leq 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}=cr_{1},$ con $c>1$.

### Interpretazione grafica

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

La funzione hash $h_{\mathbf {a} ,b}\colon \mathbb {R} ^{d}\to \mathbb {N}$ manda un vettore di $d$ componenti reali $\mathbf {v}$ in un intero non negativo. Ogni funzione hash appartenente alla famiglia viene selezionata scegliendo in modo casuale $\mathbf {a}$ e $b$ dove $\mathbf {a}$ è un vettore di $d$ componenti reali i cui elementi sono scelti in maniera indipendente da una distribuzione stabile e $b$ è un numero reale scelto secondo una distribuzione continua uniforme nell'intervallo $[0,r].$ Fissati $\mathbf {a} ,b$ e la funzione hash $h_{\mathbf {a} ,b}$ si calcola attraverso la relazione $h_{\mathbf {a} ,b}(\mathbf {v} )=\left\lfloor {\frac {\mathbf {a} \cdot \mathbf {v} +b}{r}}\right\rfloor ,$ dove $\mathbf {a} \cdot \mathbf {v}$ indica il prodotto scalare euclideo tra $\mathbf {a}$ e $\mathbf {v}$ e $\lfloor \cdot \rfloor$ indica la funzione parte intera.

### Ricerca dei Nearest Neighbor

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 hash $g$, in cui ogni funzione $g$ si ottiene concatenando $k$ funzioni $h_{1},\ldots ,h_{k}$ da ${\mathcal {F}}$, cioè
    $g(p)={\bigh_{1}(p),\ldots ,h_{k}(p){\big )}.$
La scelta di concatenare $k$ funzioni 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 hash $g$ presa casualmente da ${\mathcal {G}}$ si ottiene concatenando $k$ funzioni hash prese casualmente da ${\mathcal {H}}$.
Successivamente l'algoritmo costruisce $L$ tabelle di hash, ognuna corrispondente a una diversa funzione hash $g$.
Nella fase di preprocessing si fa un hash di tutti gli $n$ punti dell'insieme di dati $S$ in ognuna delle $L$ tabelle di hash. Dato che le tabelle di hash risultanti hanno solo $n$ elementi diversi da zero, si può ridurre l'utilizzo di memoria per ogni funzione hash a $O(n)$ usando funzioni hash standard.
Considerando l'interrogazione $q$ al sistema così creato, l'algoritmo itera sulle $L$ funzioni hash $g$. Per ogni $g$, reperisce i punti dell'insieme di dati 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$.