Fast Approximate Nearest Neighbor Search with a Dynamic Exploration Graph using Continuous Refinement

• DOI: 10.48550/arxiv.2307.10479
• Publication Date: 2023-01-01
• Authors: Nico Hezel; Kai Uwe Barthel; Konstantin Schall; Klaus Jung
• Keywords: Nearest neighbor graph

For approximate nearest neighbor search, graph-based algorithms have shown to offer the best trade-off between accuracy and search time. We propose Dynamic Exploration Graph (DEG) which significantly outperforms existing in terms of exploration efficiency by combining two new ideas: First, a single undirected even regular graph is incrementally built partially replacing edges integrate vertices update old neighborhoods at same Secondly, an edge optimization algorithm used continuously improve quality graph. Combining this ongoing refinement with construction process leads well-organized structure all times, resulting in: (1) increased efficiency, (2) predictable index size, (3) guaranteed connectivity therefore reachability vertices, (4) dynamic structure. In addition we investigate how well systems can handle indexed queries where seed vertex query itself. Such tasks, despite their good starting point, are not necessarily easy. High (ANNS) does automatically imply performance exploratory search. Extensive experiments show that our for unindexed queries.