Product Quantization for Nearest Neighbor Search - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Pattern Analysis and Machine Intelligence Année : 2011

Product Quantization for Nearest Neighbor Search

Matthijs Douze
  • Fonction : Auteur
  • PersonId : 843109
Cordelia Schmid
  • Fonction : Auteur
  • PersonId : 831154

Résumé

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.
Fichier principal
Vignette du fichier
jegou_pq_postprint.pdf (551.49 Ko) Télécharger le fichier
Vignette du fichier
voronoiasytmp.jpg (31.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

inria-00514462 , version 1 (23-03-2011)
inria-00514462 , version 2 (22-05-2013)

Identifiants

Citer

Hervé Jégou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33 (1), pp.117-128. ⟨10.1109/TPAMI.2010.57⟩. ⟨inria-00514462v2⟩
4020 Consultations
43366 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More