LSH

LSH

Locality sensitive hashing

Locality Sensitive Hashing (LSH) est une méthode de recherche approximative dans des espaces de grande dimension. C'est une solution au problème de la malédiction de la dimension qui apparait lors d'une recherche des plus proches voisins en grande dimension. L'idée principale est d'utiliser une famille de fonction de hachage choisies telles que des points proches dans l'espace d'origine aient une forte probabilité d'avoir la même valeur de hachage. La méthode a de nombreuses applications en vision artificielle, traitement automatique de la langue, bio-informatique...

Sommaire

Définition

Une famille LSH \mathcal F est définie pour un espace métrique \mathcal M =(M,d), un seuil R > 0 et un facteur d'approximation c > 1 [1] [2].

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

  • si d(p,q) \le R, alors Pr_{h \in H} [h(p) = h(q)] \ge P_1
  • si d(p,q) \ge cR, alors Pr_{h \in H} [h(p) = h(q)] \le P_2

Par construction, les fonctions de hachage doivent permettre aux points proches d'entrer fréquemment en collision (i.e. 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 P1 > P2. La famille \mathcal F est alors appelée (R,cR,P1,P2)-sensitive. La famille est d'autant plus intéressante si P1 est très supérieure à P2. En pratique, on a souvent \mathcal M = \mathbb{R}^d.

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

Applications

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.

Méthodes

Échantillonnage par bit pour la distance de Hamming

Une façon simple de construire une famille LSH est par échantillonage de bit[2],[5]. Cette approche est adaptée à la distance de Hamming dans un espace binaire de dimension d, i.e. un point de l'espace appartient à {0,1}d. La famille \mathcal F de fonctions de hachage est alors simplement l'ensemble des projections sur une des d coordonnées, i.e., {\mathcal F}=\{h:\{0,1\}^d\to \{0,1\}\mid h(x)=x_i,i =1 ... d\}, où xi est la ie coordonnée de x. Une fonction aléatoire h de {\mathcal F} ne fait donc que sélectionner un bit au hasard dans le vecteur x d'origine.

Cette famille possède les paramètres suivants:

  • P1 = 1 − R / d
  • P2 = 1 − cR / d.

L'algorithme LSH pour la recherche par plus proche voisins

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 \mathcal G utilisable, c'est à dire telle que P_1 \gg P_2, et ceci à partir d'une famille LSH \mathcal F de départ. L'algorithme a deux paramètres principaux: le paramètre de largeur k et le nombre de tables de hachage L.

Pré-traitement

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

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

Recherche d'un point requête q

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

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

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

Notes et références

  1. (en) Gionis, P. Indyk et R. Motwani, « Similarity Search in High Dimensions via Hashing », dans Proceedings of the 25th Very Large Database (VLDB) Conference, 1999 [, texte intégral] 
  2. a  et b (en) Piotr Indyk et Rajeev Motwani, « Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. », dans Proceedings of 30th Symposium on Theory of Computing, 1998 [, texte intégral] 
  3. Charikar, « Similarity Estimation Techniques from Rounding Algorithms », dans Proceedings of the 34th Annual ACM Symposium on Theory of Computing 2002, 2002, p. (ACM 1–58113–495–9/02/0005)… [texte intégral lien DOI (pages consultées le 2007-12-21)] 
  4. Jeremy Buhler, Efficient large-scale sequence comparison by locality-sensitive hashing, Bioinformatics 17: 419-428.
  5. (en) Alexandr Andoni et Piotr Indyk, « Near-optimal hashing algorithm for approximate nearest neighbour in high dimensions », dans Communications of the ACM, Vol. 51, 2008 [texte intégral] 

Voir aussi

Articles connexes

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Locality sensitive hashing ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article LSH de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Lsh — Maintainer: Niels Möller Aktuelle Version: v2.0.4 (05. Septempber 2007) Betriebssystem: Unix Kategorie: Networking, Security Lizenz …   Deutsch Wikipedia

  • lsh — Maintainer Niels Möller Aktuelle Version v2.0.4 (5. September 2007) Betriebssystem Unix Kategorie Networking, Security Lizenz …   Deutsch Wikipedia

  • LSH — can refer to:* Legion of Super Heroes, a superhero team * Locality sensitive hashing, a dimension reduction technique * lsh, a free software implementation of the Secure Shell protocol * LSH is the IATA code for Lashio Airport …   Wikipedia

  • LSH — steht für: Landschulheim am Solling, ein staatlich anerkanntes und privates Gymnasium und Internat Lysergsäurehydroxyethylamid, ein Mutterkornalkaloid das in einigen Pilzen und Windengewächsen vorkommt lsh steht für: lsh, eine Freie Software… …   Deutsch Wikipedia

  • Lsh — Infobox Software name = lsh caption = developer = Niels Möller latest release version = v2.0.4 latest release date = release date|2007|09|05 operating system = Unix like genre = Networking, Security license = GPL website =… …   Wikipedia

  • LSH — Landing Ship Hospital (Governmental » Military) *** Live in fear. Save a race. Howl at the moon. (Miscellaneous » Science Fiction) ** Local And State History (Academic & Science » Universities) ** Local And State History (Governmental » US… …   Abbreviations dictionary

  • LSH PA — LaSalle Real Estate Holdings, LTD. Preferred A (Business » NYSE Symbols) …   Abbreviations dictionary

  • LSH — laparoscopic supracervical hysterectomy; lutein stimulating hormone; lymphocyte stimulating hormone …   Medical dictionary

  • lsh — ISO 639 3 Code of Language ISO 639 2/B Code : ISO 639 2/T Code : ISO 639 1 Code : Scope : Individual Language Type : Living Language Name : Lish …   Names of Languages ISO 639-3

  • LSH — Least Significant Half Contributor: GSFC …   NASA Acronyms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”