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

Hervé Jégou 1 Matthijs Douze 1 Cordelia Schmid 1
1 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 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.
Type de document :
Rapport
[Research Report] RR-7020, INRIA. 2009, pp.25
Liste complète des métadonnées



https://hal.inria.fr/inria-00410767
Contributeur : Hervé Jégou <>
Soumis le : lundi 24 août 2009 - 12:57:37
Dernière modification le : samedi 17 septembre 2016 - 01:36:38
Document(s) archivé(s) le : lundi 15 octobre 2012 - 16:21:05

Fichiers

RR-7020.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00410767, version 1

Collections

Citation

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>

Partager

Métriques

Consultations de
la notice

1049

Téléchargements du document

882