Query-Adaptative Locality Sensitive Hashing

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 E8 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.

@InProceedings{JASG08,
  author       = "Herv\'e J\'egou and Laurent Amsaleg and Cordelia Schmid and Patrick Gros",
  title        = "Query-Adaptative Locality Sensitive Hashing",
  booktitle    = "International Conference on Acoustics, Speech, and Signal Processing",
  month        = "apr",
  year         = "2008",
  publisher    = "IEEE",
  keywords     = "LEAR",
  url          = "http://lear.inrialpes.fr/pubs/2008/JASG08"
}