Lower bounds on Locality Sensitive Hashing

Details Lower bounds on Locality Sensitive Hashing Lower bounds on Locality Sensitive Hashing

2005-10-29

arxiv.org/abs/cs/0510088v2

Computer Science

Computational Geometry

Scientific paper

Given a metric space $(X,d_X)$, $c\ge 1$, $r>0$, and $p,q\in [0,1]$, a distribution over mappings $\h:X\to \mathbb 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 $\rho=\frac{\log(1/p)}{\log(1/q)}$, and constructing hash families with small $\rho$ automatically yields improved nearest neighbor algorithms. Here we show that for $X=\ell_1$ it is impossible to achieve $\rho\le \frac{1}{2c}$. This almost matches the construction of Indyk and Motwani which achieves $\rho\le \frac{1}{c}$.

Affiliated with

Also associated with

No associations

Rating

Lower bounds on Locality Sensitive Hashing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower bounds on Locality Sensitive Hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds on Locality Sensitive Hashing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-545642