Additive Quantization for Extreme Vector Compression

Authors:
  • ABArtem Babenko
    Artem Babenko
  • VLVictor Lempitsky
    Victor Lempitsky
Top Cited Papers
Publisher website
Google Scholar
Abstract
We introduce a new compression scheme for high-dimensional vectors that approximates the vectors using sums of M codewords coming from M different codebooks. We show that the proposed scheme permits efficient distance and scalar product computations between compressed and uncompressed vectors. We further suggest vector encoding and codebook learning algorithms that can minimize the coding error within the proposed scheme. In the experiments, we demonstrate that the proposed compression can be used instead of or together with product quantization. Compared to product quantization and its optimized versions, the proposed compression approach leads to lower coding approximation errors, higher accuracy of approximate nearest neighbor search in the datasets of visual descriptors, and lower image classification error, whenever the classifiers are learned on or applied to compressed vectors.

This publication has 14 references indexed in Scilit: