Searching with quantization: approximate nearest neighbor search using short codes and distance estimators - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Searching with quantization: approximate nearest neighbor search using short codes and distance estimators

Hervé Jégou
  • Fonction : Auteur
  • PersonId : 833473
Matthijs Douze
  • Fonction : Auteur
  • PersonId : 843109
Cordelia Schmid
  • Fonction : Auteur
  • PersonId : 831154

Résumé

We propose an approximate nearest neighbor search method based on quantization. It uses, in particular, product quantizer to produce short codes and corresponding distance estimators approximating the Euclidean distance between the orginal vectors. The method is advantageously used in an asymmetric manner, by computing the distance between a vector and code, unlike competing techniques such as spectral hashing that only compare codes. Our approach approximates the Euclidean distance based on memory efficient codes and, thus, permits efficient nearest neighbor search. Experiments performed on SIFT and GIST image descriptors show excellent search accuracy. The method is shown to outperform two state-of-the-art approaches of the literature. Timings measured when searching a vector set of 2 billion vectors are shown to be excellent given the high accuracy of the method.
Fichier principal
Vignette du fichier
RR-7020.pdf (500.44 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-00410767 , version 1 (24-08-2009)

Identifiants

  • HAL Id : inria-00410767 , version 1

Citer

Hervé Jégou, Matthijs Douze, Cordelia Schmid. Searching with quantization: approximate nearest neighbor search using short codes and distance estimators. [Research Report] RR-7020, INRIA. 2009, pp.25. ⟨inria-00410767⟩
976 Consultations
1264 Téléchargements

Partager

Gmail Facebook X LinkedIn More