Routing-guided Learned Product Quantization For Graph-based Approximate Nearest Neighbor Search

Abstract

Given a vector dataset \(\mathcal\{X\}\), a query vector \(\vec\{x\}_q\), graph-based Approximate Nearest Neighbor Search (ANNS) aims to build a proximity graph (PG) as an index of \(\mathcal\{X\}\) and approximately return vectors with minimum distances to \(\vec\{x\}_q\) by searching over the PG index. It suffers from the large-scale \(\mathcal\{X\}\) because a PG with full vectors is too large to fit into the memory, e.g., a billion-scale \(\mathcal\{X\}\) in 128 dimensions would consume nearly 600 GB memory. To solve this, Product Quantization (PQ) integrated graph-based ANNS is proposed to reduce the memory usage, using smaller compact codes of quantized vectors in memory instead of the large original vectors. Existing PQ methods do not consider the important routing features of PG, resulting in low-quality quantized vectors that affect the ANNS's effectiveness. In this paper, we present an end-to-end Routing-guided learned Product Quantization (RPQ) for graph-based ANNS. It consi

Stats

• citations3
• S2 citations—
• github stars0
• HF likes0
• heat score4.52
• arxiv keyyue2023routing

Related papers

• Diskann++: Efficient Page-based Search Over Isomorphic Mapped Graph Index Using Query-sensitivity Entry Vertex (2023)0.00
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00
• Online Product Quantization (2017)10.61
• Rabitq: Quantizing High-dimensional Vectors With A Theoretical Error Bound For Approximate Nearest Neighbor Search (2024)12.54
• Probabilistic Routing For Graph-based Approximate Nearest Neighbor Search (2024)0.00
• SAQ: Pushing The Limits Of Vector Quantization Through Code Adjustment And Dimension Segmentation (2025)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00