Adapting the Exploration Graph for High Throughput in Low Recall Regimes

Nearest neighbor search is vital for modern search systems, particularly in high-dimensional spaces. This paper addresses the 2024 SISAP Indexing Challenge, which involves searching a dataset of 100 million 768-dimensional feature vectors under low recall and memory constraints. We explore the trade-offs between navigation and exploration graphs, where the latter is typically better suited for high recall scenarios. To tackle the challenge, we combine the state-of-the-art continuous refining Exploration Graph (crEG) with feature compression techniques. Although compression reduces overall recall accuracy, it significantly improves search speed. Given the challenge's focus on low recall, this trade-off enables crEG to perform efficiently, making it competitive even against navigation graphs traditionally favored in such settings.