Lower bounds on locality sensitive hashing

ABSTRACT

Given a metric space (X,d_X), c≥1, r>0, and p,q ≡ [0,1], a distribution over mappings H : X → N is called a (r,cr,p,q)-sensitive hash family if any two points in X at distance at most r are mapped by H to the same value with probability at least p, and any two points at distance greater than cr are mapped by H 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=l₁ it is impossible to achieve ⊇ ≤ 1/2c. This almost matches the construction of Indyk and Motwani which achieves ⊇ ≤ 1/c.

REFERENCES

• 1: A. Andoni and P. Indyk. Faster algorithms for high dimensional nearest neighbor problems. Manuscript, 2005.
• 2: W. Beckner. Inequalities in Fourier analysis. Ann. of Math. (2), 102(1):159--182, 1975.
• 3: A. Bonami. Étude des coefficients de Fourier des fonctions de Lp(G). Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335--402 (1971), 1970.
• 4: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 5: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 6: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 7: Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109688]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Theory

Keywords:
locality sensitive hashing, lower bounds, nearest neighbor search