Query-Adaptative Locality Sensitive Hashing

Hervé Jégou; Laurent Amsaleg; Cordelia Schmid; Patrick Gros

Query-Adaptative Locality Sensitive Hashing

Hervé Jégou ¹ Laurent Amsaleg ² Cordelia Schmid ¹ Patrick Gros ²

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.

Document type :

Conference papers

Domain :

Computer Science [cs] / Information Retrieval [cs.IR]

Complete list of metadatas

https://hal.inria.fr/inria-00318614
Contributor : Hervé Jégou <>
Submitted on : Tuesday, March 15, 2011 - 2:51:35 PM
Last modification on : Monday, December 17, 2018 - 11:22:02 AM
Long-term archiving on : Thursday, November 8, 2012 - 11:45:18 AM

qalsh.pdf

Files produced by the author(s)

icassp_qalsh_talk.pdf Files produced by the author(s)

Query-Adaptative Locality Sensitive Hashing

Files

Identifiers

Collections

Citation

Export

Metrics

736

1127

Contact

Query-Adaptative Locality Sensitive Hashing

Files

Identifiers

Collections

Citation

Export

Share

Metrics

736

1127

Contact