Abstract

We present a simple vector quantizer that combines lowdistortion with fast search and apply it to approximate near-est neighbor (ANN) search in high dimensional spaces.Leveraging the very same data structure that is used to pro-vide non-exhaustive search, i.e., inverted lists or a multi-index, the idea is to locally optimize an individual product quantizer (PQ) per cell and use it to encode residuals. Lo-cal optimization is over rotation and space decomposition;interestingly, we apply a parametric solution that assumesa normal distribution and is extremely fast to train. Witha reasonable space and time overhead that is constant inthe data size, we set a new state-of-the-art on several publicdatasets, including a billion-scale one.