La recherche efficace de voisinage dans un espace multidimensionnel a été étudiée dans plusieurs domaines tels que la reconnaissance de formes et l'exploration de données. Les graphes de voisinage sont des structures géométriques basées sur le concept de proximité des éléments de données, et ils peuvent être utilisés pour déterminer les plus proches voisins de données multidimensionnelles. Le problème est que, outre la construction couteuse de ces graphes, leur mise à jour est aussi difficile en raison de l'insertion ou la suppression d'un élément. Dans cet article nous proposons d'adapter les graphes de voisinage pour l'indexation de plus grandes quantités de données multidimensionnelles. Nous proposons une modification d'une méthode existante de mise à jour locale de graphes de voisinage de telle sorte à ce qu'elle puisse considérer des accès réduits aux disques afin de prendre en compte l'évolution des bases de données. Cette proposition est étendue pour faire de la construction incrémentale de graphes de voisinage. Des évaluations de l'approche ont été effectuées et les résultats montrent que notre approche est prometteuse.