Chapter 1
What is E
2
LSH?
Short answer:
E
2
LSH (Exact Euclidean LSH) is a package that provides a randomized solution for the high-dimensional
near neighbor problem in the Euclidean space l
2
. After preprocessing the data set, E
2
LSH answers queries,
typically in sublinear time, with each near neighbor being reported with a certain probability. E
2
LSH is
based on the Locality Sensitive Hashing (LSH) scheme described in [2].
Long answer:
The R-near neighbor problem is defined as follows. Given a set of points P ⊂
R
d
and a radius R > 0,
construct a data structure that answers the following queries: for a query point q, find all points p ∈ P
such that ||q − p||
2
≤ R, where ||q − p||
2
is the Euclidean distance between q and p. E
2
LSH solves a
randomized version of this problem, which we call a (R, 1 − δ)-near neighbor problem. In this case, each
point p satisfying ||q −p||
2
≤ R has to be reported with a probability at least 1−δ (thus, δ is the probability
that a near neighbor p is not reported).
E
2
LSH can be also used to solve the nearest neighbor problem, where, given the query q, the data
structure is required the report the point in P that is closest to q. This can be done by creating several R-near
neighbor data structures, for R = R
1
, R
2
, . . . R
t
, where R
t
should be greater than the maximum distance
from any query point to its nearest neighbor. The nearest neighbor can be then recovered by querying the
data structures in the increasing order of the radiae, stopping whenever the first point is found.
E
2
LSH is based on locality-sensitive hashing (LSH) scheme, as described in [2]. The original locality-
sensitive hashing scheme solves the approximate version of the R-near neighbor problem, called a (R, c)-
near neighbor problem. In that formulation, it is sufficient to report any point within the distance of at most
cR from the query q, if there is a point in P at distance at most R from q (with a constant probability). For
the approximate formulation, the LSH scheme achieves a time of O(n
ρ
), where ρ < 1/c.
To solve the (R, 1 − δ) formulation, E
2
LSH uses the basic LSH scheme to get all near neighbors (in-
cluding the approximate ones), and then drops the approximate near neighbors. Thus, the running time of
E
2
LSH depends on the data set P. In particular, E
2
LSH is slower for “bad” data sets, e.g., when for a query
q, there are many points from P clustered right outside the ball of radius R centered at q (i.e., when there
are many approximate near neighbors).
E
2
LSH is also different from the original LSH scheme in that E
2
LSH empirically estimates the optimal
parameters for the data structure, as opposed to using theoretical formulas. This is because theoretical
formulas are geared towards the worst case point sets, and therefore they are less adequate for the real data
2
