En informatique, une structure de données est une manière d’organiser les données en un modèle interne qui permet de les traiter plus facilement. Un exemple important est celui de la recherche de plus proches voisins. Si P est un ensemble fini donné de points et x un point de requête, on veut déterminer le point de P le plus proche de x. On peut bien sûr examiner tous les points de P un à un et retenir celui qui est le plus proche de x mais on peut faire beaucoup mieux. Par exemple, si les points de P sont dans le plan euclidien, on peut construire le diagramme de Voronoï de P. La recherche du plus proche voisin de x se ramène alors à localiser x dans le diagramme, ce qu’on peut faire en temps logarithmique et non pas linéaire.
En dimensions supérieures à 2, le problème est beaucoup plus difficile et, pour être efficaces, les algorithmes de recherche de plus proches voisins doivent se contenter de fournir des solutions approchées. Par ailleurs, on peut se contenter de n’avoir la solution qu’avec une bonne probabilité. Les algorithmes probabilistes s’avèrent alors une nouvelle fois très efficaces. Le cours présente différentes partitions de l’espace ambiant et montre comment tirer parti de la dimension intrinsèque de l’ensemble P. On présente également la technique LSH (local sensitive hashing) qui est actuellement la meilleure technique de recherche de voisins en grandes dimensions.
