Lower bounds on locality sensitive hashing

Rajeev Motwani, Assaf Naor, Rina Panigrahy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations

Abstract

Given a metric space (X, dX), c ≥ 1, r > 0, and p,q ∈ [0,1], a distribution over mappings ℋ: X → ℕ is called a (r,cr,p,g)-sensitive hash family if any two points in X at distance at most r are mapped by ℋ to the same value with probability at least p, and any two points at distance greater than cr are mapped by ℋ to the same value with probability at most q. This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm, and has since been used extensively for this purpose. The performance of these algorithms is governed by the parameter ρ = log(1/p)/log(1/q), and constructing hash families with small ρ automatically yields improved nearest neighbor algorithms. Here we show that for X = ℓ1 it is impossible to achieve ρ ≤ 1/2c. This almost matches the construction of Indyk and Motwani which achieves ρ ≤ 1/c.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery
Pages154-157
Number of pages4
ISBN (Print)1595933409, 9781595933409
DOIs
StatePublished - 2006
Externally publishedYes
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
Volume2006

Other

Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
CountryUnited States
CitySedona, AZ
Period6/5/066/7/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • Locality Sensitive Hashing
  • Lower Bounds
  • Nearest Neighbor Search

Fingerprint Dive into the research topics of 'Lower bounds on locality sensitive hashing'. Together they form a unique fingerprint.

  • Cite this

    Motwani, R., Naor, A., & Panigrahy, R. (2006). Lower bounds on locality sensitive hashing. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 154-157). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery. https://doi.org/10.1145/1137856.1137881