Stacked Quantizers for Compositional Vector Compression

Abstract

Recently, Babenko and Lempitsky introduced Additive Quantization (AQ), a generalization of Product Quantization (PQ) where a non-independent set of codebooks is used to compress vectors into small binary codes. Unfortunately, under this scheme encoding cannot be done independently in each codebook, and optimal encoding is an NP-hard problem. In this paper, we observe that PQ and AQ are both compositional quantizers that lie on the extremes of the codebook dependence-independence assumption, and explore an intermediate approach that exploits a hierarchical structure in the codebooks. This results in a method that achieves quantization error on par with or lower than AQ, while being several orders of magnitude faster. We perform a complexity analysis of PQ, AQ and our method, and evaluate our approach on standard benchmarks of SIFT and GIST descriptors, as well as on new datasets of features obtained from state-of-the-art convolutional neural networks.

References in corpus (3)

• Return of the Devil in the Details: Delving Deep into Convolutional Nets
• Visualizing and Understanding Convolutional Networks
• Efficient On-the-fly Category Retrieval using ConvNets and GPUs

Cited by in corpus (7)

• Beyond Product Quantization: Deep Progressive Quantization for Image Retrieval
• Deep Recurrent Quantization for Generating Sequential Binary Codes
• Bolt: Accelerated Data Mining with Fast Vector Compression
• Efficient Inner Product Approximation in Hybrid Spaces
• Approximate k-NN Graph Construction: a Generic Online Approach
• Asymmetric Correlation Quantization Hashing for Cross-modal Retrieval
• Low-Precision Quantization for Efficient Nearest Neighbor Search