Interleaved Composite Quantization For High-dimensional Similarity Search

Abstract

Similarity search retrieves the nearest neighbors of a query vector from a dataset of high-dimensional vectors. As the size of the dataset grows, the cost of performing the distance computations needed to implement a query can become prohibitive. A method often used to reduce this computational cost is quantization of the vector space and location-based encoding of the dataset vectors. These encodings can be used during query processing to find approximate nearest neighbors of the query point quickly. Search speed can be improved by using shorter codes, but shorter codes have higher quantization error, leading to degraded precision. In this work, we propose the Interleaved Composite Quantization (ICQ) which achieves fast similarity search without using shorter codes. In ICQ, a small subset of the code is used to approximate the distances, with complete codes being used only when necessary. Our method effectively reduces both code length and quantization error. Furthermore, ICQ is compa

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykhoram2019interleaved

Related papers

• Central Similarity Quantization For Efficient Image And Video Retrieval (2019)23.49
• Lossless Compression Of Vector Ids For Approximate Nearest Neighbor Search (2025)11.11
• Polysemous Codes (2016)11.49
• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00
• Qinco2: Vector Compression And Search With Improved Implicit Neural Codebooks (2025)0.00
• Simultaneous Compression And Quantization: A Joint Approach For Efficient Unsupervised Hashing (2018)7.50
• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82