IVML  
  about | r&d | publications | courses | people | links
   

Y.Kalantidis,Y.Avrithis
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
International Conference on Computer Vision and Pattern Recognition (CVPR), 2014.
ABSTRACT
We present a simple vector quantizer that combines low distortion 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 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.
01 June , 2014
Y.Kalantidis,Y.Avrithis, "Locally Optimized Product Quantization for Approximate Nearest Neighbor Search", International Conference on Computer Vision and Pattern Recognition (CVPR), 2014.
[ save PDF] [ BibTex] [ Print] [ Back]

© 00 The Image, Video and Multimedia Systems Laboratory - v1.12