Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
Authors:
- Yannis KalantidisYKYannis Kalantidis
- Yannis AvrithisYAYannis Avrithis
- 1 June 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 2329-2336
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.Keywords
This publication has 15 references indexed in Scilit:
- Joint Inverted Indexing2013
- Quantize and Conquer: A Dimensionality-Recursive Solution to Clustering, Vector Quantization, and Image Retrieval2013
- Cartesian K-Means2013
- K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes2013
- The inverted multi-index2012
- Fast search in Hamming space with multi-index hashing2012
- Iterative quantization: A procrustean approach to learning binary codes2011
- Searching in one billion vectors: Re-rank with source coding2011
- Locality sensitive hashing: A comparison of hash function types and querying mechanismsPattern Recognition Letters, 2010
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010