Locally Optimized Product Quantization for Approximate Nearest Neighbor Search

Yannis Kalantidis, Yannis Avrithis; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014, pp. 2321-2328

Abstract


We present a simple vector quantizer that combines low distortion with fast search and apply it to approximate nearest neighbor (ANN) search in high dimensional spaces. Leveraging the very same data structure that is used to provide 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. Local optimization is over rotation and space decomposition; interestingly, we apply a parametric solution that assumes a normal distribution and is extremely fast to train. With a reasonable space and time overhead that is constant in the data size, we set a new state-of-the-art on several public datasets, including a billion-scale one.

Related Material


[pdf]
[bibtex]
@InProceedings{Kalantidis_2014_CVPR,
author = {Kalantidis, Yannis and Avrithis, Yannis},
title = {Locally Optimized Product Quantization for Approximate Nearest Neighbor Search},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2014}
}