Query-Adaptative Locality Sensitive Hashing

Hervé Jégou 1 Laurent Amsaleg 2 Cordelia Schmid 1 Patrick Gros 2
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
2 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : It is well known that high-dimensional nearest-neighbor retrieval is very expensive. Many signal processing methods suffer from this computing cost. Dramatic performance gains can be obtained by using approximate search, such as the popular Locality-Sensitive Hashing. This paper improves LSH by performing an on-line selection of the most appropriate hash functions from a pool of functions. An additional improvement originates from the use of $E_8$ lattices for geometric hashing instead of one-dimensional random projections. A performance study based on state-of-the-art high-dimensional descriptors computed on real images shows that our improvements to LSH greatly reduce the search complexity for a given level of accuracy.
Type de document :
Communication dans un congrès
ICASSP 2008 - IEEE International Conference on Acoustics, Speech, and Signal Processing, Mar 2008, Las Vegas, United States. IEEE, pp.825-828, 2008, 〈10.1109/ICASSP.2008.4517737〉
Liste complète des métadonnées

qalsh.png
qalsh.png
https://hal.inria.fr/inria-00318614
Contributeur : Hervé Jégou <>
Soumis le : mardi 15 mars 2011 - 14:51:35
Dernière modification le : mercredi 11 avril 2018 - 01:58:22
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 11:45:18

Fichiers

qalsh.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | IRISA | UGA | LJK_GI_LEAR | LJK_GI | LJK | IRISA-D6 | UR1-UFR-ISTIC | UNIV-RENNES | INRIA-RENGRE

Citation

Hervé Jégou, Laurent Amsaleg, Cordelia Schmid, Patrick Gros. Query-Adaptative Locality Sensitive Hashing. ICASSP 2008 - IEEE International Conference on Acoustics, Speech, and Signal Processing, Mar 2008, Las Vegas, United States. IEEE, pp.825-828, 2008, 〈10.1109/ICASSP.2008.4517737〉. 〈inria-00318614〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

592

Téléchargements de fichiers

672

Contact


archive-ouverte@inria.fr