Locality sensitive hashing 📖 Wikipedia

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}$  et deux valeurs de probabilité ${\displaystyle P_{1}}$  et ${\displaystyle P_{2}}$ ^[1],[2]. En pratique, on a souvent ${\displaystyle {\mathcal {M}}=\mathbb {R} ^{d}}$ .

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

1. si ${\displaystyle d(p,q)\leq R}$ , alors ${\displaystyle Pr_{h\in H}[h(p)=h(q)]\geq P_{1}}$ 
2. 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)}$ ). 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] s'appuie sur 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'échantillonnage de bit^[2],[5] est une méthode simple permettant de construire une famille LSH. Cette approche est adaptée à la distance de Hamming dans un espace binaire de dimension ${\displaystyle d}$  , i.e. quand un point de l'espace appartient à ${\displaystyle \{0,1\}^{d}}$ . La famille ${\displaystyle {\mathcal {F}}}$  de fonctions de hachage est alors l'ensemble des projections sur une des ${\displaystyle d}$  coordonnées, i.e., ${\displaystyle {\mathcal {F}}=\{h:\{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i},i=1...d\}}$ , où ${\displaystyle x_{i}}$  est la i^e coordonnée de ${\displaystyle x}$ . Une fonction aléatoire ${\displaystyle h}$  de ${\displaystyle {\mathcal {F}}}$  ne fait donc que sélectionner un bit au hasard dans le vecteur ${\displaystyle x}$  d'origine.

Cette famille possède les paramètres suivants :

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

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).

• Recherche des plus proches voisins

• Alex Andoni's LSH homepage

•   Portail de l’imagerie numérique
•   Portail de l'informatique théorique