Cet article s'intéresse à l'accélération de la recherche par similarité dans les espaces à grande dimension. Les méthodes exactes de recherche de tous les plus proches voisins d'un point requête ont des performances qui se dégradent avec la dimension de l'espace (malédiction de la dimension). D'où l'éclosion cette dernière décennie de solutions alternatives pour accélérer la recherche par similarité. Après avoir dressé un panorama de nouvelles solutions, classées en trois catégories, nous proposons et évaluons trois nouvelles approches permettant d'accélérer la recherche des plus proches voisins selon la classification présentée : nous proposons d'abord une approche progressive exacte appelée HiPeR, indépendante des données et de l'index, que nous illustrons avec l'index VA-file. Ensuite nous étudions l'adaptation d'HiPeR à la recherche approximative en utilisant un modèle probabiliste de contrôle de la précision. Enfin nous présentons des stratégies de traitement efficace des requêtes multiples avec application aux index arborescents ainsi qu'à HiPeR.