Product Quantization for Nearest Neighbor Search

Hervé Jégou 1, * Matthijs Douze 2 Cordelia Schmid 2
* Corresponding author
1 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : We propose an approximate nearest neighbor search method based on product quantization, which decomposes the space into a Cartesian product of low dimensional subspaces and quantizes each subspace separately. A vector is represented by a short code corresponding to the quantization index. The Euclidean distance between two vectors can be efficiently estimated from their codes. Our method has an advantageous asymmetric version, where an estimated distance is computed between a vector and a code. Our approach is used to search for nearest neighbors efficiently, in particular in combination with an inverted file system. Experiments performed on 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 dataset of two billion vectors.
Keywords : Sorting and searching Computer vision Representations data structures transforms
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

voronoiasytmp.jpg
voronoiasytmp.jpg
https://hal.inria.fr/inria-00514462
Contributor : Hervé Jégou <>
Submitted on : Wednesday, May 22, 2013 - 10:07:34 PM
Last modification on : Monday, December 17, 2018 - 11:22:02 AM
Long-term archiving on: Tuesday, April 4, 2017 - 10:22:20 AM

Files

jegou_pq_postprint.pdf
Files produced by the author(s)

Identifiers

Collections

UNIV-RENNES1 | CNRS | INRIA | IRISA | LJK | LJK_GI_LEAR | LJK_GI | UGA | IRISA-D6 | UR1-UFR-ISTIC | UNIV-RENNES | INSA-GROUPE

Citation

Hervé Jégou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2011, 33 (1), pp.117-128. ⟨10.1109/TPAMI.2010.57⟩. ⟨inria-00514462v2⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

3697

Files downloads

17379

 

 

Contact

archive-ouverte@inria.fr