Recherche efficace de voisins les plus proches approximatifs dans des espaces de haute dimension

Nous abordons le problème de la conception de structures de données permettant une recherche efficace des voisins les plus proches approximatifs. Plus spécifiquement, étant donné une base de données composée d'un ensemble de vecteurs dans un certain espace euclidien de haute dimension, nous souhaitons construire une structure de données économiquement efficace, qui nous permettrait de rechercher, étant donné un vecteur de requête, le vecteur le plus proche ou presque le plus proche dans la base de données. Nous abordons également ce problème lorsque les distances sont mesurées par la norme L1, et dans le cube de Hamming. Améliorant et étendant de manière significative les résultats récents de Kleinberg, nous construisons des structures de données dont la taille est polynomiale par rapport à la taille de la base de données, et des algorithmes de recherche qui s'exécutent en un temps presque linéaire ou presque quadratique en fonction de la dimension (selon le cas ; les facteurs supplémentaires sont polylogarithmiques par rapport à la taille de la base de données). 1 Introduction Motivation.