TY - GEN
T1 - Lower bounds on locality sensitive hashing
AU - Motwani, Rajeev
AU - Naor, Assaf
AU - Panigrahy, Rina
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
KW - Locality Sensitive Hashing
KW - Lower Bounds
KW - Nearest Neighbor Search
UR - http://www.scopus.com/inward/record.url?scp=33748088520&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748088520&partnerID=8YFLogxK
U2 - 10.1145/1137856.1137881
DO - 10.1145/1137856.1137881
M3 - Conference contribution
AN - SCOPUS:33748088520
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 154
EP - 157
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PB - Association for Computing Machinery
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -