Product Quantization for Nearest Neighbor Search
Top Cited Papers
- 18 March 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 33 (1) , 117-128
- https://doi.org/10.1109/tpami.2010.57
Abstract
This paper introduces a product quantization-based approach for approximate nearest neighbor search. The idea is to decompose the space into a Cartesian product of low-dimensional subspaces and to quantize each subspace separately. A vector is represented by a short code composed of its subspace quantization indices. The euclidean distance between two vectors can be efficiently estimated from their codes. An asymmetric version increases precision, as it computes the approximate distance between a vector and a code. Experimental results show that our approach searches for nearest neighbors efficiently, in particular in combination with an inverted file system. Results for SIFT and GIST image descriptors show excellent search accuracy, outperforming three state-of-the-art approaches. The scalability of our approach is validated on a data set of two billion vectors.Keywords
This publication has 21 references indexed in Scilit:
- 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene RecognitionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Object retrieval with large vocabularies and fast spatial matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Scalable Recognition with a Vocabulary TreePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Minimum Sum-Squared Residue Co-clustering of Gene Expression DataPublished by Society for Industrial & Applied Mathematics (SIAM) ,2004
- Video Google: a text retrieval approach to object matching in videosPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- When Is “Nearest Neighbor” Meaningful?Published by Springer Nature ,1999
- QuantizationIEEE Transactions on Information Theory, 1998
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977