Lower bounds on locality sensitive hashing

Rajeev Motwani, Assaf Naor, Rina Panigrahy

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


Given a metric space (X, dx), c ≥ 1, r > 0, and p,q ∈ [0, 1], a distribution over mappings ℋ : X → N is called a (r, cr, p, o)-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 ℋ 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 p 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 languageAmerican English
Pages (from-to)930-935
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Issue number4
StatePublished - 2007
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics


  • Locality sensitive hashing
  • Lower bounds
  • Nearest neighbor search


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

Cite this