Quicker ADC : Unlocking the Hidden Potential of Product Quantization With SIMD

Area of Science:

• Computer Science
• Information Retrieval
• Machine Learning

Background:

• Nearest Neighbor (NN) search in high-dimensional spaces is crucial for multimedia retrieval.
• Product Quantization (PQ) enables efficient storage and distance computation for large vector databases.
• Existing PQ implementations are often limited by memory access bottlenecks.

Purpose of the Study:

• To introduce Quicker ADC, a generalization of Quick ADC for faster nearest neighbor search.
• To overcome challenges in efficiently handling non-byte-aligned bit shuffles (5, 6, and 7 bits) in AVX-512.
• To improve the performance of PQ-based nearest neighbor search in high-dimensional vector databases.

Main Methods:

• Developed Quicker ADC, supporting AVX-512 and generalized PQ codes beyond PQ m×4.
• Introduced irregular product quantizers with varying sub-quantizer granularities.
• Implemented split tables to accommodate lookup tables larger than CPU registers.

Main Results:

• Quicker ADC demonstrated superior performance compared to optimized implementations like FAISS and polysemous codes.
• Evaluated Quicker ADC on multiple index structures, including Inverted Multi-Indexes and IVF HNSW.
• Achieved significant speedups, outperforming existing optimized solutions in numerous configurations.

Conclusions:

• Quicker ADC offers a substantial performance improvement for nearest neighbor search using Product Quantization.
• The techniques developed, including irregular quantizers and split tables, effectively address challenges with non-byte-aligned bit manipulations.
• An open-source fork of FAISS incorporating Quicker ADC is released, promoting wider adoption and further research.