  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}$.
