Title: LSH on the Hypercube Revisited,
Abstract: LSH (locality sensitive hashing) had emerged as a powerful technique in
nearest-neighbor search in high dimensions [IM98, HIM12]. Given a point set $P$
in a metric space, and given parameters $r$ and $\varepsilon > 0$, the task is
to preprocess the point set, such that given a query point $q$, one can quickly
decide if $q$ is in distance at most $\leq r$ or $\geq (1+\varepsilon)r$ from
the point set $P$. Once such a near-neighbor data-structure is available, one
can reduce the general nearest-neighbor search to logarithmic number of queries
in such structures [IM98, Har01, HIM12].
In this note, we revisit the most basic settings, where $P$ is a set of
points in the binary hypercube $\{0,1\}^d$, under the $L_1$/Hamming metric, and
present a short description of the LSH scheme in this case. We emphasize that
there is no new contribution in this note, except (maybe) the presentation
itself, which is inspired by the authors recent work [HM17].