Locality sensitive hashing

Une famille LSH ${\displaystyle {\mathcal {F}}}$ est définie pour un espace métrique ${\displaystyle {\mathcal {M}}=(M,d)}$, un seuil ${\displaystyle R>0}$ et un facteur d'approximation ${\displaystyle c>1}$ [1]^, [2]. En pratique, on a souvent ${\displaystyle {\mathcal {M}}=\mathbb {R} ^{d}}$.

${\displaystyle {\mathcal {F}}}$ est une famille de fonctions ${\displaystyle h:{\mathcal {M}}\to S}$ satisfaisant les conditions suivantes pour deux points quelconques ${\displaystyle p,q\in {\mathcal {M}}}$, et une fonction ${\displaystyle h}$ choisie aléatoirement parmi la famille ${\displaystyle {\mathcal {F}}}$ :

• si ${\displaystyle d(p,q)\leq R}$, alors ${\displaystyle Pr_{h\in H}[h(p)=h(q)]\geq P_{1}}$
• si ${\displaystyle d(p,q)\geq cR}$, alors ${\displaystyle Pr_{h\in H}[h(p)=h(q)]\leq P_{2}}$

Par construction, les fonctions de hachage doivent permettre aux points proches d'entrer fréquemment en collision (i.e. ${\displaystyle h(p)=h(q)}$) et inversement, les points éloignés ne doivent entrer que rarement en collision. Pour que la famille LSH soit intéressante, il faut donc ${\displaystyle P_{2}<P_{1}}$. La famille ${\displaystyle {\mathcal {F}}}$ est alors appelée ${\displaystyle (R,cR,P_{1},P_{2})}$-sensitive. La famille est d'autant plus intéressante si ${\displaystyle P_{1}}$ est très supérieure à ${\displaystyle P_{2}}$.

Une définition alternative[3] est définie par rapport à un univers ${\displaystyle U}$ possédant une fonction de similarité ${\displaystyle \phi :U\times U\to [0,1]}$. Une famille LSH est alors un ensemble de fonctions de hachage ${\displaystyle H}$ et une distribution de probabilité ${\displaystyle D}$ sur les fonctions, telle qu'une fonction ${\displaystyle h\in H}$ choisie selon ${\displaystyle D}$ satisfait la propriété ${\displaystyle Pr_{h\in H}[h(a)=h(b)]=\phi (a,b)}$ pour tout ${\displaystyle a,b\in U}$.

LSH a été appliqué dans plusieurs domaines, en particulier pour la recherche d'image par le contenu, la comparaison de sequence d'ADN[4], la recherche par similarité de documents audios.

L'application principale de LSH est de fournir un algorithme efficace de recherche des plus proches voisins.

L'algorithme donne une méthode de construction d'une famille LSH ${\displaystyle {\mathcal {G}}}$ utilisable, c'est-à-dire telle que ${\displaystyle P_{1}\gg P_{2}}$, et ceci à partir d'une famille LSH ${\displaystyle {\mathcal {F}}}$ de départ. L'algorithme a deux paramètres principaux : le paramètre de largeur ${\displaystyle k}$ et le nombre de tables de hachage ${\displaystyle L}$.

Pré-traitement

En pré-traitement, l'algorithme définit donc une nouvelle famille ${\displaystyle {\mathcal {G}}}$ de fonctions de hachage ${\displaystyle g}$, où chaque fonction ${\displaystyle g}$ est obtenue par concaténation de ${\displaystyle k}$ fonctions ${\displaystyle h_{1},...,h_{k}}$ de ${\displaystyle {\mathcal {F}}}$, i.e., ${\displaystyle g(p)=[h_{1}(p),...,h_{k}(p)]}$. En d'autres termes, une fonction de hachage aléatoire ${\displaystyle g}$ est obtenue par concaténation de ${\displaystyle k}$ fonctions de hachage choisies aléatoirement dans ${\displaystyle {\mathcal {H}}}$.

L'algorithme construit ensuite ${\displaystyle L}$ tables de hachage, correspondant chacune à une fonction de hachage ${\displaystyle g}$. La j^e table de hachage contient alors les points de ${\displaystyle {\mathcal {M}}}$ hachés par la fonction ${\displaystyle g_{j}}$. Seules les positions non-vides des tables de hachage sont conservées, en utilisant un hachage standard des valeurs de ${\displaystyle g_{j}(p)}$. Les tables de hachage résultats n'ont alors que ${\displaystyle n}$ entrées (non-vides), réduisant l'espace mémoire par table à ${\displaystyle O(n)}$ et donc ${\displaystyle O(nL)}$ pour la structure de donnée totale.

Recherche d'un point requête ${\displaystyle q}$

Pour un point requête ${\displaystyle q}$, l'algorithme itère sur les ${\displaystyle L}$ fonctions de hachage ${\displaystyle g}$. Pour chaque ${\displaystyle g}$ considérée, on trouve les points hachés à la même position que le point requête ${\displaystyle q}$ dans la table correspondante. Le processus s'arrête dès qu'un point r est trouvé tel que ${\displaystyle d(r,q)\leq cR}$.

Étant donné les paramètres ${\displaystyle k}$ et ${\displaystyle L}$, l'algorithme a les garanties de performance suivantes :

• temps de pré-traitement : ${\displaystyle O(nLkt)}$, où ${\displaystyle t}$ est le temps d'évaluation d'une fonction ${\displaystyle h\in F}$ d'un point ${\displaystyle p}$;
• mémoire : ${\displaystyle O(nL)}$
• temps de requête : ${\displaystyle O(L(kt+dnP_{2}^{k}))}$;
• l'algorithme a une probabilité de trouver un point à une distance ${\displaystyle cR}$ de la requête ${\displaystyle q}$ (si un tel point existe) avec une probabilité ${\displaystyle \Omega (\min\{1,LP_{1}^{k}\})}$.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Locality-sensitive hashing » (voir la liste des auteurs).