Polysemous Codes

Abstract

This paper considers the problem of approximate nearest neighbor search in the compressed domain. We introduce polysemous codes, which offer both the distance estimation quality of product quantization and the efficient comparison of binary codes with Hamming distance. Their design is inspired by algorithms introduced in the 90's to construct channel-optimized vector quantizers. At search time, this dual interpretation accelerates the search. Most of the indexed vectors are filtered out with Hamming distance, letting only a fraction of the vectors to be ranked with an asymmetric distance estimator. The method is complementary with a coarse partitioning of the feature space such as the inverted multi-index. This is shown by our experiments performed on several public benchmarks such as the BIGANN dataset comprising one billion vectors, for which we report state-of-the-art results for query times below 0.3\,millisecond per core. Last but not least, our approach allows the approximate c

Stats

• citations33
• S2 citations—
• github stars0
• HF likes0
• heat score11.49
• arxiv keydouze2016polysemous

Related papers

• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Lossless Compression Of Vector Ids For Approximate Nearest Neighbor Search (2025)11.11
• Sparse Ternary Codes For Similarity Search Have Higher Coding Gain Than Dense Binary Codes (2017)7.50
• Fast Search On Binary Codes By Weighted Hamming Distance (2020)0.00
• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
• Qinco2: Vector Compression And Search With Improved Implicit Neural Codebooks (2025)0.00
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00