Nearest Neighbor Search With Compact Codes: A Decoder Perspective

Abstract

Modern approaches for fast retrieval of similar vectors on billion-scaled datasets rely on compressed-domain approaches such as binary sketches or product quantization. These methods minimize a certain loss, typically the mean squared error or other objective functions tailored to the retrieval problem. In this paper, we re-interpret popular methods such as binary hashing or product quantizers as auto-encoders, and point out that they implicitly make suboptimal assumptions on the form of the decoder. We design backward-compatible decoders that improve the reconstruction of the vectors from the same codes, which translates to a better performance in nearest neighbor search. Our method significantly improves over binary hashing methods or product quantization on popular benchmarks.

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keyamara2021nearest

Related papers

• Polysemous Codes (2016)11.49
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Lossless Compression Of Vector Ids For Approximate Nearest Neighbor Search (2025)11.11
• Qinco2: Vector Compression And Search With Improved Implicit Neural Codebooks (2025)0.00
• Privacy-preserving Near Neighbor Search Via Sparse Coding With Ambiguation (2021)3.58
• Sparse Ternary Codes For Similarity Search Have Higher Coding Gain Than Dense Binary Codes (2017)7.50
• Compact Hash Codes For Efficient Visual Descriptors Retrieval In Large Scale Databases (2016)11.76
• 2-bit Random Projections, Nonlinear Estimators, And Approximate Near Neighbor Search (2016)0.00