Recherche de voisin en grande dimension et {\em clustering\/} sur hyper-cube

\'Etant donn\'es $n$ points de ${\mathbb R^d}$, le probl\`eme du plus proche voisin se formule comme suit~:~quel {\em pre-processing\/} appliquer \`a ces points pour trouver le plus vite possible le plus proche voisin -- selon une m\'etrique euclidienne -- d'un point quelconque\,? Nous pr\'esenterons d'abord deux algorithmes r\'ecents de J.~Kleinberg --~ACM STOC'97 --, qui sont les premiers \`a founir une $\varepsilon$-approximation et une $(\varepsilon,\delta)$-approximation au probl\`eme pr\'ec\'edent avec un temps de requ\^ete non exponentiel en $d$. Nous \'evoquerons ensuite une application potentielle de ces algorithmes \`a un probl\`eme de {\em clustering\/} sur hyper-cube issu de la chimie -- l'hyper-cube de dimension $d$ \'etant simplement l'espace dans lequel une mol\'ecule consid\'er\'ee comme une s\'equence de $d$ fragments mol\'eculaires est repr\'esent\'ee par un point.