#  Parameter-free Locality Sensitive Hashing for Spherical Range
Reporting111The research leading to these results has received funding from
the European Research Council under the European Union’s 7th Framework
Programme (FP7/2007-2013) / ERC grant agreement no. 614331.

Thomas D. Ahle  IT University of Copenhagen, Denmark, {thdy, maau,
<EMAIL_ADDRESS>Martin Aumüller  IT University of Copenhagen, Denmark, {thdy,
maau<EMAIL_ADDRESS>and Rasmus Pagh  IT University of Copenhagen, Denmark,
{thdy, maau<EMAIL_ADDRESS>
###### Abstract

We present a data structure for spherical range reporting on a point set $S$,
i.e., reporting all points in $S$ that lie within radius $r$ of a given query
point $q$ (with a small probability of error). Our solution builds upon the
Locality-Sensitive Hashing (LSH) framework of Indyk and Motwani, which
represents the asymptotically best solutions to near neighbor problems in high
dimensions. While traditional LSH data structures have several parameters
whose optimal values depend on the distance distribution from $q$ to the
points of $S$ (and in particular on the number of points to report), our data
structure is essentially parameter-free and only takes as parameter the space
the user is willing to allocate. Nevertheless, its expected query time
basically matches that of an LSH data structure whose parameters have been
optimally chosen for the data and query in question under the given space
constraints. In particular, our data structure provides a smooth trade-off
between hard queries (typically addressed by standard LSH parameter settings)
and easy queries such as those where the number of points to report is a
constant fraction of $S$, or where almost all points in $S$ are far away from
the query point. In contrast, known data structures fix LSH parameters based
on certain parameters of the input alone.

The algorithm has expected query time bounded by $O(t(n/t)^{\rho})$, where $t$
is the number of points to report and $\rho\in(0,1)$ depends on the data
distribution and the strength of the LSH family used. We further present a
parameter-free way of using multi-probing, for LSH families that support it,
and show that for many such families this approach allows us to get expected
query time close to $O(n^{\rho}+t)$, which is the best we can hope to achieve
using LSH. The previously best running time in high dimensions was
$\Omega(tn^{\rho})$, achieved by traditional LSH-based data structures where
parameters are tuned for outputting a single point within distance $r$.
Further, for many data distributions where the intrinsic dimensionality of the
point set close to $q$ is low, we can give improved upper bounds on the
expected query time.

##  1 Introduction

_Range search_ is a central problem in computational geometry [1]. Given a set
$S$ of $n$ points in $\mathbb{R}^{d}$, build a data structure that answers
queries of the following type: Given a region $R$ (from a predefined class of
regions), _count_ or _report_ all points from $S$ that belong to $R$. Examples
for such classes of regions are simplices [25], halfspaces [12], and spheres
[9].

In this paper we place our main focus on the spherical range reporting problem
(SRR): Given a distance parameter $r$ and a point set $S$, build a data
structure that supports the following queries: Given a point $q$, report all
points in $S$ within distance $r$ from $q$. This problem is closely related to
_spherical range counting_ (“return the number of points”) and _spherical
range emptiness_ (“decide whether there is a point at distance at most $r$”).
Solving spherical range searching problems exactly, i.e., for $\varepsilon=0$,
and in time that is truly sublinear in the point set size $n=|S|$ seems to
require space exponential in the dimensionality of the point set $S$. This
phenomenon is an instance of the _curse of dimensionality_ , and is supported
by popular algorithmic hardness conjectures (see [2, 28]).

For this reason, most algorithms for range searching problems involve
approximation of distances: For some approximation parameter $c>1$ we allow
the data structure to only distinguish between distance $\leq r$ and $>cr$,
while points at distance in between can either be reported or not. We refer to
this relaxation as $c$-approximate SRR. Approximate range reporting and
counting problems were for example considered by Arya et al. in [9], by Indyk
in his Ph.D. thesis [19] as “enumerating/counting point locations in equal
balls” and by Andoni in his Ph.D. thesis [3] as “randomized R-near neighbor
reporting”. In low dimensions, tree-based approaches allow us to build
efficient data structures with space usage
$\tilde{O}(n\gamma^{d-1}(1+(c-1)\gamma^{2}))$ and query time
$\tilde{O}(1/((c-1)\gamma)^{d-1})$ for a trade-off parameter
$\gamma\in[1,1/(c-1)]$ for an approximation factor $1<c\leq 2$, see [9]. The
exponential dependency of time and/or space on the dimension makes these
algorithms inefficient in high dimensions.

Our approach uses the _locality-sensitive hashing_ (LSH) framework [20] which
we will introduce in Section 2. Using this technique to solve SRR is not new:
Both Indyk [19] and Andoni [3] described extensions of the general LSH
framework to solve this problem. As we will show, their approaches yield
running times of $\Omega(tn^{\rho})$, where $t$ is the number of elements at
distance at most $cr$ from the query and $\rho\in(0,1)$ is a parameter that
depends on the distance $r$, the approximation factor $c$, and the LSH family
used to build the data structure. When the output size $t$ is large this leads
to running times of $\Omega(n^{1+\rho})$, which is worse than a linear scan!
Indyk [19] also describes a reduction from spherical range counting to the
$(c,r)$-approximate near neighbor problem that asks to report a _single_ point
from the result set of $c$-approximate SRR. The reduction uses
$O(\log^{2}n/(c-1)^{3})$ queries of independently built $(c,r)$-ANN data
structures, giving a running time of $O(n^{\rho}\log^{2}n/(c-1)^{3})$.
Building upon Indyk’s technique, Chazelle et al. [12] proposed a data
structure that solves approximate halfspace range queries on the unit sphere
by applying a dimension reduction technique to Hamming space. All of these
algorithms use a standard LSH index data structure in a black-box fashion. We
propose a data structure that is almost similar to a standard LSH data
structure, but query it in an adaptive way. Our guarantees are probabilistic
in the sense that each close point is with constant probability present in the
output.

Using LSH-based indexes for range reporting means that we get all points
closer than distance $r$ with a certain probability, as well as some fraction
of the points with distance in the range $(r,cr)$. When $c$ is large, this can
have negative consequences for performance: a query could report nearly every
point in the data set, and any performance gained from approximation is lost.
When the approximation factor $c$ is set close to $1$, data structures working
in high dimensions usually need many independent repetitions to find points at
distance $r$. This is another issue with such indexes that makes range
reporting hard: very close points show up in every repetition, and we need to
remove these duplicates.

Figure 1: Three queries at radius $r$ with points $q_{1},q_{2},$ and $q_{3}$
(crosses) in a data set (dots). Dashed circles around the queries show how far
the radius-$r$ sphere can be stretched such that the number of points between
radius $r$ and radius $c_{i}r$ equals the number of points in radius $r$. We
see that queries $q_{1}$ and $q_{3}$ allow for a large stretch, while query
$q_{2}$ has a small stretch.  Naïve LSHSingle-probe (Thm. 2)Multi-probe (Thm.
5)Lower BoundLinear
Scan$n^{0.2}$$n^{0.6}$$n^{\rho}$$n$$n^{0.8}$$n^{0.6}$$n^{0.4}$$n^{0.8}$$n^{1.0}$$n^{1.2}$$n^{1.4}$$t$$W$$0$$\vdots$
Figure 2: Overview of the running time guarantees of the proposed algorithms
“Adaptive Single-probe” and “Adaptive Multi-probe” for collision probabilities
$p_{1}=.8$ and $p_{2}=.6$ in $d$-dimensional Hamming space such that
$\rho\approx.436$. The $x$-axis shows the value of $t$ as a function of $n$,
the $y$-axis shows the expected work $W$, i.e., the expected number of points
the algorithm retrieves from the hash tables. For comparison, we plotted the
target time of $O(n^{\rho}+t)$, the running time $O(tn^{\rho})$ of a naïve LSH
approach, and the running time $O(n)$ of a linear scan.

The natural approach to overcome the difficulties mentioned above is to choose
the approximation factor $c$ such that the cost of duplicated points roughly
equals the cost of dealing with far points. For LSH-based algorithms, many
papers explain an offline approach of finding the “optimal” value of $c$ for a
data set [4, 10, 15] which usually envolves sampling or assumptions on the
data distribution. However, the best value of $c$ depends not only on the data
set, but also on the _query_. This situation is depicted in Figure 1. In this
paper, we provide a query algorithm that adapts to the input and finds a near-
optimal $c$ at query time. We manage to do this in time proportional to the
number of points eventually returned for the optimal parameters, making the
search essentially free.

#### Output-sensitivity.

To illustrate the improvement over standard fixed parameter LSH, we propose
hard data sets for spherical range reporting. In these data sets, we pick
$t-1$ very close points that show up in almost every repetition, one point at
distance $r$, and the remaining points close to distance $cr$. In this case
LSH would need $\Theta(n^{\rho})$ repetitions to retrieve the point at
distance $r$ with constant probability, where e.g. $\rho=1/c$ in Hamming space
[20] and $\rho=1/c^{2}$ in Euclidean space [5]. This means that the algorithm
considers $\Theta(tn^{\rho})$ candidate points, which could be as large as
$\Theta(n^{1+\rho})$ for large $t$. In Section 5 we describe and analyze two
algorithms _Adaptive Single-probe_ and _Adaptive Multi-probe_ that mitigate
this problem. The basic idea is that these algorithms “notice” the presence of
many close points, and respond by setting $c$ more lenient, allowing for $t$
far points being reported per repetition in addition to the $t$ close points.
This in turn allows doing only $\Theta((n/t)^{\rho})$ repetitions, giving a
total candidate set of size $\Theta(t(n/t)^{\rho})$, which is never larger
than $n$. In general, the number of points between distance $r$ and $cr$ have
a linear influence in these running times. This is made precise in Section 4.

#### Multi-probing.

When we stick to the LSH framework, the ideal solution would never consider a
candidate set larger than $\Theta(n^{\rho}+t)$, giving the optimal output
sensitive running time achievable by (data independent) LSH. In order to get
closer to this bound, we analyze the _multi-probing approach_ for LSH data
structures, introduced in [26] and further developed in [24]. The idea is that
LSH partitions the space in many buckets, but usually only examines the exact
bucket in which the query point falls in each repetition. Multi-probing
considers all buckets “sufficiently correlated” with the query bucket to
increase the likelihood of finding close points. To our knowledge, multi-
probing has always been applied in order to save memory by allowing a smaller
number of repetitions to be made and trading this for an increase in query
time. Our motivation is different: We want to take advantage of the fact that
each of the very close points can only be in one bucket per repetition. Hence
by probing multiple buckets in each repetition, _we not only save memory, but
also gain a large improvement in the dependency on $t$ in our running time_.
We do this by generalizing the adaptive single-probe algorithm to not only
find the optimal $c$ for a query, but also the optimal number of buckets to
probe. As we show in Section 5, we are able to do this in time negligible
compared to the size of the final candidate set, making it practically free.
The algorithm works for any probing sequence supplied by the user, but in
Section 6 we provide a novel probing sequence for Hamming space and show that
it always improves the query time compared to the non-multi-probing variant.
For certain regimes of $t$, we show that the running time matches the target
time $O(n^{\rho}+t)$. An overview of the exact running time statements of the
algorithms proposed here with a comparison to standard LSH, a linear scan, and
the optimal running time for LSH-based algorithms is depicted in Figure 2.

#### Techniques.

The proposed data structure is very similar to a standard LSH data structure.
While such a data structure usually uses only one particular concatenation
length $k$ of hash functions, we build the data structure for all lengths
$1,\ldots,k$. At query time, we do an efficient search over the parameter
space to find the provably best level. The algorithm then retrieves only the
candidates from this level and filters far away points and duplicates. The
reason we are able to do an efficient search over the parameter space is that
certain parts of the output size can be estimated very quickly when storing
the size of the hash table buckets in the LSH data structure. For example,
when considering very large $c$, though the output may be large, there are
only few repetitions to check. Gradually decreasing $c$, we will eventually
have to check so many repetitions that the mere task of iterating through them
would be more work than scanning through the smallest candidate set found so
far. Since the number of repetitions for each value of $c$ grows
geometrically, it ends up being bounded by the last check, which has size not
larger than the returned candidate set. For multi-probing it turns out that a
similar strategy works, even though the search problem is now two-dimensional.

#### Additional Related Work.

Our approach to query-sensitivity generalizes and extends the recent work of
Har-Peled and Mahabadi [18] which considers approximate near neighbors. Our
method applies to every space and metric supported by the LSH framework while
[18] is presented for Hamming space.

The proposed single-probing algorithm can be thought of as an adaptive query
algorithm on the trie-based LSH forest introduced by Bawa et al. in [10] for
the related approximate $k$-nearest neighbor problem. (The authors of [10]
make significant assumptions on the distance distribution of approximate
nearest neighbors). The algorithm proposed there always looks at all
$n^{f(c)}$ repetitions where $f(c)$ depends on the largest distance $r$
supported by the algorithm and the approximation factor. It collects points
traversing tries synchronously in a bottom-up fashion. By looking closer at
the guarantees of LSH functions, we show that one can gradually increase the
number of repetitions to look at and find the best level to query directly. We
hope that the insights provided here will shed new light on solving
approximate nearest neighbors beyond using standard reductions as in [17].

Combining results of very recent papers [23, 13, 7] on space/time-tradeoffs
make it possible to achieve running times that are similar to our results with
respect to multi-probing. We give a detailed exposition in Appendix G and plan
to include these results in the final version.

##  2 Preliminaries

Let $(X,\textnormal{dist})$ be a metric space over $X$ with distance function
dist. In this paper, the space usually does not matter; only the multi-probing
sequence in Section 6 is tied to Hamming space.

######  Definition 1 (Spherical Range Reporting, SRR).

Given a set of points $S\subseteq X$ and a number $r\geq 0$, construct a data
structure that supports the following queries: Given a point $q\in X$, report
each point $p\in S$ with $\text{dist}(p,q)\leq r$ with constant probability.

Note that we consider the exact version of SRR but allow point-wise
probabilistic guarantees.

######  Definition 2 (Locality-Sensitive Hash Family, [11]).

A _locality-sensitive hash family_ $\mathcal{H}$ is family of functions
$h\colon X\to R$, such that for each pair $x,y\in X$ and a random
$h\in\mathcal{H}$, whenever $\text{dist}(q,x)\leq\text{dist}(q,y)$ we have
$\Pr[h(q)=h(x)]\geq\Pr[h(q)=h(y)]$, for arbitrary $q\in X$.

Usually the set $R$ is small, like the set $\\{0,1\\}$. Often we will
concatenate multiple independent hash functions from a family, getting
functions $h_{k}\colon X\to R^{k}$. We call this a hash function at level $k$.

Having access to an LSH family $\mathcal{H}$ allows us to build a data
structure with the following properties.

######  Theorem 1 ([17, Theorem 3.4]).

Suppose there exists an LSH family such that $\Pr[h(q)=h(x)]\geq p_{1}$ when
$\text{dist}(q,x)\leq r$ and $\Pr[h(q)=h(x)]\leq p_{2}$ when
$\text{dist}(q,x)\geq cr$ with $p_{1}>p_{2}$, for some metric space
$(X,\textnormal{dist})$ and some factor $c>1$. Then there exists a data
structure such that for a given query $q$, it returns with constant
probability a point within distance $cr$, if there exists a point within
distance $r$. The algorithm uses $O(dn+n^{1+\rho})$ space and $O(n^{\rho})$
hash function evaluations per query, where $\rho=\frac{\log 1/p_{1}}{\log
1/p_{2}}$.

It is essential for understanding our algorithms to know how the above data
structure works. For the convenience of the reader we provide a description of
it in Appendix A.

In this paper, we state the $\rho$-parameter as used in Theorem 1 as a
function $\rho(r,c)$ such that $\rho(r,c)=\frac{\log(1/p(r))}{\log(1/p(cr))}$,
where $p(\Delta)$ is the probability that two points at distance $\Delta$
collide. (The probability is over the random choice of the LSH function.) We
omit the parameters when their value is clear from the context.

A common technique when working with LSH is multi-probing [24, 26, 15, 6, 21].
The idea is that often the exact bucket $h_{k}(q)$ does not have a much higher
collision probability with close points than some “nearby” bucket
$\sigma(h_{k}(q))$. Hence we probe multiple buckets in each repetition to
reduce the space needed for storing repetitions. In this paper we are going to
show how this approach can give not just space improvements, but also large
improvements in query time for SRR.

The LSH framework can easily be extended to solve SRR. We just report all the
points that are in distance at most $r$ from the query point in the whole
candidate set retrieved from all tables $T_{1},\ldots,T_{L}$ [3]. For the
remainder of this paper, we will denote the number of points retrieved in this
way by $W$ (“work”). It is easy to see that this change to the query algorithm
would already solve SRR with the guarantees stated in the problem definition.
However, we will see in Section 4 that its running time might be as large as
$O(n^{1+\rho})$, worse than a linear scan over the data set.

##  3 Data Structure

We extend a standard LSH data structure in the following way.

######  Definition 3 (Multi-level LSH).

Assume we are given a set $S\subseteq X$ of $n$ points, two parameters $r$ and
$L$, and access to an LSH family $\mathcal{H}$ that maps from $X$ to $R$. Let
$\text{reps}(k)=\lceil p_{1}^{-k}\rceil$ where $p_{1}$ is the probability that
points at distance $r$ collide under random choice of $h\in\mathcal{H}$. Let
$K$ be the largest integer $k$ such that $\text{reps}(k)\leq L$. A _Multi-
level LSH data structure_ for $S$ is set up in the following way: For each
$k\in\\{0,\ldots,K\\}$ choose functions $g_{k,i}$ for $1\leq
i\leq\text{reps}(k)$ from $\mathcal{H}$ independently at random. Then, for
each $k\in\\{0,\ldots,K\\}$, build $\text{reps}(k)$ hash tables $T_{k,i}$ with
$1\leq i\leq\text{reps}(k)$. For a fixed pair $k\in\\{0,\ldots,K\\}$ and
$i\in\\{1,\ldots,\text{reps}(k)\\}$, and each $x\in X$, concatenate hash
values $(g_{1,i}(x),\ldots,g_{k,i}(x))\in R^{k}$ to obtain the hash code
$h_{k,i}(x)$. Store references to all points in $S$ in table $T_{k,i}$ by
applying $h_{k,i}(x)$. For a point $x\in X$, and for integers $0\leq k\leq K$
and $1\leq i\leq\text{reps}(k)$, we let $|T_{k,i}(x)|$ be the number of points
in bucket $h_{k,i}(x)$ in table $T_{k,i}$. We assume this value can be
retrieved in constant time.

In contrast to a standard LSH data structure, we only accept the number of
repetitions as an additional parameter. The value $K$ is chosen such that the
number of repetitions available suffices to obtain a close point at distance
$r$ with constant probability, cf. Appendix A. This is ensured by the
repetition count for all levels $0,\ldots,K$. The space usage of our data
structure is $O(n\sum_{0\leq k\leq K}p_{1}^{-k})=O(np_{1}^{-K)})=O(nL)$. Hence
multiple levels only add a constant overhead to the space consumption compared
to a standard LSH data structure for level $K$. Figure 3 provides a
visualization of the data structure.

$T_{K,i}$Pointset
$S$$h_{0,1}$$h_{1,1}$$h_{1,2}$$h_{K,i}$$\vdots$$T_{0,1}$$T_{1,1}$$T_{1,2}$$T_{2,1}$$T_{2,2}$$T_{2,3}$$T_{2,4}$Level$0$$1$$2$$\vdots$$K$Rep.${p^{-0}}$${p^{-1}}$${p^{-2}}$${p^{-K}}$$\vdots$$\ddots$$T_{K,1}$$T_{K,2}$$T_{K,3}$$T_{K,4}$$T_{K,5}$$T_{K,p^{-K}}$
Figure 3: Overview of the multi-level LSH data structure with tables $T_{k,i}$
and hash functions $h_{k,i}$ splitting a data set $S$. The data structure is
set up for levels $0,...,K$ with repetition count “Rep.” for collision
probability $p$ (avoiding ceilings). Example for a space partition of $S$
induced by hash function $h_{K,i}$ is explicitly depicted as the content of
table $T_{K,i}$ where each class is a bucket.

We describe an alternative tree-based data structure that trades query time
for space consumption in Appendix B. We remark that some of the proposed query
algorithms will require a slightly higher repetition count. In such cases, the
function reps will be redefined. The additional repetition count will never
add more than a polylog overhead to the running time.

##  4 Standard LSH, Local Expansion, and Probing the Right Level

In this section we show that using a standard LSH approach might yield running
time $\Omega(tn^{\rho})$ when standard parameter settings such as the ones
from Theorem 1 are used to solve SRR. Then, we define a measure for the
difficulty of a query. Finally, we show that if the output size and this
measure is known, inspecting a certain level in the multi-level LSH data
structure gives output- and query-sensitive expected running times.

######  Observation 1.

Suppose we want to solve SRR in $(X,\textnormal{dist})$ using LSH with
parameters as in Theorem 1 with LSH family $\mathcal{H}$. Let $q\in X$ be a
fixed query point. Then there exist data sets $S\subseteq X$ with $|S|=n$ such
that the expected number of points retrieved from the hash tables on query $q$
in the LSH data structure built for $S$ is $\Omega(tn^{\rho})$.

The basic idea of the proof is to inspect difficult data sets in which there
are $t-1$ very close points to the query, one point at distance $r$, and all
the other points at distance close to $cr$. Details are deferred to Appendix
C.

For a set $S$ of points, a point $q$, and a number $r>0$, let $N_{r}(q)$ be
the number of points in $S$ at distance at most $r$ from $q$. We next define
the _expansion_ at a query point $q$ for a given distance. The expansion
measures how far we can increase the radius of an $r$-sphere around the query
point before the number of points covered increases above some constant
factor. This dimensionality measure is central in the running time analysis of
our proposed algorithms.

######  Definition 4 (Expansion).

Let $r>0$, $q\in X$ and $S\subseteq X$ be a set of points. The _expansion_
$c^{\ast}_{q,r}$ at point $q$ is the largest number $c$ such that
$N_{cr}(q)\leq 2N_{r}(q)$, where $c^{\ast}_{q,r}$ is $\infty$ if $N_{r}(q)\geq
n/2$.

We will often simply write $c^{*}_{q}$, when $r$ is known in the context. A
visualization for the expansion around a query is depicted in Figure 1.

###  4.1 Query Algorithms If $t$ and $c^{\ast}_{q}$ are Known

######  Theorem 2.

Let $r>0$ and $c\geq 1$. Let $S$ be a set of $n$ points and let DS be the
Multi-level LSH data structure obtained from preprocessing $S$ with
$L=\Omega(n^{\rho(r,c)})$. Given a query point $q$, let $t=N_{r}(q)$ and
$c_{q}^{\ast}$ be the expansion around $q$ in $S$. There exists a query
algorithm on DS to solve SRR with the following properties:

  1. (i)

If $c_{q}^{\ast}\geq c$, the algorithm has expected running time
$O(t(n/t)^{\rho(r,c_{q}^{\ast})})$.

  2. (ii)

Otherwise, the algorithm has expected running time
$O(t(n/t)^{\rho(r,c)}+N_{cr}(q))$.

For $t=0$, the running time is the same as $t=1$.

###### Proof.

Let $p_{1}$ and $p_{2}$ be the probabilities that the query point collides
with points at distance $r$ and $c_{q}^{\ast}r$, respectively, given the LSH
family used. We consider statement (i) first. Look at level
$k=\lceil\frac{\log(n/t)}{\log(1/p_{2})}\rceil$ in DS such that $p_{2}^{k}\leq
t/n$ and $p_{1}^{-k}=\Theta((n/t)^{\rho(r,c^{\ast}_{q})})$. Since
$c^{*}_{q}\geq c$, we can assume $p_{1}^{-k}\leq L$, so that we may inspect
that many repetitions and guarantee constant collision probability with a
close points. The total expected number of collisions is then not more than
$p_{1}^{-k}(t+N_{c_{q}^{*}r}(q)p_{1}^{k}+np_{2}^{k})$. By the choice of $k$,
$np_{2}^{k}\leq t$ and so this is $O(tp_{1}^{-k}+N_{c_{q}^{*}}(q))$. By the
definition of $c^{*}_{q}$, $N_{c_{q}^{*}r}(q)=O(t)$ and so this term is
dominated by the former. Finally looking at every bucket takes time
$O(p_{1}^{-k})$, but this is likewise dominated if $t\geq 1$. Statement (ii)
follows by the same line of reasoning, simply using $c$ instead of
$c^{*}_{q}$. Since this value of $c$ does not have the expansion property, the
term $N_{cr}(q)$ is present in the running time. ∎

As can be seen from the theorem statement, our running time bounds might
depend on the number of points at distance at most $cr$. This happens when the
expansion around the query is smaller than the $c$ value that can be read off
from the number of repetitions and the LSH hash family at hand. The influence
of these points is however only linear in their number. The result basically
shows that there exists a single level of the multi-level LSH data structure
that we want to probe when $t$ and the expansion around the query is known.

##  5 Adaptive Query Algorithms

In this section we describe a query algorithm that obtains the results from
Theorem 2 without knowing $t$ or the expansion around the query. It turns out
that we can get something even better, i.e., a running time equivalent to
knowing the entire distribution of distances $\text{dist}(q,x)$ from the query
point $q$ to data points $x$ in the data set.

We work on a multi-level LSH data structure, DS, set up for $S\subseteq X$
with tables $T_{k,i}$. DS is assumed to have been built with $L$ repetitions
and $K$ levels, see Definition 3. Now, a query algorithm looking at the
buckets at level $k$, would be expected to take time

$\displaystyle\textnormal{{E}}[W_{k}]$
$\displaystyle=p_{1}^{-k}(O(1)+\sum_{x\in S}\Pr[h_{k}(q)=h_{k}(x)]).$ (1)

This accounts for the $p_{1}^{-k}$ repetitions to be made for correctness (cf.
Appendix A), $O(1)$ time for probing and evaluating the hash functions, and,
by linearity of expectation, the number $\sum_{x\in S}\Pr[h_{k}(q)=h_{k}(x)]$
of expected collisions and thus points retrieved from the hash tables. For
ease of presentation, we omit ceilings for repetition counts $p_{1}^{-k}$ and
note that adding a constant to $k$ never changes the results by more than a
constant factor.

The function $\textnormal{{E}}[W_{k}]$ over $k$ will have an optimum in
$[0,K]$. It turns out that we can indeed find this optimum and get expected
running time close to:

$\displaystyle W_{\text{single}}$ $\displaystyle=\min_{0\leq k\leq
K}\textnormal{{E}}[W_{k}].$ (2)

Since this describes the best expected running time given knowledge of the
distance distribution _at the query_ , we note that the quantity is always
upper bounded by running times stated in Theorem 2. (Given that the number of
repetitions is sufficiently high as stated there.) However, in many important
cases it can be much smaller than that! In Appendix D we calculate
$W_{\text{single}}$ for different data distributions, including “locally
growth-restricted” as considered in [14]. In this case it turns out that
$W_{\text{single}}=O(\log n)$, an exponential improvement over “standard”
query time $O(n^{\rho})$.

The query algorithm is given as Algorithm 1 and works as follows: For each
level $0\leq k\leq K$, calculate the work of doing
$\text{reps}(k)=p_{1}^{-k}(2\log 2k)$ repetitions by summing up all bucket
counts. (The $2\log 2k$ factor is a technical detail explained in the proof
below.) Terminate as soon as the optimal level has been provably found, which
may be one that we have considered in the past, and report all close points in
the candidate set. This decision is based on whether the number of buckets to
look at alone is larger than the smallest candidate set found so far or not.

Algorithm 1 Adaptive-Single-Probe($q$, $p_{1}$, $T$)

1:$k\leftarrow 1,k_{\text{best}}\leftarrow 0,w_{k_{\text{best}}}\leftarrow n;$

2:while $\text{reps}(k)\leq\min(L,w_{k_{\text{best}}})$ do

3: $w_{k}\leftarrow\sum_{i=1}^{\text{reps}(k)}(1+|T_{k,i}(q)|)$;

4: if $w_{k}<w_{k_{\text{best}}}$ then

5: $k_{\text{best}}\leftarrow k;w_{k_{\text{best}}}\leftarrow w_{k}$;

6: $k\leftarrow k+1$;

7:return $C\leftarrow\bigcup_{i=1}^{\text{reps}(k_{\text{best}})}\\{x\in
T_{k_{\text{best}},i}(q)\mid\text{dist}(x,q)\leq r\\}$

######  Theorem 3.

Let $S\subseteq X$ with $|S|=n$ and $r$ be given. Then Algorithm 1 on DS
solves SRR with constant probability. The expected running time of the while-
loop in Lines (2)–(6) and the expected number of distance computations in Line
(7) is $O(W_{\text{single}}\log\log W_{\text{single}})$.

_Proof._ First we show that the algorithm works correctly, then we argue about
its running time.

For correctness, let $y\in S$ be a point with $\text{dist}(y,q)\leq r$. At
each level $k$, we see $y$ in a fixed bucket with probability at least
$p_{1}^{k}$. With $\text{reps}(k)$ repetitions, the probability of finding $y$
is at least $1-(1-p_{1})^{\text{reps}(k)}\geq 1-1/(2k)^{2}$. By a union bound
over the $K$ levels of the data structure, $y$ is present on every level with
probability at least $1-\sum_{k=1}^{\infty}1/(2k)^{2}\geq 1/2$, which shows
correctness.

Now we consider the running time. The work inside the loop is dominated by
Line (3) which takes time $O(\text{reps}(k))$, given constant access to the
size of the buckets. Say the last value $k$ before the loop terminates is
$k^{\ast}$, then the loop takes time $\sum_{k=1}^{k^{*}}O(\log k\cdot
p_{1}^{-k})\leq\log k^{*}\cdot
p_{1}^{-k^{*}}\sum_{k=0}^{\infty}O(p_{1}^{k})=O(\log k^{*}\cdot
p_{1}^{-k^{*}})=O(w_{k_{\text{best}}})$, where the last equality is by the
loop condition, $\text{reps}(k^{\ast})\leq w_{k_{\text{best}}}$.

In Line 7, the algorithm looks at $w_{k_{\text{best}}}$ points and buckets.
Hence the total expected work is

$\displaystyle\textnormal{{E}}(w_{k_{\text{best}}})$
$\displaystyle=\textnormal{{E}}\left[\min_{0\leq k\leq K}w_{k}\right]$
$\displaystyle\leq\min_{0\leq k\leq K}\textnormal{{E}}[w_{k}]$ by Jensen’s
inequality $\displaystyle=\min_{0\leq k\leq K}\log
k\cdot\textnormal{{E}}[W_{k}]$ $\displaystyle\leq\log
k^{\prime}\cdot\textnormal{{E}}[W_{k^{\prime}}]$ where
$k^{\prime}=\operatorname*{arg\,min}_{0\leq k\leq K}\textnormal{{E}}[W_{k}]$
$\displaystyle=O(W_{\text{single}}\log\log W_{\text{single}})$ as
$p_{1}^{-k^{\prime}}\leq W_{\text{single}}$. ∎

###  5.1 A Multi-probing Version of Algorithm 1

We extend the algorithm from the previous subsection to take advantage of
multi-probing. For a particular hash function $h_{k}$, distance $r$ and value
$\lambda\geq 1$, we define a _probing sequence_
$\sigma=(\sigma_{k,\ell})_{1\leq\ell\leq\lambda}$ as a sequence of functions
$R^{k}\to R^{k}$. Now when we would probe bucket $T_{k,i}(h_{k}(q))$, we
instead probe
$T_{k,i}(\sigma_{k,1}h_{k}(q)),\dots,T_{k,i}(\sigma_{k,\lambda}h_{k}(q))$.
(Where $\sigma_{k,1}$ will usually be the identity function.)

For a point $y$ at distance $r$ from $q$, we will be interested in the event
$[\sigma_{k,\ell}h_{k}(q)=h_{k}(y)]$. The probability that this event occurs
is donated by $p_{k,\ell}$. If $p_{k,1}\geq p_{k,2}\geq\dots$, we say that the
probing sequence is _reasonable_. The intuition is that we probe buckets in
order of expected collisions. In particular, by disjointness of the events,
the probability of a collision within the first $\ell$ probes is exactly
$P_{k,\ell}=p_{k,1}+\dots+p_{k,\ell}$. Hence doing $\ell$ probes per
repetition, we need about $1/P_{k,\ell}$ repetitions to obtain constant
probability of finding $y$. In practice, probing sequences are usually not
reasonable [6], but as long as $p_{k,\ell}$ is known, they can be sorted in
advance.

To state the complexity of our algorithm, we generalize the quantity
$W_{\text{single}}$ from (2) in the natural way to include multi-probing. As
in the case of probing a single bucket, $W_{\text{multi}}$ denotes the minimal
work one would expect to need for an LSH based approach that knows the optimal
values of $k$ and $\ell$.

$\displaystyle W_{\text{multi}}$ $\displaystyle=\min_{0\leq k\leq
K,1\leq\ell}\left[\frac{1}{P_{k,\ell}}\left(\ell+\sum_{x\in S,1\leq
i\leq\ell}\Pr[\sigma_{k,i}h(q)=h(x)]\right)\right]$ (3)

As in Algorithm 1, we carefully explore the now two-dimensional and infinite
space $[0,K]\times[1,\infty]$ of parameters. Consider the probability of
finding some point $y$ at distance $r$ to our query. Say we choose values
$(k,\ell)$ and make $\text{reps}(k,\ell)$ repetitions; we would then probe
buckets
$\bigcup_{i=1}^{\text{reps}(k,\ell)}\bigcup_{j=1}^{\ell}T_{k,i}[\sigma_{k,j}h_{k}(q)]$
and find $y$ with probability $1-(1-P_{k,\ell})^{\text{reps}(k,\ell)}$. As in
the single-probing algorithm, we have to be careful about dependencies and set
$\text{reps}(k,\ell)=(2\log(2\ell k))/P_{k,\ell}$ such that the probability of
not finding $y$ is less than $\exp(-\text{reps}(k,\ell)/P_{k,\ell})=(2\ell
k)^{-2}$. A union bound over the whole parameter space yields
$\sum_{k=1}^{\infty}\sum_{\ell=1}^{\infty}(2\ell k)^{-2}<7/10$, and so $y$ is
present for every parameter choice with constant probability.

All that remains is reusing the idea from Algorithm 1 of maintaining upper and
lower bounds on the final work, and stop once they meet. The parameter space
is explored using a priority queue. The pseudocode of the algorithm is given
as Algorithm 2. To obtain good query time it is necessary to store the values
$W_{k,\ell}$ computed so far and reuse them in Line 7 of Algorithm 2. Details
are given in the proof below.

Algorithm 2 Adaptive-Multi-probe($q$, $\sigma$, $T$)

1:$W_{\text{best}}\leftarrow n$; $k_{\text{best}}\leftarrow 0$;
$\ell_{\text{best}}\leftarrow 1$; $\text{PQ}\leftarrow$ empty priority queue

2:for $1\leq k\leq K$ do

3: $\text{PQ.insert}((k,1),\text{reps}(k,1))$

4:while PQ.min() $<W_{\text{best}}$ do

5: $(k,\ell)\leftarrow$ PQ.extractMin()

6: PQ.insert($(k,\ell+1)$, $(\ell+1)\cdot$reps$(k,\ell+1)$)

7:
$W_{k,\ell}\leftarrow\sum_{i=1}^{\text{reps}(k,\ell)}\sum_{j=1}^{\ell}\left(1+|T_{k,i}[\sigma_{k,j}h_{k,i}(q)]|\right)$

8: if $W_{k,\ell}<W_{\text{best}}$ then

9: $k_{\text{best}}\leftarrow k;\quad\ell_{\text{best}}\leftarrow\ell;\quad
W_{\text{best}}\leftarrow W_{k,\ell}$

10:return
$\bigcup_{i=1}^{\text{reps}(k_{\text{best}},\ell_{\text{best}})}\bigcup_{j=1}^{\ell_{\text{best}}}\\{x\in
T_{k_{\text{best}},i}[\sigma_{k_{\text{best}},j}h_{k_{\text{best}},i}(q)]\mid\text{dist}(x,q)\leq
r\\}$

######  Theorem 4.

Let $S\subseteq X$ and $r$ be given. Let $(k,\ell)$ be a pair that minimizes
the right-hand side of (3). Given a reasonable probing sequence $\sigma$,
Algorithm 2 on DS solves SRR. If DS supports at least $\text{reps}(k,\ell)$
repetitions, the expected running time is
$O(W_{\text{multi}}\log^{3}W_{\text{multi}})$ and the expected number of
distance computations is $O(W_{\text{multi}}\log W_{\text{multi}})$.

###### Proof.

Correctness of the algorithm follows by the explanation before the theorem
statement.

To analyze the running time, we define
$\text{cost}(k,\ell)=\ell\cdot\text{reps}(k,\ell)$. This value is used as the
priority of a parameter pair in the priority queue. It provides a lower bound
on the work required to consider this parameter pair because we have to check
that many buckets. Next we note that it cannot happen that all pairs
$(k,\ell)$ in the priority queue have cost larger than $W_{\text{best}}$, but
there exists a pair $(k^{\prime},\ell^{\prime})$ with $k^{\prime}\geq k$ and
$\ell^{\prime}\geq\ell$ not inspected so far such that
$\text{cost}(k^{\prime},\ell^{\prime})<W_{\text{best}}$. This is because for
fixed $k$ the cost is non-decreasing in $\ell$ by Lemma 1 (provided in
Appendix E) and for fixed $\ell$ cost$(k,\ell)$ is non-decreasing in $k$.

To compute a new value $W_{k,\ell+1}$ in Line (7) of the algorithm, we take
advantage of the work $W_{k,\ell}$ already discovered, and only compute the
number of buckets that are new or no longer needed. Specifically, we compute

$\displaystyle
W_{k,\ell+1}=W_{k,\ell}+\sum_{i=1}^{\text{reps}(k,\ell+1)}|T_{k,i}(\sigma_{k,\ell+1}(q))|-\sum_{j=1}^{\ell}\sum_{i=1+\text{reps}(k,\ell)}^{\text{reps}(k,\ell+1)}|T_{k,i}(\sigma_{k,j}(q))|.$

So, for each $k$ we never visit a bucket more than twice and amortized over
all operations, the computation of $W_{k,\ell+1}$ takes time
$O(\text{reps}(k,\ell+1))$. For each $k$ with $1\leq k\leq K$, let
$\ell_{k}^{\ast}$ be the largest value of $\ell$ such that the pair $(k,\ell)$
was considered by the algorithm. The total cost of computing
$W_{k,1},\ldots,W_{k,\ell_{k}^{\ast}}$ is then at most
$\sum_{i=1}^{\ell^{\ast}}\text{reps}(k,i)=\sum_{i=1}^{\ell^{*}}2(\log(2ki))/P_{k,i}=O(\ell^{*}(\log\ell^{\ast})^{2}/P_{k,\ell^{\ast}})$
by Lemma 1. By the loop condition, we know that
$\log\ell^{\ast}\cdot\ell^{\ast}/P_{k,\ell^{\ast}}$ is at most
$W_{\text{best}}$, so the algorithm spends time $O(W_{\text{best}}\log
W_{\text{best}})$ for fixed $k$.

Let $k_{\text{max}}$ be the maximum value of $k$ such that a pair $(k,\ell)$
was considered by the algorithm. Since we stop when every item in the priority
queue has a priority higher or equal to $W_{\text{best}}$, we must have
$k_{\text{max}}\leq\frac{\log W_{\text{best}}}{\log 1/p_{1}}$ because we need
at least $p_{1}^{-k_{\text{max}}}$ repetitions for the single probe on level
$k_{\text{max}}$.

Thus, the final search time for the while-loop is
$O(W_{\text{best}}\log(W_{\text{best}})^{2})$ and the algorithm makes exactly
$W_{\text{best}}$ distance computations in Line (10). Now observe that by
bounding the additional repetitions by $O(\log W_{\text{multi}})$, the same
reasoning as in the proof of Theorem 3 shows
$\textnormal{{E}}(W_{\text{best}})=O(W_{\text{multi}}\log W_{\text{multi}})$.
∎

##  6 A Probing Sequence in Hamming Space

In this section we analyze bitsampling LSH in Hamming space [17, Section
3.2.1] using a novel, simple probing sequence. We consider the static setting
as in Section 4.1, where the number of points to report and the expansion
around the query is known. We then show the existence of certain (optimal)
level and probing length parameters, and prove that using those give a good
expected running time. The adaptive query algorithm from Section 5 would find
parameters at least as good as those, and thus yield a running time as least
as good as what we show here.

$a$$X$$\sigma_{1,1}h_{1,k}(q)$$\sigma_{2,1}h_{2,k}(q)$$\sigma_{2,i}h_{2,k}(q)$$\sigma_{3,1}h_{3,k}(q)$$h_{1,k}(y)$$h_{2,k}(y)$$h_{3,k}(y)$$\dots$$L$
Figure 4: At each of the $L$ repetitions we query the closest $\ell$
positions. Since the projected distance $X$ to our target point $y$ is
distributed as $\text{Bin}(k,\text{dist}(q,y)/d)$, we find $y$ with constant
probability by setting $L=O(\Pr[X\leq a]^{-1})$.

Our scheme uses hash functions $h_{k}:\\{0,1\\}^{d}\rightarrow\\{0,1\\}^{k}$
that sample $k$ positions at random with repetition. For a fixed query point
$q\in\\{0,1\\}^{d}$ and $k\geq 1$, the probing sequence $\sigma_{k,\ell}$ maps
$h_{k}(q)$ to the $\ell$-th closest point in $\\{0,1\\}^{k}$, where ties are
broken arbitrarily. This sequence can be generated efficiently, see [22].

Fix a target close point $y\in\\{0,1\\}^{d}$ at distance $r$, let $p$ be the
probability that $q$ and $y$ collide, and let $p_{k,\ell}$ be the probability
that $y$ lands in the $\ell$-th bucket that we check. Furthermore, let
$V(a)=\sum_{i=0}^{a}{k\choose i}$ be the volume of the radius $a$ hamming
ball. If $\sigma_{k,\ell}h_{k}(q)$ is at distance $a$ to $h(q)$, we have a
collision if $q$ and $y$ differ in exactly $a$ out of the $k$ coordinates
chosen by $h_{k}$. Hence, $p_{k,\ell}=p^{k-a}(1-p)^{a}$ for the $a$ satisfying
$V(a-1)<\ell\leq V(a)$. Thus, the sequence is reasonable. Figure 4 illustrates
our approach.

The best approximations to sizes of hamming balls are based on the entropy
function. Hence, for the purpose of stating the theorem, we introduce the
following notation. For $\alpha\in[0,1]$ and $\beta\in[0,1]$, we let
$H(\alpha)=\alpha\log 1/\alpha+(1-\alpha)\log 1/(1-\alpha)$ and
$\operatorname*{D}\left(\alpha\;\middle\|\;\beta\right)=\alpha\log(\alpha/\beta)+(1-\alpha)\log((1-\alpha)/(1-\beta))$
denote the binary entropy of $\alpha$ and the relative entropy between
$\alpha$ and $\beta$, respectively. Moreover, let $\rho(r,c)=\tfrac{\log
t}{\log
n}\left(1+\tfrac{\operatorname*{D}\left(\alpha\;\middle\|\;1-p(r)\right)}{\operatorname*{H}(\alpha)}\right)$
where $\alpha$ is defined implicitly from $\tfrac{\log t}{\log
n}\left(1+\tfrac{\operatorname*{D}\left(\alpha\;\middle\|\;1-p(cr)\right)}{\operatorname*{H}(\alpha)}\right)=1$.

######  Theorem 5.

Let $r>0$ and $c\geq 1$. Let $S$ be a set of $n$ points and let DS be the
Multi-level LSH data structure obtained from preprocessing $S$ with
$L=\Omega(n^{\rho(r,c)})$. Given a query point $q$, let $t=N_{r}(q)+1$ and let
$c_{q}^{\ast}$ be the expansion around $q$ in $S$. If $c_{q}^{\ast}\geq c$,
there exists a query algorithm on DS to solve SRR with running time
$O(n^{\rho(r,c_{q}^{*})})$, otherwise the running time is
$O(n^{\rho(r,c)}+N_{cr}(q))$.

We do not know of a simple closed form for $\rho(r,c)$, but Figure 2 on Page 2
shows a numerical evaluation for comparison with the running time obtained for
single-probing and other approaches.

The figure suggests that we always get better exponents than the single-probe
approach, and that we get optimal query time for large $t$ and asymptotically
optimal for $t=n^{o(1)}$. Corollary 1 confirms this:

######  Corollary 1.

Let $\rho=(\log p_{1})/(\log p_{2})<1/c$ be the usual exponent for
bitsampling, then:

If $t\geq
n^{\frac{\operatorname*{H}(1-p_{2})}{\operatorname*{H}(1-p_{2})+\operatorname*{D}\left(1-p_{2}\;\middle\|\;1-p_{1}\right)}}$,
the expected query time is $O(n^{\rho(r,c)})=O(n^{\rho}+t)$.

If $t=n^{o(1)}$, the expected query time is
$O(n^{\rho(r,c)})=O(n^{\rho}t^{o(1)})$.

###### Proof of Theorem 5.

We will now show that the smaller number of repetitions needed by multi-
probing leads to fewer collisions with the $t$ very close points in hard
instances of SRR. To see this, we bound the value of $W_{\text{multi}}$ from
(3) as follows:

$\displaystyle W_{\text{multi}}$
$\displaystyle=\min_{k,\ell}\left[\frac{1}{\sum_{1\leq\ell\leq\lambda}\Pr[\sigma_{k,\ell}(h_{k}(q))=h_{k}(y)]}\left(\ell+\\!\\!\\!\\!\\!\sum_{x\in
S,1\leq\ell\leq\lambda}\\!\\!\\!\Pr[\sigma_{k,\ell}(h_{k}(q))=h_{k}(x)]\right)\right]$
$\displaystyle\leq\min_{k,a}\left[\frac{1}{\Pr[\text{dist}(h_{k}(q),h_{k}(y))\leq
a]}\left(V_{k}(a)+\sum_{x\in S}\Pr[\text{dist}(h_{k}(q),h_{k}(x))\leq
a]\right)\right]$
$\displaystyle\leq\min_{k,a}\left[\frac{1}{\Pr[\text{Bin}(k,1\text{-}p_{1})\leq
a]}\left(V_{k}(a)+t+t^{\prime}\Pr[\text{Bin}(k,1\text{-}p_{1})\leq
a]+n\Pr[\text{Bin}(k,1\text{-}p_{2})\leq a]\right)\right]$

The first inequality holds by restricting $\ell$ to only take values that are
the volume of a $k$-dimensional hamming ball; in the second inequality we
upper bounded the collision probabilities for points in ranges $[0,r)$,
$[r,cr)$ and $[cr,d]$.

The next step is to minimize this bound over the choice of $k$ and $a$. We
focus on $t^{\prime}=O(t)$ and so we want
$V_{k}(a)=t=n\Pr[\text{Bin}(k,1\text{-}p_{2})\leq a]$. For simplicity we write
$\alpha=a/k$ for the normalized radius. We use the following tight bound on
the tail of the binomial distribution: $\Pr[\text{Bin}(k,p)\leq\alpha
k]=\exp(-k\operatorname*{D}\left(\alpha\;\middle\|\;p\right))\Theta(1/\sqrt{k})$
for $\alpha\in(0,1/2)$ and $V_{k}(\alpha
k)=\exp(kH(\alpha))\Theta(1/\sqrt{k})$ [27]. Then our equation can be written
as $k\operatorname*{H}(\alpha)=\log t=\log
n-k\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{2}\right)$. This suggests
$k=\frac{\log t}{\operatorname*{H}(\alpha)}=\frac{\log
n}{\operatorname*{H}(\alpha)+\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{2}\right)}$
and
$\frac{\operatorname*{H}(\alpha)+\operatorname*{D}\left(x\;\middle\|\;1-p_{2}\right)}{\operatorname*{H}(\alpha)}=\frac{\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{2}\right)}{\operatorname*{H}(\alpha)}+1$.
We can then plug $k$ into the bound on $W_{\text{multi}}$:

$\displaystyle W_{\text{multi}}$
$\displaystyle\leq\frac{3t}{\Pr[\text{Bin}(k,1-p_{1})\leq
a]\Theta(\sqrt{k})}+t^{\prime}$
$\displaystyle=O(t\exp(k\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{1}\right)))+t^{\prime}=O\left(n^{\frac{\log
t}{\log
n}\left(\frac{\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{1}\right)}{\operatorname*{H}(\alpha)}+1\right)}\right)+t^{\prime}$
(4)

which are exactly the values stated in Theorem 5. ∎

###### Proof Sketch Corollary 1.

For the first statement observe that if $\alpha$ is as large as $1-p_{1}$,
then $\Pr[\text{Bin}(k,1-p_{1})\leq\alpha k]$ is constant. The second factor
in the minimization has all terms being within a constant of $t$, and so the
whole thing becomes $O(t)$. We can check that $\alpha\geq 1-p_{1}$ happens
exactly when $\frac{\log t}{\log
n}\geq\frac{\operatorname*{H}(1-p_{2})}{\operatorname*{H}(1-p_{2})+\operatorname*{D}\left(1-p_{2}\;\middle\|\;1-p_{1}\right)}$.
In this range $t\geq n^{\rho}$, so $O(t)=O(n^{\rho}+t)$.

For the second part of the corollary, we solve the equation implied by Theorem
5, asymptotically as $\tau=\frac{\log t}{\log n}\to 0$. Details can be found
in Appendix F, but the idea is as follows: We first define
$f_{p}(\alpha)=1+\frac{\operatorname*{D}\left(\alpha\;\middle\|\;p\right)}{\operatorname*{H}(\alpha)}$,
and show
$f_{p_{1}}(\alpha)=(\rho+\psi\alpha/\log\frac{1}{p_{2}}+O(\alpha^{2}))f_{p_{2}}(\alpha)$
for $\psi$ being the constant defined in Corollary 1. Using bootstrapping, we
show the inversion $\alpha=f_{p_{2}}^{-1}(1/\tau)=\frac{\log
1/p_{2}}{\alpha\log 1/\alpha}+O(1/\log\frac{1}{\alpha})$. Plugging this into
(4) proves the corollary. ∎

##  7 Conclusion

In this article we proposed an adaptive LSH-based algorithm for Spherical
Range Reporting that is never worse than a static LSH data structure knowing
optimal parameters for the query in advance, and much better on many input
distributions where the output is large or the query is easy.

The main open problem remaining is to achieve target time $O(n^{\rho}+t)$ for
all inputs. One approach might be a data-dependent data structure as described
in [8]. In the light of our multi-probing results, we however wonder if the
bound can be obtained data independently as well. Here, it would be
interesting to analyze other probing sequences. It would be interesting to see
whether one can describe adaptive query algorithms that make use of the
output-sensitive space/time-tradeoff data structures we described in Appendix
G. Finally, it would be natural to extend our methods to give better LSH data
structures for the approximate $k$-nearest neighbor problem.

## References

  * [1] Pankaj K. Agarwal and Jeff Erickson.  Geometric range searching and its relatives.  Contemporary Mathematics 223, pages 1–56, 1999.  URL: http://jeffe.cs.illinois.edu/pubs/pdf/survey-tr.pdf.
  * [2] Josh Alman and Ryan Williams.  Probabilistic polynomials and hamming nearest neighbors.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 136–150, 2015.  doi:10.1109/FOCS.2015.18.
  * [3] Alexandr Andoni.  Nearest Neighbor Search: the Old, the New, and the Impossible.  PhD thesis, MIT, 2009.  URL: http://www.mit.edu/~andoni/thesis/main.pdf.
  * [4] Alexandr Andoni and Piotr Indyk.  E2LSH, user manual.  2005\.  URL: http://www.mit.edu/~andoni/LSH/manual.pdf.
  * [5] Alexandr Andoni and Piotr Indyk.  Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.  In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pages 459–468, 2006.  doi:10.1109/FOCS.2006.49.
  * [6] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt.  Practical and optimal LSH for angular distance.  In Advances in Neural Information Processing Systems 28, NIPS 2015, pages 1225–1233. Curran Associates, Inc., 2015.  URL: http://papers.nips.cc/paper/5893-practical-and-optimal-lsh-for-angular-distance.pdf.
  * [7] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten.  Lower bounds on time-space trade-offs for approximate near neighbors.  arXiv preprint arXiv:1605.02701, 2016.
  * [8] Alexandr Andoni and Ilya Razenshteyn.  Optimal data-dependent hashing for approximate near neighbors.  In Proceedings of the Forty-Seventh Annual ACM Symposium on the Theory of Computing, STOC 2015, pages 793–801. ACM, 2015.
  * [9] Sunil Arya, Guilherme D Da Fonseca, and David M Mount.  A unified approach to approximate proximity searching.  In European Symposium on Algorithms, ESA 2010, pages 374–385. Springer, 2010.
  * [10] Mayank Bawa, Tyson Condie, and Prasanna Ganesan.  LSH forest: self-tuning indexes for similarity search.  In Proceedings of the 14th international conference on World Wide Web, WWW 2005, pages 651–660. ACM, 2005.
  * [11] Moses Charikar.  Similarity estimation techniques from rounding algorithms.  In Proceedings on 34th Annual ACM Symposium on Theory of Computing, STOC 2002, pages 380–388, 2002.  doi:10.1145/509907.509965.
  * [12] Bernard Chazelle, Ding Liu, and Avner Magen.  Approximate range searching in higher dimension.  Comput. Geom., 39(1):24–29, 2008.  URL: http://dx.doi.org/10.1016/j.comgeo.2007.05.008, doi:10.1016/j.comgeo.2007.05.008.
  * [13] Tobias Christiani.  A framework for similarity search with space-time tradeoffs using locality-sensitive filtering.  CoRR, abs/1605.02687, 2016.  URL: http://arxiv.org/abs/1605.02687.
  * [14] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni.  Locality-sensitive hashing scheme based on p-stable distributions.  In Proceedings of the Twentieth annual Symposium on Computational Geometry, SOCG 2004, pages 253–262. ACM, 2004.
  * [15] Wei Dong, Zhe Wang, William Josephson, Moses Charikar, and Kai Li.  Modeling LSH for performance tuning.  In Proceedings of the 17th ACM conference on Information and Knowledge Management, CIKM 2008, pages 669–678. ACM, 2008.
  * [16] Leonhard Euler.  De progressionibus harmonicis observationes.  Commentarii academiae scientiarum Petropolitanae, 7(1734-35):150–156, 1740.
  * [17] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani.  Approximate nearest neighbor: Towards removing the curse of dimensionality.  Theory of Computing, 8(1):321–350, 2012.  doi:10.4086/toc.2012.v008a014.
  * [18] Sariel Har-Peled and Sepideh Mahabadi.  Proximity in the age of distraction: Robust approximate nearest neighbor search.  CoRR, abs/1511.07357, 2015.  URL: http://arxiv.org/abs/1511.07357.
  * [19] Piotr Indyk.  High-dimensional computational geometry.  PhD thesis, Stanford University, 2000.  URL: https://people.csail.mit.edu/indyk/thesis.html.
  * [20] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, STOC 1998, pages 604–613, 1998.  doi:10.1145/276698.276876.
  * [21] Michael Kapralov.  Smooth tradeoffs between insert and query complexity in nearest neighbor search.  In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, pages 329–342, 2015.  doi:10.1145/2745754.2745761.
  * [22] Donald E. Knuth.  Combinatorial algorithms: Part 2, The Art of Computer Programming, vol. 4a, 2011.
  * [23] Thijs Laarhoven.  Tradeoffs for nearest neighbors on the sphere.  arXiv preprint arXiv:1511.07527, 2015.
  * [24] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li.  Multi-probe LSH: Efficient indexing for high-dimensional similarity search, VLDB 2007.  pages 950–961. VLDB Endowment, 2007.  URL: http://dl.acm.org/citation.cfm?id=1325851.1325958.
  * [25] Jirí Matousek.  Geometric range searching.  ACM Comput. Surv., 26(4):421–461, 1994.  URL: http://doi.acm.org/10.1145/197405.197408, doi:10.1145/197405.197408.
  * [26] Rina Panigrahy.  Entropy based nearest neighbor search in high dimensions.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pages 1186–1195, 2006.
  * [27] Valentin Petrov.  Sums of independent random variables, volume 82.  Springer Science & Business Media, 2012.
  * [28] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theor. Comput. Sci., 348(2-3):357–365, 2005.  doi:10.1016/j.tcs.2005.09.023.

##  Appendix A Proof of Theorem 1

###### Proof.

Given access to an LSH family $\mathcal{H}$ with the properties stated in the
theorem and two parameters $L$ and $k$ (to be specified below), repeat the
following process independently for each $i$ in $\\{1,\ldots,L\\}$: Choose $k$
hash functions $g_{i,1},\ldots,g_{i,k}$ independently at random from
$\mathcal{H}$. For each point $p\in S$, we view the sequence
$h_{i}(p)=(g_{i,1}(p),\ldots,g_{i,k}(p))\in R^{k}$ as the hash code of $p$,
identify this hash code with a bucket in a table, and store a reference to $p$
in bucket $h_{i}(p)$. To avoid storing empty buckets from $R^{k}$, we resort
to hashing and build a hash table $T_{i}$ to store the non-empty buckets for
$S$ and $h_{i}$.

Given a query $q\in X$, we retrieve all points from the buckets
$h_{1}(q),\ldots,h_{L}(q)$ in tables $T_{1},\ldots,T_{L}$, respectively, and
report a close point in distance at most $cr$ as soon as we find such a point.
Note that the algorithm stops and reports that no close points exists after
retrieving more than $3L$ points, which is crucial to guarantee query time
$O(n^{\rho})$.

The parameters $k$ and $L$ are set according to the following reasoning.
First, set $k$ such that it is expected that at most one distant point at
distance at least $cr$ collides with the query in one of the repetitions. This
means that we require $np_{2}^{k}\leq 1$ and hence we define
$k=\lceil\frac{\log n}{\log(1/p_{2})}\rceil$. To find a close point at
distance at most $r$ with probability at least $1-\delta$, the number of
repetitions $L$ must satisfy
$\delta\leq(1-p_{1}^{k})^{L}\leq\exp(-p_{1}^{k}\cdot L)$. This means that $L$
should be at least $p_{1}^{-k}\ln\delta$ and simplifying yields
$L=O(n^{\rho})$. Note that these parameters are set to work even in a worst-
case scenario where there is exactly one point at distance $p$ and all other
points have distance slightly larger than $cr$. ∎

##  Appendix B A Trie-based Version of the Data Structure

In this section we discuss an alternative representation of our data
structure. This is meant as a replacement for the Multi-level LSH data
structure described in Definition 3. It offers better space consumption while
being slower to query.

As in the LSH forest data structure proposed by Bawa et al. [10], we do not
store references to data points in hash tables. Instead we use a sorted array
with a trie as a navigation structure on the array. The technical description
follows.

First, choose $K\cdot L$ functions $g_{i,j}$ for $1\leq i\leq L$ and $1\leq
k\leq K$ from $\mathcal{H}$ independently at random. For each
$i\in\\{1,\ldots,L\\}$, we store a sorted array $A_{i}$ with references to all
data points in $S$ ordered lexicographically by there bucket code over
$R^{K}$. To navigate this array quickly, we build a trie over the bucket codes
of all keys in $S$ of depth at most $K$. Each vertex of the trie has two
attributes leftIndex and rightIndex. If the path from the root of the trie to
vertex $v$ is labeled $L(v)$, then leftIndex and rightIndex point to the left-
most and right-most elements in $A_{i}$ whose bucket code starts with $L(v)$.
We fix some more notation. For each point $q\in X$, we let
$v_{i,k^{\prime}}(q)$ be the vertex in trie $\mathcal{T}_{i}$ that is reached
by searching for the bucket code of $q$ on level at most $k^{\prime}$.
Furthermore, we let $\mathcal{T}_{i,k}(q)$ denote the set of keys that share
the same length $k$ prefix with $q$ in trie $\mathcal{T}_{i}$. We can compute
$|\mathcal{T}_{i,k}(q)|$ by subtracting $v_{i,k}(q).\texttt{leftIndex}$ from
$v_{i,k}(q).\texttt{rightIndex}+1$.

##  Appendix C Difficult Inputs for Standard LSH

Suppose we want to solve SRR using an LSH family $\mathcal{H}$. Assume that
the query point $q\in X$ is fixed. Given $n$, $t$ with $1\leq t\leq n$, and
$c>1$, we generate a data set $S$ by picking

  * •

$t-1$ points at distance $\epsilon$ from $q$, for $\epsilon$ small enough that
even concatenating $\lceil\frac{\log n}{\log 1/p_{2}}\rceil$ hash functions
from $\mathcal{H}$, we still have collision probability higher than $0.01$,

  * •

one point $x\in X$ with $\textnormal{dist}(q,x)=r$,

  * •

the remaining $n-t$ points at distance $cr$.

We call a set $S$ that is generated by the process described above a _$t$
-heavy input for SRR on $q$_. By definition, a $t$-heavy input has expansion
$c$ at query point $q$. We argue that the standard LSH approach is
unnecessarily slow on such inputs.

######  Observation 2.

Suppose we want to solve SRR in $(X,\textnormal{dist})$ using LSH with
parameters as in Theorem 1 with LSH family $\mathcal{H}$. Let $q\in X$ be a
fixed query point, and $S$ be a $t$-heavy input generated by the process
above. Then the expected number of points retrieved from the hash tables on
query $q$ in the LSH data structure is $\Theta(tn^{\rho})$.

###### Proof.

The standard LSH data structure is set up with $k=\lceil\frac{\log n}{\log
1/p_{2}}\rceil$ and $L=O(n^{\rho})$. $L$ repetitions are necessary to find the
close point at distance $r$ with constant probability. By the construction of
$S$, each repetition will contribute at least $\Theta(t)$ very close points in
expectation. So, we expect to retrieve $O(tn^{\rho})$ close points from the
hash tables in total. ∎

The process described above assumes that the space allows us to pick
sufficiently many points at a certain distance. This is for example true in
$\mathbb{R}^{d}$ with Euclidean distance. In Hamming space $\\{0,1\\}^{d}$ we
would change the above process to enumerate the points from distance
$1,2,\ldots$ and distance $cr+1,cr+2,\ldots$. If $d$ and $r$ are sufficiently
large, the same observation as above also holds for inputs generated according
to this process.

##  Appendix D Examples For Calculating $W_{\text{single}}$ for Certain Input
Distributions

In this section we discuss two examples to get a sense for quantity (2)
defined on Page 2.

#### Example 1 (Random Points in Hamming Space)

Fix a query point $q\in\\{0,1\\}^{d}$ and assume that our data set $S$
consists of $n$ uniform random points from $\\{0,1\\}^{d}$. Then the distance
$X$ from our query point is binomially distributed $\sim\text{Bin}(n,1/2)$. If
we choose bitsampling as in [20] as hash function, $\sum_{x\in
S}\Pr[h_{k}(q)=h_{k}(x)]$ is just
$n\textnormal{{E}}((1-X/d)^{k})=nd^{-k}\textnormal{{E}}(X^{k})$. This
coresponds to finding the $k$th moment of a binomial random variable, which we
can approximate by writing $X=d/2+Z_{d}\sqrt{d/4}$ where
$\textnormal{{E}}(Z_{d})=0$ and $Z_{d}\to Z$ converges to a standard normal.
Then
$n\textnormal{{E}}((X/d)^{k})=n2^{-k}\textnormal{{E}}(1+Z_{d}/\sqrt{d})^{k}=n2^{-k}(1+k\textnormal{{E}}(Z_{d})/\sqrt{d}+O(k^{2}/d))=n2^{-k}(1+O(k^{2}/d))$.
For dimension $d=\Omega(\log n)^{2}$ our algorithm would take
$k\approx\log_{2}n$ to get $\sum_{x\in S}\Pr[h_{k}(q)=h_{k}(x)]=O(1)$ and
$W=n^{\frac{\log 1/p_{1}}{\log 2}}$. Just as we would expect for LSH with
bitsampling and far points at distance $cr=d/2$.

#### Example 2 (Locally Growth-Restricted Data)

Another interesting setting to consider is when the data is locally growth-
restricted, as considered by Datar et al. [14, Appendix A]. This means that
the number of points within distance $r$ of $q$, for any $r>0$, is at most
$r^{c}$ for some small constant $c$. In [14], the LSH framework is changed by
providing the parameter $k$ to the hash function. However, if we fix $r=k$,
our algorithm will find a candidate set of size $W=O(\log n)$. So, our
algorithm takes advantage of restricted growth and adapts automatically on
such inputs.

The proof from [14] works, since they also inspect all colliding points. It is
easy to see that the integral $\int_{1}^{r/\sqrt{2}}e^{-Bc}c^{b}\text{ d}c$ is
still bounded by $2^{O(b)}$ when we start at $c=0$ instead of $c=1$, since the
integrand is less than 1 in this interval.

##  Appendix E Lemma 1

######  Lemma 1.

Let $x_{1}\geq x_{2}\geq\dots$ be a non-increasing series of real numbers. Let
$X_{n}=\sum_{k=1}^{n}x_{k}$ be the $k$th prefix sum. Then it holds:

$\displaystyle n/X_{n}$ $\displaystyle\leq(n+1)/X_{n+1}$ (5)
$\displaystyle\sum_{k=1}^{n}1/X_{k}$ $\displaystyle=O(n\log n/X_{n}).$ (6)

Here we have used the approximation for harmonic numbers,
$H_{n}=1+1/2+\dots+1/n=\log n+O(1)$, by Euler [16].

###### Proof.

Since the values $x_{k}$ are non-increasing, we have $X_{n}\geq nx_{n}\geq
nx_{k+1}$ and so

$\displaystyle(n+1)X_{n}\geq nX_{n}+nx_{n+1}=nX_{n+1}$

which is what we want for (5). For the second inequality, we use (5)
inductively, we get $a/X_{a}\leq b/X_{b}$ whenever $a\leq b$. Hence we can
bound (6) term-wise as

$\displaystyle\sum_{k=1}^{n}\frac{1}{X_{k}}\stackrel{{\scriptstyle\eqref{eq:rect}}}{{\leq}}\sum_{k=1}^{n}\frac{n}{kX_{n}}=\frac{n}{X_{n}}\sum_{k=1}^{n}\frac{1}{k}=\frac{n}{X_{n}}H_{n}=O(n\log
n/X_{n}).$

∎

We may notice that the bound is tight for $x_{1}=x_{2}=\dots=x_{n}$. Say
$x_{k}=1$ for all $k$, then $X_{k}=k$ and
$\sum_{k=1}^{n}1/X_{k}=H_{n}=\Omega(n\log n/X_{n})$. In the other extreme,
$\sum_{k=1}^{n}1/X_{k}\geq n/X_{n}$, which is sharp when $x_{1}=1$ and
$x_{k}=0$ for $k\geq 2$.

##  Appendix F Proof of Corollary 1, second part

When $t$ is small compared to $n$, the multiprobing radius $\alpha$ can be
made smaller. In this regime, we hence consider the following expansion:

$\displaystyle f(\alpha,p_{1})$
$\displaystyle=1+\frac{\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{1}\right)}{\operatorname*{H}(\alpha)}$
$\displaystyle=\frac{\operatorname*{H}(\alpha)+\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{1}\right)}{\operatorname*{H}(\alpha)+\operatorname*{D}\left(\alpha\;\middle\|\;1-p_{2}\right)}f(\alpha,p_{2})$
$\displaystyle=\frac{\log\frac{1}{p_{1}}+\alpha\log\frac{p_{1}}{1-p_{1}}}{\log\frac{1}{p_{2}}+\alpha\log\frac{p_{2}}{1-p_{2}}}f(\alpha,p_{2})$
$\displaystyle=\left(\frac{\log p_{1}}{\log
p_{2}}+\frac{\log\frac{p_{1}}{1-p_{1}}\log\frac{1}{p_{2}}-\log\frac{1}{p_{1}}\log\frac{p_{2}}{1-p_{2}}}{\left(\log\frac{1}{p_{2}}\right)^{2}}\alpha+O(\alpha^{2})\right)f(\alpha,p_{2})$
$\displaystyle=(\rho+\psi\alpha/\log{1/p_{2}}+O(\alpha^{2}))f(\alpha,p_{2}),$
(7)

for constants $\rho$ and $\psi$ depending on $p_{1}$ and $p_{2}$. This already
gives us that we are asymptotically optimal, as long as $\alpha
f(\alpha,p_{2})$ goes to 0 as $f(\alpha,p_{2})$ goes to $\infty$. To see that
this is indeed the case, we need the following asymptotics:

$\displaystyle\operatorname*{H}(\alpha)+\operatorname*{D}\left(\alpha\;\middle\|\;1-p\right)$
$\displaystyle=\alpha\log\tfrac{1}{1-p}+(1-\alpha)\log\tfrac{1}{p}$
$\displaystyle=\log\tfrac{1}{p}+O(\alpha)$
$\displaystyle\operatorname*{H}(\alpha)$
$\displaystyle=\alpha\log\tfrac{1}{\alpha}+(1-\alpha)\log\tfrac{1}{1-\alpha}$
$\displaystyle=\alpha\log\tfrac{1}{\alpha}+(1-\alpha)(\alpha-O(\alpha^{2}))$
$\displaystyle=\alpha(\log\tfrac{1}{\alpha}+1)+O(\alpha^{2})$ $\displaystyle
f(\alpha,p)$
$\displaystyle=(\operatorname*{H}(\alpha)+\operatorname*{D}\left(\alpha\;\middle\|\;1-p\right))/\operatorname*{H}(\alpha)$
$\displaystyle=\frac{\log\frac{1}{p}}{\alpha(\log\frac{1}{\alpha}+1)}+O(1/\log\tfrac{1}{\alpha})$
(8)

We would like invert (8) to tell us how fast $\alpha$ goes to zero, and plug
that into (7). To this end, we let $y=f(\alpha,p_{2})/\log\tfrac{1}{p_{2}}$.
Then it is clear that, at least asymptotically, $1/y^{2}<\alpha<1/y$. That
tells us $\alpha=y^{-\Theta(1)}$, and we can use this estimate to “bootstrap”
the inversion:

$\displaystyle\alpha$
$\displaystyle=\frac{1}{y(\log\frac{1}{\alpha}+1)}+O\left(\frac{\alpha}{y\log\tfrac{1}{\alpha}}\right)$
$\displaystyle=\frac{1}{y\left(\log\left[\frac{1}{\left(\frac{1}{y(\log\frac{1}{\alpha}+1)}+O(1/(y^{2}\log\tfrac{1}{\alpha}))\right)}\right]+1\right)}+O(1/(y^{2}\log\tfrac{1}{\alpha}))$
$\displaystyle=\frac{1}{y\left(\log\left[y(\log\frac{1}{\alpha}+1)\right]+\log\left[\frac{1}{1+O(1/y)}\right]+1\right)}+O(1/y^{2})$
$\displaystyle=\frac{1}{y\log y+O(y\log\log y)}+O(1/y^{2})$
$\displaystyle=\frac{1}{y\log y}+O\left(\frac{\log\log y}{y(\log
y)^{2}}\right)$ (9)

Plugging the result back into (7) we finally get:

$\displaystyle\log\textnormal{{E}}(W_{k})$ $\displaystyle=(\log
t)f(\alpha,p_{1})$ $\displaystyle=\log
t\left(\rho+\tfrac{\psi}{(\log{1/p_{2}})y\log y}+O\left(\frac{\log\log
y}{y(\log y)^{2}}\right)\right)f(\alpha,p_{2})$ $\displaystyle=\log
t\left(\rho f(\alpha,p_{2})+\frac{\psi}{\log
f(\alpha,p_{2})}+O\left(\frac{\log\log f}{(\log f)^{2}}\right)\right)$
$\displaystyle=\rho\log n+\log t\left(\frac{\psi}{\log\frac{\log n}{\log
t}}+O\left(\frac{\log\log\frac{\log n}{\log t}}{\left(\log\frac{\log n}{\log
t}\right)^{2}}\right)\right),$

as $\frac{\log n}{\log t}$ goes to $\infty$, i.e., $\tau$ goes to $0$.

##  Appendix G A Different Approach to Solving SRR with LSH

We reconsider the approach to solve SRR presented in Indyk’s Ph.D. thesis [19,
Page 12] under the name “enumerative PLEB”. While his method does not yield
good running times directly, it is possible to combine a number of very recent
results, to get running times similar to the ones achieved by our methods. We
give a short overview of this approach next. As in Section 4.1, we assume that
the number of points $t$ to report is known. At the end of this section we
describe a counting argument that is also contained in Indyk’s Ph.D. thesis
[19] that allows to solve the $c$-approximate spherical range counting problem
in an output-sensitive way.

Indyk describes a black-box reduction to solve SRR using a standard dynamic
data structure for the $(c,r)$-near neighbor problem. It works by repeatedly
querying an $(c,r)$-near point data structure (time $O(n^{\rho_{q}})$) and
then deleting the point found (time $O(n^{\rho_{u}})$), where $\rho_{q}$ and
$\rho_{u}$ are the query- and update-parameters. (For a standard LSH approach,
we have $\rho_{q}=\rho_{u}$.) This is done until the data structure no longer
reports any points within distance $r$. Due to the guarantees of an
$(c,r)$-near neighbor data structure, in the worst case the algorithm recovers
all points within distance $cr$, giving a total running time of
$t^{\prime}(n^{\rho_{q}}+n^{\rho_{u}})$, where $t^{\prime}$ is the number of
points within distance $cr$ which might yield a running time of
$\Omega(n^{1+\rho})$ as noticed in Appendix C.

Of course, we can never guarantee sublinear query time when $t^{\prime}$ is
large, but we can use a space/time-tradeoff-aware to improve the factor of
$t$, when the number of returned points is large.

We will assume the $(c,r)$-near neighbor data structure used in the reduction
is based on LSH. In [7], Andoni et al. describe a general data structure
comprising loosely “all hashing-based frameworks we are aware of”:

######  Definition 5 (List-of-points data structure).

  * •

Fix sets $A_{i}\subseteq\mathcal{R}^{d}$, for $i=1\ldots m$; with each
possible query point $q\in\mathcal{R}^{d}$, we associate a set of indices
$I(q)\subseteq[m]$ such that $i\in I(q)\Leftrightarrow q\in A_{i}$;

  * •

For a given dataset $S$, the data structure maintains $m$ lists of points
$L_{1},L_{2},\dots,L_{m}$, where $L_{i}=S\cap A_{i}$.

Having such a data structure, we perform queries as follows: For a query point
$q$, we scan through each list $L_{i}$ for $i\in I(q)$ and check whether there
exists some $p\in L_{i}$ with $\|p-q\|\leq cr$. If it exists, return $p$.

Data structures on this form naturally allow insertions of new points, and we
notice that if “Lists” are replaced by “Sets” we can also efficiently perform
updates.

To solve spherical range reporting, we propose the following query algorithm
for a point $q$:

  1. 1.

For each $i\in I(q)$ look at every point $x$ in $L_{i}$.

  2. 2.

If $\|x-q\|\leq r$, remove the point from all lists, $L_{j}$, where it is
present.

This approach allows for a very natural space/time-tradeoff. Assuming that
querying the data structure takes expected time $O(n^{\rho_{q}})$ and updates
take expected time $O(n^{\rho_{u}})$, the expected running time of the query
is $O(n^{\rho_{q}}+tn^{\rho_{u}})$. This asymmetry can be exploited with a
time/space tradeoff. In very recent papers [23, 13, 7] it was shown how to
obtain such tradeoffs in Euclidean space for approximation factor $c\geq 1$,
for any pair ($\rho_{q},\rho_{u}$) that satisifies

$\displaystyle c^{2}\sqrt{\rho_{q}}+(c^{2}-1)\sqrt{\rho_{u}}=\sqrt{2c^{2}-1}.$

To minimize running time, we may take exponents balancing
$T=n^{\rho_{q}}=tn^{\rho_{u}}$ and obtain

$\displaystyle\frac{\log T}{\log n}$
$\displaystyle=\frac{1}{2c^{2}-1}+\frac{c^{2}-1}{2c^{2}-1}\tau+\frac{c^{2}\left(c^{2}-1\right)}{2c^{2}-1}\left(2-\tau-2\sqrt{1-\tau}\right)\stackrel{{\scriptstyle\text{(*)}}}{{\leq}}\rho+(1-c^{4}\rho^{2})\tau,$

where $\tau=\frac{\log t}{\log n}$ and $\rho=1/(2c^{2}-1)$. Here (*) holds for
$t\leq\frac{2c^{2}-1}{c^{4}}$, and $T=O(t)$ otherwise. Note that this approach
requires knowledge of $t$. A visualization of the running time guarantees of
this approach is shown in Figure 5. Note that it requires knowledge of $t$ and
does not adapt to the expansion around the query point. It would be
interesting to see whether our adaptive methods could be used to obtain a
variant that is query-sensitive. Next, we discuss an algorithm for the
spherical range counting problem that can be used to obtain an approximation
of the value $t$ sufficient for building the data structure presented here.

$n^{0.6}$$n^{0.6}$$n^{0.8}$$n$$n^{1.2}$$n^{1.4}$$n^{0.8}$$n$$n^{0.4}$$n^{0.2}$$t$$W$Linear
ScanNaïve LSHList-of-pointsLower Bound Figure 5: Visualization of the running
time guarantees of the space/time-tradeoff list-of-points data structure for
$c=1.3$ in Euclidean space. The $x$-axis shows the value of $t$ compared to
$n$, the $y$-axis shows the expected work $W$. For comparison, we plotted the
lower bound of $O(n^{\rho}+t)$, the running time $O(tn^{\rho})$ of the naïve
LSH approach, and the running time $O(n)$ of a linear scan.

###  G.1 Solving $c$-approximate Spherical Range Counting

In [19, Chapter 3.6], Indyk shows that by performing $O((\log
n)^{2}/\alpha^{3})$ queries to independently built $(c,r)$-near neighbor data
structures, there is an algorithm that returns for a query $q$ a number $C$
such that $(1-\alpha)N_{r}(q)\leq C\leq(1+\alpha)N_{cr}(q)$ with constant
probability. The running time of the black-box reduction is $O(n^{\rho}(\log
n)^{2}/\alpha^{3})$. We show in this section that we can solve the problem in
time $O((n/t)^{\rho}\log n/\alpha^{3})$.

At the heart of the algorithm of [19] is a subroutine that has the following
output behavior for fixed $C$:

  1. 1.

If $N_{cr}(q)\leq C(1-\alpha)$, it will answer SMALLER

  2. 2.

If $N_{r}(q)\geq C$, it will answer GREATER

The subroutine uses $O(\log n/\alpha^{2})$ queries of independently build
$(c,r)$-near neighbor data structures, each built by sampling $n/C$ points
from the data set.

We can use the above subroutine to solve the spherical range counting problem
in time $O((n/t)^{\rho}\log n/\alpha^{3})$ time as follows. Half the size of
$\alpha$, and perform a geometrical search for the values
$t=n,(1-\alpha)n,(1-\alpha)^{2}n,\ldots$ . Assuming that a query on a data
structure that contains $n$ points takes expected time $O(n^{\rho})$ and
stopping as soon as the algorithm answers “Greater” for the first time, we
obtain a running time (without considering the $O(\log n/\alpha^{2})$
repetitions for each $t$ value) of

$\displaystyle\left(\frac{n}{n}\right)^{\rho}+\left(\frac{n}{n(1-\alpha)}\right)^{\rho}+\left(\frac{n}{n(1-\alpha)^{2}}\right)^{\rho}+\dots+\left(\frac{n}{t}\right)^{\rho}$
$\displaystyle\leq\left(\frac{n}{t}\right)^{\rho}+\left(\frac{n(1-\alpha)}{t}\right)^{\rho}+\left(\frac{n(1-\alpha)^{2}}{t}\right)^{\rho}+\dots$
$\displaystyle=\left(\frac{n}{t}\right)^{\rho}\frac{1}{1-(1-\alpha)^{\rho}}\leq\left(\frac{n}{t}\right)^{\rho}\frac{1}{\alpha\rho},$

which results in a total running time of $O((n/t)^{\rho}\log n/\alpha^{3})$.