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... Une famille LSH est définie pour un espace métrique , un seuil et un facteur d'approximation En pratique, on a souvent . est une famille de fonctions satisfaisant les conditions suivantes pour deux points quelconques , et une fonction choisie aléatoirement parmi la famille : si , alors si , alors Par construction, les fonctions de hachage doivent permettre aux points proches d'entrer fréquemment en collision (i.e. ) et inversement, les points éloignés ne doivent entrer que rarement en collision. Pour que la famille LSH soit intéressante, il faut donc . La famille est alors appelée -sensitive. La famille est d'autant plus intéressante si est très supérieure à . Une définition alternative est définie par rapport à un univers possédant une fonction de similarité . Une famille LSH est alors un ensemble de fonctions de hachage et une distribution de probabilité sur les fonctions, telle qu'une fonction choisie selon satisfait la propriété pour tout . LSH a été appliqué dans plusieurs domaines, en particulier pour la , la comparaison de sequence d'ADN, la recherche par similarité de documents audios. L'échantillonnage de bit 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 , i.e. quand un point de l'espace appartient à . La famille de fonctions de hachage est alors l'ensemble des projections sur une des coordonnées, i.e., , où est la i coordonnée de .