La découverte d'informations cachées dans les bases de données multimédias est une tâche difficile à cause de leur structure complexe et à la subjectivité liée à leur interprétation. Face à cette situation, l'utilisation d'un index est primordiale. Un index multimédia permet de regrouper les données selon des critères de similarité. Nous proposons dans cet article d'apporter une amélioration à une approche déjà existante d'interrogation d'images par le contenu . Nous proposons une méthode efficace pour mettre à jour, localement, les graphes de voisinage qui constituent notre structure d'index multimédia. Cette méthode est basée sur une manière intelligente de localisation de points dans un espace multidimensionnel. Des résultats prometteurs sont obtenus après des expérimentations sur diverses bases de données.