SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search

• DOI: 10.1145/3709730
• Publication Date: 2025-02-11T20:45:06Z
• Authors: Yutong Gou; Jianyang Gao; Yuexuan Xu; Cheng Long
• Keywords: Nearest neighbor graph; Best bin first

Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance terms the time-accuracy trade-off. However, they face bottlenecks due to random memory accesses caused by searching process on graph indices and costs computing exact distances guide process. To relieve bottlenecks, recent method named NGT-QG makes an attempt integrating quantization graph. It (1) replicates stores codes vertex's neighbors compactly so that can be accessed sequentially, (2) uses SIMD-based implementation FastScan efficiently estimate based batch for guiding While achieves promising improvements over vanilla methods, it not fully unleashed potential For instance, entails re-ranking step compute at end, which introduces extra accesses; its structure is jointly designed considering in-batch nature FastScan, causes wastes computation searching. In this work, following NGT-QG, we present new SymphonyQG, more symphonious integration (e.g., avoids explicit refines aligned with FastScan). Based extensive experiments real-world datasets, SymphonyQG establishes state-of-the-art trade-off: 95% recall, 1.5x-4.5x QPS compared most competitive baselines 3.5x-17x classical library HNSWlib across all tested datasets. At same time, indexing least 8x faster than NGT-QG.