| 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. |
[  PDF] [
BibTex] [
Print] [
 Back] |
