Constructing Parameter-Optimal Graph ANNS Index with GArena
作者: Puqing Wu, Minhui Xie, Hao Guo, Jie Yin, Sen Yang, Youyou Lu, Yunpeng Chai
2026-03摘要: Graph-based Approximate Nearest Neighbor Search (GANNS) delivers exceptional query performance compared to other algorithms, but this efficiency comes at the cost of significantly longer construction time. Because index construction parameters can alter final query throughput by up to an order of magnitude, identifying the parameter-optimal configuration is essential for real-world deployments. Yet, this process is notoriously challenging: traditional tuning methods can take days or weeks due to the need for repeated, full graph rebuilds. This paper introduces GArena, a GANNS constructor that accelerates optimal construct parameter search. Our key observation is that while different parameter settings yield distinct graph topologies, their construction processes exhibit over 70% redundancy in distance calculations. Though a naive distance cache can eliminate this redundancy, it incurs prohibitive memory overhead (dozens of TB). Instead, GArena redesigns the tuning paradigm by launching multiple parallel graphs with different configurations and aligning their distance computation trajectories, thereby greatly enhancing the distance cache’s temporal locality. GArena can bound the cache size to only a few MB (fully resident in CPU cache). GArena also introduces a performance-potentialguided pruner to discard unpromising configurations early on small subsets. Evaluation shows that GArena can dramatically shrink the tuning process from a day down to minutes, while consistently identifying the optimal configuration.