Distance-Sensitive Hashing∗
Martin Aumüller

Tobias Christiani

IT University of Copenhagenmaau@itu.dk

IT University of Copenhagen
tobc@itu.dk

Rasmus PaghFrancesco Silvestri

IT University of Copenhagenpagh@itu.dk

University of Padova
silvestri@dei.unipd.it

ABSTRACT
Locality-sensitive hashing (LSH) is an important tool for managing
high-dimensional noisy or uncertain data, for example in connection with data cleaning (similarity join) and noise-robust search(similarity search). However, for a number of problems the LSH
framework is not known to yield good solutions, and instead ad hoc
solutions have been designed for particular similarity and distancemeasures. For example, this is true for output-sensitive similarity
search/join, and for indexes supporting annulus queries that aim
to report a point close to a certain given distance from the query
point.
In this paper we initiate the study of distance-sensitive hashing(DSH), a generalization of LSH that seeks a family of hash functions
such that the probability of two points having the same hash value isa given function of the distance between them. More precisely, givena distance space (X , dist) and a “collision probability function” (CPF)
f : R → [0, 1] we seek a distribution over pairs of functions (h, д)such that for every pair of points x, y ∈ X the collision probability
is Pr[h(x) = д(y)] = f (dist(x, y)). Locality-sensitive hashing is
the study of how fast a CPF can decrease as the distance grows.
For many spaces, f can be made exponentially decreasing evenif we restrict attention to the symmetric case where д = h. We
show that the asymmetry achieved by having a pair of functions
makes it possible to achieve CPFs that are, for example, increasingor unimodal, and show how this leads to principled solutions toproblems not addressed by the LSH framework. This includes anovel application to privacy-preserving distance estimation. We
believe that the DSH framework will find further applications inhigh-dimensional data management.
To put the running time bounds of the proposed constructions
into perspective, we show lower bounds for the performance of
DSH constructions with increasing and decreasing CPFs underangular distance. Essentially, this shows that our constructions are∗ The research leading to these results has received funding from the European ResearchCouncil under the European Union’s 7th Framework Programme (FP7/2007-2013) /ERC grant agreement no. 614331. Silvestri has also been supported by project SID2017
of the University of Padova.
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
PODS’18, June 10–15, 2018, Houston, TX, USA© 2018 Association for Computing Machinery.
ACM ISBN 978-1-4503-4706-8/18/06. . . $15.00
https://doi.org/10.1145/XXXXXX.XXXXXX

tight up to lower order terms. In particular, we extend existing
LSH lower bounds, showing that they also hold in the asymmetricsetting.

CCS CONCEPTS• Theory of computation → Randomness, geometry and discrete structures; Data structures design and analysis; • Information systems → Information retrieval;

KEYWORDS
locality-sensitive hashing; similarity search; annulus query
ACM Reference Format:
Martin Aumüller, Tobias Christiani, Rasmus Pagh, and Francesco Silvestri.
2018. Distance-Sensitive Hashing. In Proceedings of 2018 International Conference on Management of Data (PODS’18). ACM, New York, NY, USA, 17 pages.
https://doi.org/10.1145/XXXXXX.XXXXXX

1INTRODUCTION

The growth of data from a variety of sources that need to be managed and analyzed has made it increasingly important to design
data management systems with features that make them robust
and tolerant towards noisy data. For example: different texts representing the same object (in data reconciliation), slightly different
versions of a string (in plagiarism detection), or feature vectors
whose similarity reflects the affinity of two objects (in recommendersystems). In data management, such tasks are often addressed using
the similarity join operator [49].
When data sets are high-dimensional, traditional algorithmic
approaches often fail. Fortunately, there are general principles forhandling high-dimensional data sets. One of the most successful
approaches is the locality-sensitive hashing (LSH) framework by
Indyk and Motwani [32], further developed in collaboration with
Gionis [27] and Har-Peled [29]. LSH is a powerful framework for approximate nearest neighbor (ANN) search in high dimensions that
achieves sublinear query time, and it has found many further applications. However, for a number of problems the LSH framework is
not known to yield good solutions, for example output-sensitive
similarity search, and indexes supporting annulus queries returning
points at distance approximately r from a query point.
Motivating example. A classical application of similarity searchis in recommender systems: Suppose you have shown interest in aparticular item, for example a news article x. The semantic meaningof a piece of text can be represented as a high-dimensional feature
vector, for example computed using latent semantic indexing [25].
In order to recommend other news articles we might search the set

P of article feature vectors for articles that are “close” to x. But ingeneral it is not clear that it is desirable to recommend the “closest”
articles. Indeed, it might be desirable to recommend articles that areon the same topic but are not too aligned with x, and may provide
a different perspective [2].
Discussion. Unfortunately, existing LSH techniques do not allow us to search for points that are “close, but not too close”. In anutshell: LSH provides a sequence of hash functions h 1 , h 2 , . . . suchthat if x and y are close we have hi (x) = hi (y) for some i with constant probability, while if x and y are distant we have hi (x) = hi (y)only with small probability (typically 1/n, where n upper bounds
the number of distant points). As a special case, this paper discusses
techniques that allow us to refine the first requirement: If x andy are “too close” we would like collisions to occur only with verysmall probability. At first sight this seems impossible because we
will, by definition, have a collision when x = y. However, this objection is overcome by switching to an asymmetric setting where
we work with pairs of functions (hi , дi ) and are concerned withcollisions of the form hi (x) = дi (y).
More generally, we initiate the systematic study of the following
question: In the asymmetric setting, what is the class of functions
f for which it is possible to achieve Pr[h(x) = д(y)] = f (dist(x, y)),where the probability is over the choice of (h, д) and dist(x, y) is the
distance between x and y. We refer to such a function as a collision
probability function (CPF). More formally:
Definition 1.1. A distance-sensitive hashing (DSH) scheme for the
space (X , dist) is a distribution D over pairs of functions h, д : X →R with collision probability function (CPF) f : R → [0, 1] if foreach pair x, y ∈ X and (h, д) ∼ D we have Pr[h(x) = д(y)] =f (dist(x, y)).
The theory of locality-sensitive hashing is the study of decreasing
CPFs whose collision probability is high for neighboring points andlow for far-away points.

1.1

Our contributions

We initiate the systematic study of distance-sensitive hashing (DSH),
and in particular we:• Show tight upper and lower bounds on the maximum possible growth rate of CPFs under angular distance. This extends
upper and lower bound techniques for locality-sensitive
hashing to the asymmetric setting.
• Provide several DSH constructions that exploit asymmetry
between the functions д and h to achieve non-standard CPFs.
For example, for Hamming distance we show how to achieve
a CPF that equals any polynomial P : {0, . . . , d} → [0, 1] up
to a scaling factor.
• Present several motivating applications of DSH: Hyperplanequeries, annulus search, spherical range reporting, and privacypreserving distance estimation.
The lower bound for angular distance implies lower bounds for
Hamming and Euclidean distance DSH. It also shows that existing(asymmetric) LSH constructions used to search for vectors close toa given hyperplane [52] are near-optimal.
On the upper bound side, our constructions show that asymmetric methods are significantly more expressive than standard,
symmetric LSH constructions. Since asymmetric methods are often

applicable in cases where symmetric methods are used, it seems
relevant to re-assess whether such constructions can be improved,
even in settings where a decreasing CPF is desired.
Though our DSH applications do not lead to quantitative running time improvements compared to existing, published ad-hoc
solutions, we believe that studying the possibilities and limitationsof the DSH framework will help unifying approaches to solving“distance sensitive” algorithmic problems. We now proceed with amore detailed description of our results.
1.1.1 Angular distance. We consider monotonically increasing
CPFs for angular distance between vectors on the unit sphere Sd −1 .
It will be convenient to express distances in terms of dot products ⟨·, ·⟩ rather than by angles or Euclidean distances, with theunderstanding that there is a 1-1 correspondence between them.
The constructions rely on the idea of “negating the query point”:
leveraging state-of-the-art symmetric LSH schemes, we obtain DSH
constructions with monotone CPFs by replacing the query point
q by −q in a symmetric LSH construction. We initially apply thisidea in section 2.1 to Cross-Polytope LSH [8] getting an efficient
DSH with a monotonically decreasing CPF. We then show that amore flexible result follows with a variant of ideas used in the filter
constructions from [10, 14, 21]. The filter based approach contains
a parameter t that can be used for fine tuning the scheme. Thisparameter is exploited in the data structure solving the annulus
query problem (see section 6.2). More specifically, the filter based
approach gives the following result:
Theorem 1.2. For every t > 1 there exists a distance-sensitive
family D− for (Sd −1 , ⟨·, ·⟩) with a monotonically decreasing CPF fsuch that for every α ∈ (−1, 1) with |α | < 1 − 1/t we havetln(1/f (α)) = 1+α1−α 2 + Θ(log t).
2(1)

The complexity of sampling, storing, and evaluating (h, д) ∈ D− is2O(dt 4e t /2 ).
Note that in terms of the angle between vectors f is increasing,as desired. A corollary of Theorem 1.2 is that we can efficiently
obtain a CPF f such that ρ − = ln f (0)/ln f (α) ≤ 1−α1+α + o t (1). (Weuse ot (·) to indicate that the function depends only on t.) The value
ρ − measures the gap between collision probabilities (the larger thegap, the smaller ρ − ), and is significant in search applications. The
construction based on cross-polytope LSH haspthe same CPF as theconstruction stated in Theorem 1.2 with t = 2 log d.
It turns out that the value ρ − is optimal up to the lower-orderterm. To show this we consider vectors x, y ∈ {−1, +1}d that areeither 0-correlated or α-correlated (i.e., Pr[xi = yi ] = 1+α2 indepen√dently for each i). These are unit vectors up to a scaling factor d,
and for large d the dot product will be tightly concentrated aroundthe correlation. Since correlation is invariant under linear transformation, we may without loss of generality consider x, y ∈ {0, 1}d .
In section 3 we show the following lower bound:
Theorem 1.3. Let D be a distribution over pairs of functionsh, д : {0, 1}d → R, and define fˆ : [−1, 1] → [0, 1] as fˆ(α) = Pr[h(x) =д(y)] where x, y are randomly α-correlated and (h, д) is sampled ac1+α
cording to D. Then for every 0 ≤ α < 1 we have that fˆ(α) ≥ fˆ(0) 1−α .

Considering f (α) = limd →∞ fˆ(α), taking logarithms of the final
inequality we get that ρ − = ln f (0)/ln f (α) ≥ 1−α1+α , as desired. Theorem 1.3 standard (symmetric) LSH lower bounds [12, 37, 40] to an
asymmetric setting in the following sense: If there exists a too powerful asymmetric LSH family D+ , then by negating the query point
q we obtain a family D− with a monotone CPF that contradicts
the statement in Theorem 1.3. Observe that this reasoning cannot
be applied to standard LSH bounds since they do not handle theasymmetry we allow in our setting.
The proof of the theorem builds on the Reverse Small-Set Expansion Theorem [39] which, given subsets A, B ⊆ {0, 1}d and random
α-correlated vectors x, y, lower bounds the probability of the event[x ∈ A ∧ y ∈ B] as a function of α, |A| and |B|. Through a sequenceof inequalities we take the lower bound for pairs of subsets of spaceand extend it to hold for distributions over pairs of functions thatpartition space, yielding a surprisingly powerful and simple lower
bound.
1.1.2 DSH constructions. In the paper we also presents several
specific and general constructions for DSH families, in addition to
the constructions on the unit sphere discussed above.
In section 4.1, we apply the negating trick to the well-known
bit-sampling approach from [32] to get a simple construction ofa DSH family with an increasing CPF for Hamming distance. The
idea to obtain a DSH with increasing CPF is to use the bit-sampling
approach, but negate the bit that is picked from the query point.
We show that for small distances, the “collision probability gap”
between points at distance r and r /c, which is measured by thevalue ρ − = ln f (r )/ln f (r /c), is worse than if we were to map
bit strings onto the unit sphere and use the construction from
Theorem 1.2. This can be considered somewhat surprising because
the bit-sampling LSH family has an optimal collision probability gap
for the collision probability of points at distance r and cr , measured
by the value ρ + = ln f (r )/ln f (cr ), for small r [40].
The negating trick does not work for Euclidean space, since it
is potentially unbounded. Nevertheless, we describe in section 4.2
a DSH construction with a ρ − -value asymptotically matching theperformance of constructions on the unit sphere. The construction
is based on an asymmetric version of the classical LSH family for
Euclidean space by Datar et al. [23]: specifically, for parametersw ∈ R and k ∈ N, we letjkjk⟨a,x⟩+b⟨a,x⟩+bh : x 7→,
д : x 7→
+ k,
(2)
w
w
where b ∈ [0, w] is uniformly random and a ∼ N d (0, 1) is a ddimensional random Gaussian vector. We show that this method,
for a suitable choice of parameters w and k, provides a near-optimal
collision probability gap. This is surprising, since the classical construction in [23] is not optimal as an LSH for Euclidean space [7].
An example CPF for the above method is shown in Figure 1. As we
can see from this figure, the collision probaiblity decreases rapidly
on the left side of the maximum, but decreases more slowly on
the right side. In particular, this construction has a CPF that is not
monotone but unimodal.
In section 5, we extend our work by targeting the following natural question: let P (t) be a polynomial, does there exist a distancesensitive hash family with CPF f (t) = P (t)? We present two general approaches of constructing CPFs on the unit sphere and incollision probability
0.08

0.06

0.04

0.02

2

4

6

8

10

distance

Figure 1: Collision probability function of (2) with k = 3, w =1.

Hamming space that cover a wide range of such polynomials. The result for the unit sphere easily follows from asymmetric embeddings
previously used by Valiant [51] to solve the closest pair problem.
For Hamming space, we propose an approach based on bit-sampling
and polynomial factorization that obtains the desired CPF up to ascaling factor ∆ ≥ 1 that depends on the roots of the polynomial.
1.1.3 Applications. We briefly describe here some applicationsof DSH constructions. They are all straightforward given a DSH,
but give an idea of the versatility of the framework. We refer tosection 6 for formal statements and details.
• Hyperplane queries. The problem of searching a set ofunit vectors for a point (approximately) closest to a given
hyperplane can be solved using a CPF f , parameterized by
dot product, that peaks at f (0). This approach was previously
used in ad-hoc contructions, see [52].
• Approximate annulus search. The problem of searchingfor a point at approximately distance r from a query point
can be solved using a CPF that peaks at r . Previous solutions to this problem used a different, two-stage filtering
approach [41].
• Approximate spherical range reporting. Classical LSH
data structures are inefficient when many near neighbors
need to be found, since each neighbor may have a highcollision probability and may be “found” many times. A “stepfunction” CPF that is flat for small distances, and then rapidly
decreases implies good output-sensitivity. Again, previous
results addressing this problem were ad-hoc [4].
• Privacy preserving distance estimation. If two parties
want to compute the distance between private vectors, limiting the leakage of other information, secure multi-party
computations can be used (see e.g. [28]). Using “step function”
CPFs we can transform this kind of question into a question
about Hamming distance between vectors, for which much
more efficient protocols exist [24, 26].

1.2

Related work

A recent book by Augsten and Böhlen [13] surveys algorithms
for similarity join, with emphasis on data cleaning. Many of thecommonly used algorithms are heuristics with weak theoreticalguarantees, especially in high dimensions. Recently, however, asubstantial literature has been devoted the theoretical study ofsimilarity search and join in data management, e.g. [5, 30, 34, 54]. Allof these papers address particular similarity or distance measures,and their results are not directly comparable to those obtained inthis paper. In the following we review selected results from theLSH literature in more detail, referring to [6, 53] for comprehensive
surveys.
For simplicity we consider only LSH constructions that are isometric in the sense that the probability of a hash collision depends
only on the distance dist(x, y). In other words, there exists a CPF
f : R → [0, 1] such that Pr[h(x) = h(y)] = f (dist(x, y)). Almost all
LSH constructions whose collision probability has been rigorously
analyzed are isometric. Notable exceptions are recent data dependent LSH methods such as [11] where the LSH distributions, andthus the collision probabilities, depend on the structure of data.
ρ-values. Much attention has been given to optimal so-called ρvalues of locality-sensitive hash functions, where we consider nonincreasing CPFs. Suppose we are interested in hash collisions whendist(x, y) ≤ r 1 but want to avoid hash collisions when dist(x, y) ≥r 2 , for some r 2 > r 1 . The ρ-value of this setting (denoted in thispaper with ρ + ) is the ratio of the logarithms of collision probabilities
at distance r 1 and r 2 , i.e., the real number in [0, 1] such that f (r 1 ) =f (r 2 )ρ . The ρ-value determines the performance of LSH-based
data structures for the (r 1 , r 2 )-approximate near neighbor problem,see [29]. In many spaces a good upper bound on ρ can be given interms of the ratio c = r 2 /r 1 , but in general the smallest possible ρ
can depend on r 1 , r 2 , f (r 1 ), as well as the number of dimensions d.
In our applications it will be natural to consider the “dual” ρ-valuethat measures the growth rate that can be achieved when distanceincreases.
LSHable functions. Charikar [17] gave a necessary condition
that all CPFs in the symmetric setting must fulfill, namely, dist(x, y) =1 − Pr[h(x) = h(y)] must be the distance measure of a metric, andmore specifically this metric must be isometrically embeddable
in ℓ1 . In the asymmetric setting this condition no longer holds sincein general Pr[h(x) = д(x)] < 1.
Chierichetti et al. considered transformations that can be used tocreate new CPFs [18], and studied the decision problem to verify ifthere exists an LSH with given pairwise collision probabilities [19].
The transformations in [18, Lemma 7] are considered in a symmetric setting, but the same constructions applied in the asymmetricsetting give the following result, proved for completeness in Appendix D.1:
n be a collection of n distance-sensitive
Lemma 1.4. Let {Di }i=1n .
families with CPFs { fi }i=1(a) There exists a distance-sensitive family Dconcat with CPF f (x) =În
i=1 fi (x).
n over {D }, there exists(b) Given a probability distribution {pi }i=1iÍpa distance-sensitive family D with CPF f (x) = ni=1 pi fi (x).

An example application of Lemma 1.4 is shown in Figure 2. Interestingly, at least in the symmetric setting, the application of thislemma to a single CPF yields all transformations that are guaranteed to map a CPF to a CPF. Chierichetti et al. [20] recently extended
the study of CPFs in the symmetric setting to allow approximation,i.e., allowing the collision probability to differ from a target function
by a given approximation factor.
Asymmetric LSH. Motivated by applications in machine learning, Vijayanarasimhan et al. [52] presented asymmetric LSH methods for Euclidean space where the CPF is a decreasing functionof the dot product |⟨x, y⟩|. Shrivastava and Li [48] also explored
how asymmetry can be used to achieve new CPFs (increasing), in
settings where the inner product of vectors is used to measure closeness. Neyshabur and Srebro [38] extended this study by showingthat the extra power obtained by asymmetry hinges on restrictions
on the vector pairs for which we consider collisions: If vectors
are not restricted to a bounded region of Rd , no nontrivial CPF(as a function of inner product) is possible. On the other hand, if
one vector is normalized (e.g. a query vector), the performance ofknown asymmetric LSH schemes can be matched with a symmetricmethod. But in the case where vectors are bounded but not normalized, asymmetric LSH is able to obtain CPFs that are impossible forsymmetric LSH. Ahle et al. [5] showed further impossibility results
for asymmetric LSH applied to inner products, and that symmetric
LSH is possible in a bounded domain even without normalization
if we just allow collision probability 1 when vectors coincide.
Indyk [31] showed how asymmetry can be used to enable new
types of embeddings. More recently asymmetry has been used in
the context of locality-sensitive filters [10, 21] and maps [22]. The
idea is to map each point x to a pair of sets (h(x), д(x)) such that
Pr[h(x) ∩ д(y) , ∅] is constant if x and y are close, and very small
if x and y are far from each other. This yields a nearest neighbordata structure that adds for each vector x ∈ P the elements of h(x)to a hash table; a query for a vector q proceeds by looking up eachkey in д(q) in the hash table. One can transform such methods
into asymmetric LSH methods by using min-wise hashing [15, 16],
see [21, Theorem 1.4].
Recommender systems. Returning to our motivating example,
the topic of getting “interesting” recommendations using nearest
neighbor methods is not new. Abbar et al. [1] built a nearest neighbor data structure on a core-set of P to guarantee diverse query
results. However, this method effectively discards much of the dataset, so may not be suitable in all settings. Indyk [31] and Pagh etal. [41] proposed data structures for finding the furthest neighbor in Euclidean space, leveraging random projections and using
specialized data structures.
Privacy-preserving search. Privacy is an increasing concern
in connection with data analytics. Proximity information is potentially sensitive, since it may be used to reveal the source of adata point. Ideally we would like information-theoretical privacy
guarantees [3], but the standard technique of adding noise to data
does not seem to work well for proximity problems, since adding
noise merely shifts distances. Riazi et al. [46] considered answering
nearest neighbor queries without leaking the actual distance. They
showed that standard LSH approaches can compromise privacy
under a “triangulation” attack, however this risk can be reduced
by designing an LSH (symmetric) with a CPF that is “flat” in theregion of interest of an attacker. However, only rather weak privacy
guarantees were provided.

0.25

0.25

0.20

0.20

0.15

0.15

0.10

0.10

0.05

0.05

5

10

15

20

5

10

15

20

Figure 2: Composing several unimodal CPFs (left) to form a “step function” CPF (red curve on the right) using Lemma 1.4.

2

OPTIMAL ANGULAR DSHThis section describes DSH schemes with monotonically increasing and decreasing CPFs for the unit sphere that match the lower
bounds shown in the following section 3. As LSH are monotone
schemes too (i.e., CPF decreasing with distance or increasing withsimilarity), we refer to DSH schemes with the opposite monotonicity as anti-LSH (i.e., CPF increasing with distance or decreasing
with similarity).
For notational simplicity, the CPF is expressed as function of theinner product of two points, however it holds for other angular similarity and distance measures: on the unit sphere, inner product isequivalent to the cosine similarity and there is a 1-1 correspondencewith Euclidean distance and angular distance. Results on the unit
sphere can be extended to ℓs -spaces for 0 < s ≤ 2 through Rahimi
and Recht’s [44] embedding version of Bochner’s Theorem [45]applied to the characteristic functions of s-stable distributions as
used in [21].
We use the notation D− to denote a family with CPF that isdecreasing in the inner product between points, and D+ to denotea family with a CPF that is increasing in the inner product between
points. The idea behind the following constructions is to take astandard (symmetric) locality-sensitive hash family D+ for the unit
sphere with an increasing CPF, and transform it into a family D−
with a decreasing CPF by introducing asymmetry (i.e, by negating
the query value).

showed the following theorem, here reproduced in terms of innerproduct similarity.1
Theorem 2.1 (Theorem 1 in [8]). Let f be the CPF of hash family
CP + . Suppose that x, y ∈ Sd −1 such that ⟨x, y⟩ = α, where α ∈(−1, 1). Then,1−α1=ln d + O α (ln ln d).
lnf (α) 1 + α
To obtain a DSH with a monotonically decreasing CPF (in thesimilarity), we define the family CP − consisting of pairs (h − , д− )as follows: To sample a pair (h − , д− ) ∼ CP − , sample a functionh ∼ CP. For each point x ∈ X , set h − (x) = h(x) and д− (x) = h(−x).
This means that we invert the query point before applying thehash function. Intuitively, we map the point to the point on the
cross-polytope that is furthest away after applying the random
rotation.
Corollary 2.2. Let f be the CPF of hash family CP − . Supposethat x, y ∈ Sd −1 such that ⟨x, y⟩ = α, where α ∈ (−1, 1). Then,1+α1=
ln d + O α (ln ln d).
lnf (α) 1 − αProof. If ⟨x, y⟩ = α, then ⟨x, −y⟩ = −α. Since h − (x) = д− (y)corresponds to h(x) = h(−y), we can apply the result of Theorem 2.1
for similarity threshold −α.
□

2.2
2.1

Cross-polytope DSH schemes

Andoni et al. [8] described the following LSH family CP for the ddimensional unit sphere Sd −1 : To sample a function h ∼ CP, sample
a random matrix A ∈ Rd ×d in which each entry is independently
sampled from a standard normal distribution N (0, 1). To computea hash value of a point x, compute x̂ = Ax/∥Ax∥ ∈ Sd −1 and map
x to the closest point to x̂ among {±ei }1≤i ≤d , where ei is the i-th
standard basis vector of Rd . Intuitively, a random hash function
from CP applies a random rotation to a point and hashes it to its
closest point on the cross-polytope.
To formally define a DSH from CP, we sample (h + , д+ ) ∼ CP +by sampling h ∼ CP and set h + = д+ = h. In [8], Andoni et al.

Filter-based DSH schemes

Recent work on similarity search for the unit sphere [9, 11, 14, 21]
has used variations of the following technique: Pick a sequence ofrandom spherical caps and hash a point x ∈ Sd −1 to the index of
the first spherical cap in the sequence that contains x. By allowing
the spherical cap to have different sizes for queries and updates, it
was shown how to obtain space-time tradeoffs for similarity searchon the unit sphere that is optimal for random data [10, 21]. We
obtain a family D− with a decreasing CPF by taking a standard(symmetric) family with its sequence of spherical caps and introduce
asymmetry by negating the query point. Intuitively, this means thatfor (h, д) ∼ D− we let h use the original sequence of spherical caps
while д uses the spherical caps that are diametrically opposite to the
1 An inner product of α ∈ (−1, 1) between two vectors on the unit sphere corresponds

to Euclidean distance τ =p2(1 − α ).

ones used by h. We therefore get a collision h(x) = д(y) if and only
if x and y are contained in random diametrically opposite sphericalcaps. We proceed by describing the family D+ and the modificationthat gives us the family D− .
The family D+ takes as parameter a real number t > 0 and an
integer m that we will later set as a function of t. We sample apair of functions (h, д) from D+ by sampling m vectors z 1 , . . . , zm
where zi ∼ N d (0, 1). The functions h, д map a point x ∈ Sd −1 tothe index i of the first projection zi where ⟨zi , x⟩ ≥ t. If no suchprojection is found, then we ensure that h(x) , д(x) by mappingthem to different values. Formally, we set
h + (x) = min({i | ⟨zi , x⟩ ≥ t } ∪ {m + 1}),
д+ (x) = min({i | ⟨zi , x⟩ ≥ t } ∪ {m + 2}).
We use the idea of negating the query point to obtain a family
D− from D+ by setting:д− (x) = д+ (−x) = min({i | ⟨zi , x⟩ ≤ −t } ∪ {m + 2}).
The analysis of CPF for D− and D+ and the proof of Theorem 1.2
are provided in Appendix A.1.

3

LOWER BOUND FOR MONOTONE DSHThis section provides lower bounds on the CPFs of DSH families
in d-dimensional Hamming space under the similarity measure
simH (x, y) = 1 − 2 ∥x − y∥ 1 /d. These results extend to the unit
sphere and Euclidean space through standard embeddings.
Our primary focus is to obtain the lower bound in Theorem 1.3,
which holds for a CPF that is decreasing with the similarity. As
with our upper bounds for the unit sphere, re-applying the same
techniques also yields a lower bound for the case of an increasing
CPF in the similarity. The derivation of the lower bound is stated inappendix B. The proof combines the (reverse) small-set expansion
theorem by O’Donnell [39] with techniques inspired by the LSH
lower bound of Motwani et al. [37]. The reverse small-set expansion
theorem lower bounds the probability that random α-correlated
points (x, y) end up in a pair of subsets A, B of the Hamming cube,as a function of the size of these subsets. Two vectors, say (x, y), are
α-correlated if x is chosen uniformly at random from {0, 1}d andy is constructed by rerandomizing each bit from x independently
at random with probability 1 − α. The main contribution here is
to extend this lower bound for pairs of subsets of Hamming space
to our object of interest: distributions over pairs of functions thatpartition space.
We then use the above result to get a lower bound on the ρ − -valueof anti-LSH schemes for simH (x, y). We introduce the following
property:
Definition 3.1. Let D be a DSH family for (X , dist) with CPF
f . We say that D is (α − , α + , f − , f + )-decreasingly sensitive (resp.,(α − , α + , f − , f + )-increasingly sensitive) if it satisfies:• For α ≤ α − , we have that f (α) ≥ f − (respectively, f (α) ≤f − );• For α ≥ α + , we have that f (α) ≤ f + (respectively, f (α) ≥f + ).
We observe that if dist is a distance (resp., similarity) measure,then a decreasingly (resp., increasingly) sensitive DSH scheme corresponds to a standard LSH.

Theorem 3.2. Let 0 < α − < α + < 1 be constants. Then every(α − , α + , f − , f + )-decreasingly sensitive family D for ({0, 1}d , simH )must satisfy
ρ− =plog(1/f − )1 − α+≥− O( log(1/f + )/d).
log(1/f + )1 + α + − 2α −In the statement of Theorem 3.2 we may replace the properties
from Definition 3.1 that hold for every α ≤ α − and every α ≥ α +with less restrictive versions that hold in an ε-interval around α − , α +for some ε = od (1). Furthermore, if we rewrite the bound in termsof relative Hamming distances δ and δ /c where δ, c are constants,
we obtain a lower bound of 1/(2c − 1) − od (1) — an expression thatis familiar from known LSH lower bounds [12, 37].

4 HAMMING AND EUCLIDEAN SPACE DSH
4.1 Anti-LSH construction in Hamming space
Bit-sampling [32] is one of the simplest LSH families for Hamming
space, yet gives optimal ρ + -values in terms of the approximation
factor [40]. Its CPF is f (t) = 1 − t, where t is the relative Hamming distance. By using a function pair (x 7→ x i , x 7→ 1 − x i )where i ∈ {1, . . . , d} is random, we get a simple asymmetric DSH
family for Hamming space whose CPF f (t) = t is monotonicallyincreasing in the relative Hamming distance. We refer to this specific family as anti bit-sampling. For anti bit-sampling, we get thatρ − = ln f (r )/ln f (r /c) = Ω(1/ln c) as soon as the relative Hamming
distance r ∈ [0, 1] is smaller than 1/e. Perhaps surprisingly, anti
bit-sampling is not optimal and a better result, with ρ − = O(1/c),
follows by the anti-LSH schemes based on cross-polytope hashingand filters for the unit sphere in the following subsection. Similarly,
the DSH construction for Euclidean space in section 4.2 gives avalue of O(1/c) for ρ − .

4.2

A DSH construction in Euclidean space

A simple and elegant DSH family in Euclidean space is given bya natural extension of the LSH family introduced by Datar et al.
[23], where we project a point onto a line and split this line up
into buckets. Let k and w be two suitable parameters to be chosen
below. Consider the family Rk,w of pairs of functions (h, д) definedin equation (2), indexed by a uniform real number b ∈ [0, w] and ad-dimensional random Gaussian vector a ∼ N d (0, 1). We have thefollowing result whose proof is provided in Appendix C:
Theorem 4.1. Let r − and r be two real values such that 0 < r − < r ,and let c = r /r − . Then there exists a constant w = w(c) such that foreach k the family Rk,w satisfies
ρ− =ln(1/f (r ))1(1 + O k (1/k)) .
=ln(1/f (r − )) c 2

The proof uses that for a ∼ N d (0, 1) the inner product ⟨a, (x−y)⟩is distributed as N (0, ∆) for two points x and y at distance ∆. For
the hash values of x and y to collide, the inner product must roughly
lie in the interval [(k − 1)w, (k + 1)w]. Because we are free to choosek and w, we can move the interval into the tail of the N (0, ∆)distribution, where the target distances r and r /c have quadratic
influence in the exponents.

5

GENERAL CONSTRUCTIONS

So far we have focused our attention on constructions with monotone CPFs, which just represent one kind of DSH schemes. It isnatural to wonder if more advanced CPFs can be obtained. In thissection, we provide some results in this direction by describing
two constructions yielding a wide class of CPFs. We remark thatthese general constructions do not seem to provide any improved
constructions in the monotone case.
Angular similarity functions. We say that sim : [−1, 1] → [0, 1]
is an LSHable angular similarity function if there exists an hashfamily S with collision probability function sim(⟨x, y⟩) for eachx, y ∈ Sd −1 . For example, the function sim(t) = 1 − arccos(t)/π is
LSHable using the SimHash construction of Charikar [17].
Valiant [51] described a pair of mappings φ 1P , φ 2P : Rd → RD ,where D = O(d k ), such that φ 1P (x) · φ 2P (y) = P (⟨x, y⟩), for anyÍpolynomial P (t) = ki=0 ai t i . By leveraging this construction we
get the following result (with proof provided in Appendix D.2).
Theorem 5.1. Suppose that sim is an LSHable angular similarityÍÍ
function and that the polynomial P (t) = ki=0 ai t i satisfies ki=0 |ai |= 1. Then there exists a distribution over pairs (h, д) of functions suchthat for all x, y ∈ Sd −1 , Pr[h(x) = д(y)] = sim(P (⟨x, y⟩)).
The computational cost of a naïve implementation of the proposed scheme may be prohibitive when d k is large. However, byusing the so-called kernel approximation methods [42], we can innear-linear time compute approximations φ̂ 1P (x) and φ̂ 2P (y) thatsatisfy φ̂ 1P (x) · φ̂ 2P (y) = P (⟨x, y⟩) ± ε with high probability for agiven approximation error ε > 0.
Hamming distance functions. It is natural to wonder which CPFs
can be expressed as a function of the relative Hamming distancedh (x, y). A first answer follows by using the anti bit-sampling
approach from section 4 together with Lemma 1.4. This gives aÍscheme for matching any polynomial P (t) = ki=0 ai t i that satisÍk
fies i=0 ai = 1 and ai > 0 for each i.
In this section, we provide another construction that matches,
up to a scaling factor ∆, any polynomial P (t) having no roots witha real part in (0, 1). The scaling factor depends only on the rootsof the polynomial. We claim that such a factor is unavoidable in
the general case: indeed, without ∆, it would be possible to matchthe CPF 1 − t 2 for Hamming space, which implies ρ ≤ 1/c 2 incontradiction with the lower bound 1/c in [40]. (Nevertheless, it isan open question to assess how tight ∆ is.) We have the following
result that is proven in Appendix D.3:
Í
Theorem 5.2. Let P (t) = ki=0 ai t i , Z be the multiset of rootsof P (t), and ψ ≤ k be the number of roots with negative real part.
Then there exists a DSH family with collision probability Pr(h(x) =Îд(y)) = P (dh (x, y)) /∆ with ∆ = ak 2ψ z ∈Z, |z |>1 |zi |.
ÎThe construction exploits the factorization P (t) = ak z ∈Z (t −z) and consists of a combination of |Z | variations of bit-sampling
and anti bit-sampling. Although the proposed scheme may notreach the ρ-value given by the polynomial P (t), it can be used for
estimating P (d H (x, y)) since the scaling factor is constant and only
depends on the polynomial.

Finally, we observe that our scheme can be used to approximate
any function f (t) that can be represented with a Taylor series:
indeed, it is sufficient to truncate the series to the term that gives
the desired approximation, and then to apply our construction to
the resulting truncated polynomial.

6 APPLICATIONS
6.1 Hyperplane queries and annulus search
Approximate annulus search is the problem of finding a point in theset P of data points with distance in an interval [r − , r + ] from a query
point. On the unit sphere, hyperplane queries are a special case ofannulus queries where we want to find a point with inner productclose to 0 to a query point. This type of search has applications inmachine learning (see [33, 36]).
The ad hoc solution for this problem [41] in Euclidean space
works by first building an LSH data structure that aims to retrieve
points at distance at most r while filtering out points at distance atleast r + . In each repetition and in each bucket of the hash table, onebuilds a data structure that is set up to filter away points at distanceat least r − while preserving points at distance at least r . The latter
filtering can be thought of as applying an anti-LSH in each bucket.
For r − = r /c and r + = cr for a c ≥ 1, the construction in [41]2answers queries in time Õ(dn ρ+1/c ) and the data structure uses2
1+ρ+1/c+dn), where ρ describes the collision probability
space Õ(ngap of the LSH that is used, disregarding logarithmic terms by using
the Õ(.) notation.
Having access to a DSH family with a CPF that peaks inside[r − , r + ] and is significantly smaller at the ends of the interval gives
an LSH-like solution to this problem.
Theorem 6.1. Suppose we have a set P of n points, an interval[r − , r + ], a distance r ∈ [r − , r + ], and assume we are given a DSH
scheme with a CPF f that peaks inside [r − , r + ] and satisfies f (r ′ ) ≤1/n for all r ′ < [r − , r + ]. Then there exists a data structure that, given
a query q for which there exists x ∈ P with dist(q, x) = r , returns
x ′ ∈ P with dist(q, x ′ ) ∈ [r − , r + ] with probability at least 1/2. The∗
data structure uses space O(n 1+ρ /f (r ) + dn) and has query time∗O(dn ρ ), where ρ ∗ = log(1/f (r ))/log n.
Proof. The data structure is a straightforward adaptation of theconstruction of a near neighbor data structure using LSH. Associatewith each data point x and query point y the hash values h(x) andд(y), where (h, д) are independently sampled from the distancesensitive family. Store all points x ∈ S according to h(x) in a hashtable. Let y be the query point and let x be a point at distancer . Compute д(y) and retrieve all the points from S that have thesame hash value. If a point within distance [r − , r + ] is among thepoints, output one such point. We expect max{ f (r − )n, f (r + )n} ≤ 1collisions with points at distance at most r − or at least r + . The∗
probability of finding x is at least f (r ). Thus, L = 1/f (r ) ≤ n ρ
repetitions suffice to retrieve x with constant probability 1/e. If thealgorithm retrieves more than 8L points, none of which is in theinterval [r − , r + ], the algorithm terminates. By Markov’s inequality,
the probability that the algorithm retrieves 8L points, none of whichis in the interval [r − , r + ], is at most 1/8.
□

6.2

Annulus search on the unit sphereWe will construct a distance sensitive family D for solving theapproximate annulus search problem. Let D+ be parameterized byt + and let D− be parameterized by t − . To sample a pair of functions(h, д) from D we independently sample a pair (h + , д+ ) from D+
and (h − , д− ) from D− and define (h, д) by h(x) = (h + (x), h − (x)) andд(x) = (д+ (x), д− (x)).
Let f (α) denote the CPF of D. We would like to be able toparameterize D such that f (α) is somewhat symmetric around aunique maximum value of α. It can be verified from the definitionof D+ that p+ (−1) = 0 which implies that f (−1) = f (1) = 0. If we
ignore lower order terms and define γ > 0 by t − = γt + , then we
can see thatln(1/f (α)) ≈1 − α t +2 1 + α γ 2t +2
+
.
1+α 2
1−α 2

1.00
0.75
0.50
0.25
α

-1.00

-0.75

-0.50

-0.25

0.25

0.50

0.75

-1.00 -0.75 -0.50 -0.25

We note that the assumption f (r + ), f (r − ) ≤ 1/n in the theorem
is not critical: the standard technique of powering (see Lemma 1.4(a))
allows us to work with the CPF f (x)k for integer k, where k is thesmallest integer such that f (x)k ≤ 1/n.
We observe that this data structure improves the trivial scanningsolution when ρ ∗ = log(1/f (r ))/log(1/n) < 1, that is when f (r ) >f (r − ) and f (r ) > f (r + ). This is satisfied by unimodal distancesensitive hash families, that is when the CPF has a single maximum
at t ∗ and is decreasing for both t ≤ t ∗ and t ≥ t ∗ : as soon as t ∗ liesin the interval (r − , r + ) we obtain a data structure with sublinear
query time.
Obtaining a CPF that peaks inside of [r − , r + ] can be achieved by
combining a standard LSH family H with a DSH family A that has
an increasing CPF by means of powering each part. For example,
when combining a bit-sampling and an anti bit-sampling family,
concatenating k 1 bit-sampling and k 2 anti bit-sampling results in
the CPF f (t) = (1 − t)k1 t k2 . Setting k 1 = k 2 (1 − t)/t results in fpeaking at distance r . In general, for the value ρ ∗ in the statementof the theorem, this approach yields a bound of ρ ∗ ≤ ρ + + ρ − ,where ρ + and ρ − are the ρ-values of H and A, respectively. Thisis essentially the same as the running time guarantee of the ad hoc
data structure in [41] in Euclidean space.
In section 6.2, we show how to combine the two monotonic
constructions from section 2.2 on the unit sphere. A key ingredientof the construction is that we do not need the powering approachdescribed above but can combine a single LSH with a single antiLSH function and set the thresholds of each part accordingly. With
respect to hyperplane queries under inner product similarity, the resulting construction allows us to search a point set P of unit vectors
for a vector approximately orthogonal to a query vector q in time∗1−α 2 , where we guarantee to return a vector x
dn ρ +o(1) for ρ ∗ = 1+α2with ⟨x, q⟩ ∈ [−α, α] if an orthogonal vector exists. When applied
to search for approximately orthogonal vectors, our technique improves ρ-values of previous techniques, but the improvement is not
surprising in view of recent progress in angular LSH, see e.g. [8].
However, Theorem 6.4 in Section 6.2 supports searching a wide
range of different annuli and not just the ones centered aroundvectors with zero correlation. As an additional result, we obtain adefinition of an annulus in a space with bounded distances.

1.00

s=2
s=3
s=4

α max

Figure 3: Annuli as defined in Theorem 6.2 for every valueof α max and s = 2, 3, 4.
For simplicity, temporarily define a(α) = (1 − α)/(1 + α) > 0. Givena fixed γ , the equation a + γ 2 /a is minimized (corresponding toapproximately maximizing f (α)) when setting a = γ . Let α max ∈(−1, 1) and set γ = a max = (1 − α max )/(1 + α max ). To find values
α − < α max < α + where ln(1/f (α − )) ≈ ln(1/f (α + )) note that thiscondition holds for every s > 1 when we set a − = sa max and a + =(1/s)a max . We therefore parameterize D by α max ∈ (−1, 1) andt > 0 and set t + = t and t − = (1−α max )/(1+α max )t + . By combining
our bounds from Lemma A.5 with the above observations we areable to obtain the following theorem which immediately yields asolution to the approximate annulus search problem.
Theorem 6.2. For every choice of t > 0 and constant α max ∈(−1, 1) the family D satisfies the following: For every choice of constant s > 1 consider the interval [α − , α + ] defined to contain every α
1−α max
1−αmaxsuch that s1 1−α1+α max ≤ 1+α ≤ s 1+α max , then
• For α ∈ [α − , α + ] we have that

1 − α max t 2.
f (α) = Ω (1/t 2 ) exp −(s + 1/s)
1 + α max 2• For α < [α − , α + ] we have that

1 − α max t 2.
f (α) = O (1/t 2 ) exp −(s + 1/s)
1 + α max 2
The complexity of sampling, storing, and evaluating a pair of functions
2(h, д) ∈ D is O(dt 4e t /2 ).
See Figure 3 for a visual representation of the annulus for given
parameters α max and s.

We define an approximate annulus search problem for similarity
spaces and proceed by applying Theorem 6.2 to provide a solution
for the unit sphere, resulting in Theorem 6.4.
Definition 6.3. Let β − < α − ≤ α + < β + be given real numbers.
For a set P of n points in a similarity space (X , sim) a solution tothe ((α − , α + ), (β − , β + ))-annulus search problem is a data structurethat supports a query operation that takes as input a point x ∈ X
and if there exists a point y ∈ P such that α − ≤ sim(x, y) ≤ α +then it returns a point y ′ ∈ P such that β − ≤ sim(x, y ′ ) ≤ β + .
Theorem 6.4. For every choice of constants −1 < β − < α − <1−β − 1−β +− 1−α +
α + < β + < 1 such that 1−α1+α − 1+α + = 1+β 1+β we can solve the−+((α + , α − ), (β + , β − ))-annulus problem for (Sd −1 , ⟨·, ·⟩) with space usage dn + n1+ρ+o(1) words and query time dn ρ+o(1) where2c α + 1/c α≤c β + 1/c β
c + 1/crq
 1−α +
1−β −  1−β +−and we define 1 < c α < c β by c α = 1−α,c=β1+α − 1+α +
1+β
1+β ,
ρ=

−

and c = c β /c α .

6.3

Spherical range reporting

Approximate spherical range reporting [4] aims to report all points
in P within distance r from a query point. A common problem
with LSH-based solutions for reporting all close points is that the
CPF is monotonically decreasing starting with collision probability
very close to 1 for points that are very close to the query point.
On the other hand, many repetitions are necessary to find points
at the target distance r . This means that the algorithm retrieves
many duplicates for solving range reporting problems. The stateof-the-art data structure for range reporting queries [4] requires
O ((1 + |S ∗ |)(n/|S ∗ |)ρ ), where S ∗ is the set of points at distance at
most r + .
CPFs that have a (roughly) fixed value in [0, r ] and then decrease
rapidly to zero (so-called “step-function CPFs”) yield data structureswith good output sensitivity.
Theorem 6.5. Suppose we have a set P of n points and two distances r < r + . Assume we are given a DSH scheme with CPF f
where f (r ′ ) ≤ 1/n for all r ′ ≥ r + , and let f min = inf t ∈[0,r ] f (t),f max = supt ∈[0,r ] f (t). Then there exists a data structure that, given
a query q, returns S ⊆ {x ∈ P | dist(q, x) ≤ r + } such that for eachx ∈ P with dist(q, x) ≤ r , Pr[x ∈ S] > 1/2. The data structure∗uses space O(n 1+ρ + dn) and the query has expected running time∗ρO(dn + d |S | f max /f min ), where ρ ∗ = log(1/f min )/log(1/f (r + )).
Proof. We assume that we build a standard LSH data structure
as in the proof of Theorem 6.1 above. We use 1/f min repetitions suchthat each point within distance r is found with constant probability.
Each repetition will contribute O (1 + |S ∗ | f max ) points in expectation. Thus, the total cost will be O ((1 + |S ∗ | f max )/f min ) from which
the statement follows.
□
In short, Theorem 6.5 provides a better analysis of the performance of a standard LSH data structure that takes into account the
gap between f min and f max . Again, the assumption f (r + ) ≤ 1/n in
the theorem is not critical.

+

In particular, the theorem shows that if we have a constantbound on f max /f min the output sensitivity is optimal in the sensethat the time to report an additional close point is O(d) which is
the time it takes to verify its distance to the query point. Suchstep-function CPFs are implicit in the linear space extremes of thespace-time tradeoff techniques for near neighbor search [10, 21]. To
see why this is the case consider a randomized (list-of-points [10])data structure that solves the approximate near neighbor problem
using linear space. The data structure stores each point in exactly
one bucket. During a query L different buckets are searched. The
data structure has the property that near neighbors collide in atleast one bucket with constant positive probability. We can now
construct a family D where we sample (h, д) ∼ D by samplinga random (data-independent) data structure. We set h(x) equal tothe index of the single bucket that x would be stored in during
an update, and д(x) is set to the index of a random bucket outof the L buckets that would be searched during a query for x. If
the data structure guarantees finding an r -near neighbor, then theprobability of collision is Θ(1/L) for points x, y with dist(x, y) ≤ r .
Even though this theoretical construction gives optimal output
sensitivity, it is possible that a better value of ρ ∗ can be obtainedby allowing a higher space usage.

6.4

Privacy-Preserving Distance Estimation

Consider a database consisting of private information, for example
medical histories of patients, encoded as points in a space. We would
like to be able to search the database for points that are similar
to a given query point q without revealing sensitive information
about the data points, except whether there exists a point withina given distance r from q. This is nontrivial even in the case of asingle point, so we focus on the distance estimation problem: Is
the distance between points q and x at most r or not? Given x wewould like to answer this while revealing as little information as
possible about x. Secure multi-party computations can be used forthis (see e.g. [28]), but such protocols are not practical in general.
In contrast, the intersection of two sets can be computed efficiently
and in a private way that does not reveal anything about the items
not in the intersection [24, 26, 43].
We are going to allow false positives and approximate false negatives as follows. For an approximation factor c > 1, and parametersε, δ > 0:• If q and x have distance at most r , we say “Yes” with probability at least 1 − ε.
• If q and x have distance at least cr , we say “No” with probability at least 1 − δ .
Our approach is to reduce this problem to private set intersection,
as follows: For a parameter t to be chosen later, pick a DSH family
H with a step-function CPF with collision probability Θ(1/t) at
distances in [0, r ], and let ρ > 0 be the smallest constant such thatthe collision probability for distances larger than cr is O(t −1/ρ ).
Without loss of generality we may assume that hash values areO(log t) bits (if not, hash them to this number of bits using universal hashing, increasing the collision probability only slightly).
Now generate a sequence of O(t log(1/ε)) hash functions pairs(h 1 , д1 ), (h 2 , д2 ), · · · ∼ H , independently and consider the vectors(h 1 (x), h 2 (x), . . . ) and (д1 (x), д2 (x), . . . ). By definition the expected(component-wise) intersection size of the two vectors, i.e., the expected number of hash collisions, is O(log(1/ε)). This means thatthe intersection of the two vectors reveals O(log(1/ε) log t) bits of
information about the vectors in expectation. Also, by adjusting
constants, the probability that the intersection size is 0 when q
and x are close is at most ε. Thus, saying “Yes” if and only if theintersection is nonempty satisfies the first condition. On the other
hand, by a union bound the probability of a “Yes” when q and x
have distance at least cr is δ = O(t log(1/ε)/t 1/ρ ). Conversely, weneed t ≈ (1/δ )ρ/(1−ρ) to have false positive probability δ .
We observe that our approach has a stronger privacy constraint
than the result in [46]. Indeed, the step-function DSH preserves
privacy even if the q and x points are very close (e.g., q = x), since
the collision probability is almost equal in the range [0, r ]. On theother hand, a standard LSH, as the one adopted in [46], has an highcollision rate when the points are very close, revealing information
on near points.

7

CONCLUSION

We have initiated the study of distance-sensitive hashing, an asymmetric class of hashing methods that considerably extend the capabilities of standard LSH. We proposed different constructionsof such hash families and described some applications. Interestingly, DSHs provide an unique framework for capturing problems
that have been separately studied, like nearest neighbor [32], finding orthogonal vectors [52], furthest point query [41], and privacy
preserving search [46].
Though we settled some basic questions regarding what is possible using DSH, many questions remain. Ultimately, one would likefor a given space a complete characterization of the CPFs that canbe achieved, with emphasis on extremal properties. For example:
For a CPF that has f (x) = Θ(ε) for x ∈ [0, r ], how small a valueρ + (c) = log(f (r ))/log(f (cr )) is possible outside of this range? Additionally, our solution to the annulus problem works by combining
an LSH and an anti-LSH family to obtain a unimodal family: While
we know lower bounds for both, it is not clear whether combining
them yields optimal solutions for this problem. Finally, it is also ofinterest to consider other applications of DSH in privacy preserving
search and in kernel density estimation (e.g. [35]).
Acknowledgement. We thank Thomas D. Ahle for insightful
conversations.

A MONOTONE DSH CONSTRUCTIONS
A.1 Optimal monotone DSH schemes for theunit sphere√2straightforward to verify√ that Pr[Z 1 ≥ t ∧ αZ 1 + 1 − α Z 2 ≥ t] =2□
Pr[Z 1 ≥ t ∧ −αZ 1 + 1 − α Z 2 ≤ −t].
The collision probability for (h, д) ∼ D+ depends only on the
inner product α = ⟨x, y⟩ between the pair of points being evaluatedand is given by
Pr[h(x) ≤ m ∨ д(y) ≤ m]Pr[⟨z, x⟩ ≥ t ∧ ⟨z, y⟩ ≥ t].
Pr[⟨z, x⟩ ≥ t ∨ ⟨z, y⟩ ≥ t]

To see why this is the case first note that it is only possible thath(x) = д(y) in the event that h(x) ≤ m ∨ д(y) ≤ m. Conditioned on
this happening, consider the first i such that either ⟨zi , x⟩ ≥ t or⟨zi , y⟩ ≥ t. Now the probability of collision is given by Pr[⟨z, x⟩ ≥t ∧ ⟨z, y⟩ ≥ t |⟨z, x⟩ ≥ t ∨ ⟨z, y⟩ ≥ t].
To bound the CPF of D+ and D− , we use the following tailbounds for the standard normal distribution and the tail bounds by
Savage [47] for the bivariate standard normal distribution.
Lemma A.2 (Follows Szarek & Werner [50]). Let Z be a standard normal random variable. Then, for every t ≥ 0 we have that1
1 −t 2 /2
1 1 −t 2 /2e
≤ Pr[Z ≥ t] ≤ √e.
√
2π t + 1
2π t
Lemma A.3 (Savage [47]). Let α ∈ (−1,√1) and let Z 1 , Z 2 ∼N (0, 1). Define X 1 = Z 1 and X 2 = αZ 1 + 1 − α 2Z 2 . Then, forevery t > 0 we have that

1 (1 + α)2(2 − α)(1 + α) 1
t2
exp
−
√
1−α
1+α
t 2 2πt 2 1 − α 21 (1 + α)2t2< Pr[X 1 ≥ t ∧ X 2 ≥ t] <
exp
−
√
1+α
2πt 2 1 − α 21−Corollary A.4. By symmetry of the normal distribution theLemma A.3 bounds apply to Pr[X 1 ≥ t ∧ X 2 ≤ −t] when we replace all occurrences of α with −α.
We are now ready to bound the CPF for D+ .
Lemma A.5. For every t > 0 and α ∈ (−1, 1) the family D+
satisfies
1 t + 1 (1 + α)2
1 − α t2¯
f + (α) < f + (α) := √
exp −
,
√
1+α 2
2π t 2
1 − α2
3(2 − α)(1 + α) 1t ¯
f + (α) > 1 −f + (α) − 2e −t .
21−αt t +1

We initially bound the CPF of the family D+ , which translates to abound for D− through the following observation:

The complexity of sampling, storing, and evaluating a pair of functions
2(h, д) ∈ D+ is O(dt 4e t /2 ).

Lemma A.1. Given D+ and D− with identical parameters, wehave that f + (α) = f − (−α).

Proof. We proceed by deriving upper and lower bounds on thecollision probability.

Proof. A bivariate normally distributed variable with correlation α can√ be represented as a pair (X , Y ) with X = Z 1 andY = αZ 1 + 1 − α 2Z 2 where Z 1 , Z 2 are i.i.d. standard normal. By
the symmetry of the standard normal distribution around zero it isPr[⟨z, x⟩ ≥ t ∧ ⟨z, y⟩ ≥ t]Pr[⟨z, x⟩ ≥ t]

1 t + 1 (1 + α)2
1 − α t2
≤ √
exp
−
.
√
1+α 2
2π t 2
1 − α2f + (α) ≤We derive the lower bound in stages.

We define a probabilistic version of the collision probability function that we will state results for. Later we will apply concentration
bounds on the similarity between α-correlated pairs of points inorder to make statements about the actual CPF. We will use R to
denote the range of a family of functions which, without loss ofgenerality, we can assume to be finite.

Pr[h(x) = д(y)]Pr[⟨z, x⟩ ≥ t ∧ ⟨z, y⟩ ≥ t]Pr[⟨z, x⟩ ≥ t ∨ ⟨z, y⟩ ≥ t]Pr[⟨z, x⟩ ≥ t ∧ ⟨z, y⟩ ≥ t]≥
− Pr[h(x) > m].
2 Pr[⟨z, x⟩ ≥ t]
≥ (1 − Pr[h(x) > m])

The first part is lower bounded byPr[⟨z, x⟩ ≥ t ∧ ⟨z, y⟩ ≥ t]
(2 − α)(1 + α) 1
≥ 1−·
2 Pr[⟨z, x⟩ ≥ t]
1−α
t2


1 − α t2
1 1 (1 + α)2
exp −
.
√
√
1+α 2
2 2π t 1 − α 2
The probability of not being captured by a projection depends on
the number of projections m. In order to make this probability
negligible we can set m = ⌈2t 3 /p ′ ⌉ where p ′ denotes the lower
bound from Lemma A.2.
Pr[h(x) > m] ≤ (1 − Pr[⟨z, x⟩ ≥ t])m ≤ (1 − p ′ )2t /p ≤ e −2t .
3′

3

The bound on the complexity of sampling, storing, and evaluating apair of functions (h, д) ∈ D+ follows from having m = ⌈2t 3 /p ′ ⌉ =2
O(t 4e t /2 ) standard normal projections of length d to be sampled,
stored, and evaluated.
□
Combining the above ingredients we get the following results,
which implies Theorem 1.2 by Lemma A.1.

Definition B.3 (Probabilistic CPF). Let D be a distribution overpairs h, д : {0, 1}d → R and 0 ≤ α < 1. Then we define the probabilistic CPF fˆ : [0, 1] → [0, 1] byfˆ(α) =Pr

Before stating the main result, we prove the following technicallemma by showing that the pair of partitions induced by (h, д) ∈ D
minimizes a convex function of the probability of the parts, under
the additional constraint that Pr[h(x) = д(y)] = p, when all parts
are of equal volume and as small as possible.
Lemma B.4. For every 0 ≤ α < 1, every pair of functions h, д : {0, 1}d →R must satisfy

Theorem A.6. For every t > 1 there exists a distance-sensitive
family D+ for (Sd −1 , ⟨·, ·⟩) with a CPF f such that for every α ∈(−1, 1) satisfying |α | < 1 − 1/t we have that1−α t 2ln(1/f (α)) = 1+α 2 + Θ(log t).

(3)

Furthermore, the CPF of D+ is monotonically increasing, and thecomplexity of sampling, storing, and evaluating (h, д) ∈ D− is2O(dt 4e t /2 ).
A more careful analysis of the collision probabilities is requiredin order to combine the families D− and D+ to form a unimodal
family that can be used to solve the annulus search problem, see
Theorem 6.1. These results are stated in Appendix 6.2.

B LOWER BOUND FOR MONOTONE DSH
B.1 Proof of Theorem 1.3

1
1−α

Õ©
ª
­ Pr [h(x) = д(y) = i]®®
(x,y)
i ∈R «0-corr.
¬

Theorem B.2 (Rev. Small-Set Expansion [39]). Let 0 ≤ α ≤ 1.
Let A, B ⊆ {0, 1}d have volumes exp(−a 2 /2), exp(−b 2 /2), respectively, where a, b ≥ 0. Then we have that

1 a 2 + 2αab + b 2
Pr [x ∈ A, y ∈ B] ≥ exp −.
2
1 − α2(x,y)α -corr.

1+α
1−α

ª
©Õ
≥­
Pr [h(x) = д(y) = i]®®
(x,y)«i ∈R 0-corr.
¬

Proof. For i ∈ R define Ai = |h −1 (i)|/2d and Bi = |д−1 (i)|/2d .
ÍGiven some value of p = i Ai Bi we would like to choose the1Ípartition to minimize i (Ai Bi ) 1−α . In order to avoid complications
due to integrality constraints on the number of partitions, we definea weighted version of the problem with the property that its solution
never exceeds the solution of the original problem.

We begin by introducing the required tools from [39]. In the following, for A ⊂ {0, 1}d we refer to the quantity |A|/2d as the volume
of A.
Definition B.1. For 0 ≤ α ≤ 1 we say that (x, y) are α-correlated
if x is chosen uniformly at random from {0, 1}d and y is constructedby rerandomizing each bit from x independently at random withprobability 1 − α.

[h(x) = д(y)].

(h,д)∼D(x, y) α -corr.

minimizeÕsubject toÕ

w i ,Ai , B i

1w i (Ai Bi ) 1−αi

w i Ai Bi = p,iÕiw i Ai = 1,Õw i Bi = 1.

i

To ease notation and due to symmetry we will suppress different
values i, i ′ ∈ R in what follows. The Lagrangian for this problem.

and its first order partial derivatives are given byL(w i , Ai , Bi , λ A , λ B , λp )ÕÕ1=
w i (Ai Bi ) 1−α − λ A ( w i Ai − 1)ii− λB (

Õw i Bi − 1) − λp (iÕw i Ai Bi − p),i1∂L= (Ai Bi ) 1−α − λ A Ai − λ B Bi − λp Ai Bi ,
∂w i


α
∂L
1
= wi
(Ai Bi ) 1−α Bi − λ A − λp Bi ,
∂Ai
1−α


α
∂L
1
1−α
= wi
(Ai Bi ) Ai − λ A − λp Ai ,
∂Bi
1−α
Õ
∂L
=
w i Ai − 1,
∂λ A
i
Õ
∂L
=
w i Bi − 1,
∂λ B
i
Õ
∂L
=
w i Ai Bi − p.
∂λpi

We will proceed by deriving necessary conditions for a solution by
manipulating the first order conditions that all the partial derivatives are equal to zero. Consider the following sum:ÕÕÕ  ∂L 
1 Õ
w i (Ai Bi ) − λ A w i Ai − λp w i Ai Bi .
Ai =
∂A
1
−
α
i
i
i
i
i
Setting this equal to the corresponding sum for Bi allows us to∂L A = ∂L B allows us toconclude that λ A = λ B . Setting ∂Ai∂B i iiconclude that w i Ai = w i Bi . Consider now an i for which w i , 0
which implies that Ai = Bi . Further assume that Ai , 0 since thecase of Ai = Bi = 0 will not affect the problem. Setting the first∂L = 0 and ∂L = 0 equal to each other we getorder conditions ∂w
∂A
i

2
1−α

Ai

− 2λ A Ai − λp A2i =

i

1+α
1
Ai1−α − λ A − λp Ai .
1−αThis allows us to conclude that1+α2α
α
1 + α 1−αλA = −
Ai1−α , λp =
Ai .
1−α
1−α
Because the same derivation holds for every i, for i , j and under
the assumptions that w i , Ai , 0 and w j , A j , 0 it must hold that
Ai = A j . We can therefore restrict our attention to the case of asingle w i and Ai = Bi since all other solutions will result in thesame value in the optimum. From the first order conditions we havethat w i Ai = 1 and w i A2i = p and it is therefore easy to see that an
optimal solution is
w 1 = 1/p,

A1 = B 1 = p

with everything else set to zero. In the unweighted original formulation of the problem, this corresponds to the partitions induced byh, д each consisting of 1/p equal parts of volume p.
□

Proof. For a function h : {0, 1}d → R define its inverse imagedh −1 : R → 2 {0,1} by h −1 (i) = {x ∈ {0, 1}d | h(x) = i}. For a pairof functions (h, д) ∈ D and i ∈ R we define ah,i , bд,i ≥ 0 such that
2 /2) and |д−1 (i)|/2d = exp(−b 2 /2). For|h −1 (i)|/2d = exp(−ah,iд,ifixed (h, д) define fˆh,д (α) = Pr(x, y) α -corr. [h(x) = д(y)]. We obtaina lower bound on fˆ(α) as follows:"#Õˆf (α) =
EPr
[h(x) = д(y) = i](h,д)∼Di ∈R(x, y) α -corr.

1 ah,i + 2αah,i bд,i + bд,i
≥
E
exp −
2
1 − α2(h,д)∼D
i ∈R
"
2
2 !#
Õ
(2)
1 ah,i + bд,i
≥
E
exp −
2 1−α
(h,д)∼D
i ∈R

 1+α
1−α
(3)
1+α (4)Efˆh,д (0)≥Efˆh,д (0) 1−α ≥
"

(1)

2

2

!#

Õ

(h,д)∼D(h,д)∼D

1+α= fˆ(0) 1−α .

Here, (1) is due to Theorem B.2, (2) follows from the simple factthat a 2 + α(a 2 + b 2 ) + b 2 ≥ a 2 + 2αab + b 2 , (3) follows from theresult of an optimization problem in Lemma B.4, and (4) follows
from a standard application of Jensen’s Inequality.
□

B.2

Proof of Theorem 3.2

To prove Theorem 3.2, we analyze the CPF for a (r, cr, p, q)-increasingly
family for Hamming distance. Indeed, a (α − , α + , f − , f + )-decreasing
family for ({0, 1}d , simH ) is a (r, cr, p, q)-increasingly family for({0, 1}d , distH ), with α − = 1 − r /d and α + = 1 − cr /d.
Theorem B.6. For every constant ε > 0, every (r , cr , p, q)-increasingly
family A for {0, 1}d under Hamming distance with r ≤ (1 − ε)d/2
must satisfyplog 1/p1
ρ(A) =≥− O( (c/r ) log(1/q)).
log 1/q
2c − 1
Proof. Given A we define a distribution Â over pairs of funcˆ
tions ĥ, д̂ : {0, 1}d → R where dˆ ≤ d remains to be determined. We
sample a pair of functions (ĥ, д̂) from Â by sampling (h, д) from H
and setting ĥ(x) = h(x ◦ 1) and similarly д̂(x) = д(x ◦ 1) where 1ˆdenotes the (d − d)-dimensional
all-ones vector. We will now turnto the process of relating p to p̂ = fˆ(0) and q to q̂ = fˆ(α) for Â.
Let 0 < εp < 1 and set dˆ = ⌈2r /(1 − εp )⌉. Then by applying
standard Chernoff bounds we get
!
εp2 r
Pr
[dist(x, y) ≤ r ] ≤ exp −.
1 − εp 2(x,y) 0-corr.
ε2
For convenience, define δp = exp − 1−εp p r2 . We now have p̂ ≥(1 − δp )p.
In order to tie q̂ to q we consider the probability of α-correlated
We are now ready to state our main lemma that lower bounds
pointshaving distance greater than r /c. The expected Hammingˆˆf (α) in terms of f (0). This immediately implies Theorem 1.3.
ˆ − α)/2. We
distance of α-correlated (x, y) in dˆ dimensions is d(1Lemma B.5. For every distribution D over pairs of functions h, д : {0, 1}d →would like to set α such that the probability of the distance exceed1+α
R and every 0 ≤ α < 1 we have that fˆ(α) ≥ fˆ(0) 1−α .
ing r /c is small. Let X denote dist(x, y), then the standard Chernoff

1−εbound states that:
Pr[X ≥ (1 + ε)µ] ≤ e −ε µ/3 .
2For a parameter 0 < εq < 1 we set α such that the following issatisfied:
2r 1 − α(1 + εq )µ ≥ (1 + εq )≥ r /c.
1 − εp 21−εThis results in a value of α = 1 − 1+εqp c1 and we observe that
!
εq2 r
2
.
δq ≤ exp(−εq µ/3) ≤ exp −1 + εq 3c

We proceed by lower bounding ρ̂. Temporarily define 1 − ε ′ = 1+εqp
and observe thatln(1/p̂)1−α≥ln(1/q̂)1+α(1 − ε ′ )/c=2 − (1 − ε ′ )/c
1
ε′
ε′
≥
−
−
.
2
2c − 1 (2c − 1)2c − 1
We have thatε′ = 1 −It follows that1 − εp1 + εq − (1 − εp )=≤ εq + εp ,1 + εq1 + εqand combining these bounds results inq̂ ≤ (1 − δq )q + δq .

ln(1/p)1≥− 2(εq + εp − δq /q − δp ).
ln(1/q)2c − 1p
We can now set εq = εp = K · (c/r ) ln(1/q) for some universal
constant K to obtain Theorem 3.2.
□

Let us summarize what we know so far:p̂ ≥ (1 − δp )pq̂ ≤ (1 − δq )q + δq ≤ q(1 + δq /q)
0 < εp , εq < 1
εp2rδp ≤ exp −1 − εp 2
δq ≤ exp −
α =1−

εq2

B.3

r
1 + εq 3c!

1 − εp 1
1 + εq c1+αq̂ ≥ p̂ 1−α .
We assume that 0 < q < p < 1 and furthermore, without lossof generality we can assume that q ≤ 1/e due to the powering
technique (see Lemma 1.4(a)). In our derivations we also assume
that δp ≤ 1/2 and δq ≤ 1/(2e) such that δq /q ≤ 1/2. This will laterbe implicit in the statement of the result in big-Oh notation. From
our assumptions and standard bounds on the natural logarithm weare able to derive the following:ln(1 − δp ) ln(1/p̂)ln(1/p)≥ln(1/q)ln(1/q)ln(1/p̂)≥− 2δpln(1/q)ln(1/p̂)≥− 2δpln(1 + δq /q) + ln(1/q̂)ln(1 + δq /q)ln(1/p̂)≥1−− 2δpln(1/q̂)ln(1/q̂)ln(1 + δq /q)ln(1/p̂)≥−− 2δpln(1/q̂) ln(1/(1 + δq /q)q)

Theorem B.7 (Gen. Small-Set Expansion). Let 0 ≤ α ≤ 1. Let
A, B ⊆ {0, 1}d have volumes exp(−a 2 /2), exp(−b 2 /2) and assume
0 ≤ αb ≤ a ≤ b. Then,
1 a 2 + 2αab + b 2
Pr [x ∈ A, y ∈ B] ≥ exp −.
2
1 − α2(x,y)
Lemma B.8. For every distribution D over pairs of functions h, д : {0, 1}d →1−αR and every 0 ≤ α < 1 we have that fˆ(α) ≤ fˆ(0) 1+α .
Remark 1. The restriction from Theorem B.7 that 0 ≤ αb ≤ a ≤ b
can be ignored when attempting to upper bound fˆ in the proof of
Lemma B.8 as further asymmetry does not increase the probabilityof collision. The solution to the optimization problem underlying thelower bound in Lemma B.8 has a = b regardless.

(4)

In equation (4) we use the statement itself combined with our assumptions on p and q to deduce thatln(1/p)ln(1/p̂)≥.
ln(1/q)ln(1/q̂)We can re-apply the techniques behind Lemma B.5 and Theorem
3.2 to state similar results in the other direction where for α − < α +we are interested in upper bounding f (α + ) as a function of f (α − ).
This is similar to the well-studied problem of constructing LSH
lower bounds and our results match known LSH bounds [12, 37],
indicating that the asymmetry afforded by D does not help us
when we wish to construct similarity-sensitive families with monotonically increasing CPFs. Implicitly, this result already follows
from the space-time tradeoff lower bounds for similarity searchshown independently by Andoni et al. [10] and Christiani [21]. Aswith Lemma B.5, the following theorem by O’Donnell [39] is thefoundation of our lower bounds.

α -corr.

ln(1/p̂)≥− 2δq /q − 2δp .
ln(1/q̂)1>

The other direction!

We are now ready to state the corresponding result for similaritysensitive families.
Theorem B.9. Let 0 < α − < α + < 1 be constants. Then every(α − , α + , f − , f + )-sensitive family D for Hamming space ({0, 1}d , simH )must satisfyplog(1/f + )1 − α+≥− O( log(1/f − )/d).
log(1/f − )1 + α + − 2α −C

A DSH CONSTRUCTION IN EUCLIDEANSPACEProof of Theorem 4.1. For the sake of simplicity we assume
r = 1 in the analysis (otherwise it is enough to scale down vectors
accordingly). Let x and y be two points in Rd with distance ∆.
We know that for a ∼ N d (0, 1) the inner product ⟨a, (x − y)⟩ isdistributed as N (0, ∆). A necessary but not sufficient condition tohave a collision between x and y is that ⟨a, (x−y)⟩ lies in the interval[(k −1)w, (k +1)w]. Now, if t := ⟨a, (x−y)⟩ ∈ [(k −1)w, kw], then the
random offset b must lie in an interval of length t − (k − 1)w, putting⟨a, x⟩ and ⟨a, y⟩ − (k − 1)w into different buckets. For the interval[kw, (k + 1)w] similar observations show that b has to be chosen in√
2
an interval of length (k + 1)w − t. Let ϕ(t) = 1/ 2πe −t /2 be thedensity function of a standard normal random variable. Similarly
to the calculations in [23], the collision probability at distance ∆can be calculated as follows:
 



⟨a, y⟩ + b⟨a, x⟩ + b−=kf (∆) = Pr
w
w
∫ kw


ϕ(t/∆) t=− (k − 1) dt∆
w(k −1)w∫ (k +1)wϕ(t/∆) ϕ(kw/∆)
t 
+
k +1−
dt −
∆
w
∆
kw
∫ kw

t2  t1−=√e 2∆2− (k − 1) dtw
2π ∆ (k −1)w!
∫ (k +1)w
2
2 
t 
−t2
− (kw2)
2∆
2∆
k +1−
.
+
e
dt − ew
kw
We now proceed to upper bound ρ − by finding an upper boundon f (1/c) and a lower bound on f (1). Simple calculations give an
upper bound of2
2wc
f (1/c) ≤ √ e −(c(k −1)w ) /2 .
(5)
2π
For the lower bound, we only look at the interval t ∈ [kw, (k +1/2)w] and obtain the bound:∫ (k +1/2)w

t2
1
t 
f (1) ≥ √e− 2 k + 1 −
dt
w
2π kw
2
w
≥ √ e −((k +1/2)w ) /2 .
(6)
4 2π
Now we multiply the ratio of the logarithms of the right-hand sidesof (5) and (6) with c 2 and proceed to show that this term is boundedby 1 + O(1/k), √which shows the result. In the following, we set w
such that w ≤ 2π /(2c). We compute:2ln √w e −((k+1/2)w ) /2
4 2π
 c2

2wc e −(c(k −1)w )2 /2
ln √D GENERAL CONSTRUCTIONS
D.1 Transformation in [18] for asymmetricsetting: proof of Lemma 1.4
Proof. Let x, y be two arbitrary points from X . Part (a): Sample a pair (hi , дi ) from Di for each i ∈ {1, . . . , n} and set h(x) =(h 1 (x), . . . , hn (x)) and д(y) = (д1 (y), . . . , дn (y)). We observe thatnnÖÖPr(h(x) = д(y)) =Pr(hi (x) = дi (y)) =fi (dist(x, y)).
i=1

i=1

Part (b): Pick an integer i ∈ {1, . . . , n} according to {pi } at random.
Then sample a pair (hi , дi ) from Di . The hash function pair (h, д)
is given by (i, hi (x)) and (i, дi (y)). We observe thatnnÕÕPr(h(x) = д(y)) =pi
Pr (h(x) = д(y)) =pi fi (dist(x, y)).
i=1(h,д)∼Di

i=1

□

D.2

Angular similarity function

This section shows how to derive a distance sensitive scheme with
Ícollision probability sim(P (⟨x, y⟩)), when ki=0 |ai | = 1. Figure 4
gives some examples of functions that can be obtained from Theorem 5.1 using SimHash [17].
Proof of Theorem 5.1. Valiant [51] has shown how, for any
p preal degree-k polynomial p, to construct a pair of mappings φ 1 , φ 2 :pp
Rd → RD , where D = O(d k ), such that φ 1 (x) · φ 2 (y) = P (⟨x, y⟩).
For completeness we outline the argument here: First consider themonomial P (t) = ak t k . For x ∈ Rd , let x(k ) denote the vector of
dimension d k indexed by vectors i = (i 1 , . . . , i k ) ∈ [d]k , whereÎ(k )xi = kj=1 x i j . It is easy to verify that ⟨x(k) , y(k ) ⟩ = (⟨x, y⟩)k forp

all x, y ∈ Rd . With this notation in place we can define φ 1 (x) =
p
p
p
p
p
|ai | x(k ) and φ 2 (y) = (ai / |ai |) y(k ) which satisfy φ 1 (x) ·φ 2 (x) =ai (⟨x, y, )⟩k . The asymmetry of the mapping is essential to allow
a negative coefficient ak . To handle an arbitrary real polynomialÍ
P (t) = ki=0 ai t i we simply concatenate vectors corresponding toÍeach monomial, obtaining a vector of dimension ki=0 d i = O(d k ).
Observe that ||x(k ) ||22 = ⟨x(k ) , x(k) ⟩ = (⟨x, x, )⟩k = ||x||22k . ThisÍ p 2
pmeans that for ||x||22 = 1 we have ||φ 1 (x)|| 2 = ki=0 |ai | = 1,Íusing the assumption ki=0 |ai | = 1. Similarly, we have for ||y||22 = 1
p
Í
Í
p
p
that ||φ 2 (y)|| 2 = ki=0 (ai / |ai |)2 = ki=0 |ai | = 1. Thus, φ 1 andp
φ 2 map S d −1 to S D−1 .
Our family F samples a function s from the distribution S
corresponding to sim and constructs the function pair (h, д) withpph(x) = s(φ 1 (x)), д(y) = s(φ 2 (y)). Using the properties of the functions involved we haveppPr[h(x) = д(y)] = sim(⟨φ 1 (x), φ 2 (y)⟩) = sim(P (⟨x, y⟩)).

2π

=
=

−2 ln( √w ) + ((k + 1/2)w)24 2π

2wc )c 2 + ((k − 1)w)2−2 ln( √2π(k + 1/2)2(k − 1)2□−2 ln( √w ) + ((k + 1/2)w)2
≤

4 2π

D.3

((k − 1)w)2+ O(1/k 2 ) = 1 + O(1/k).
□

Hamming distance functions

Proof of Theorem 5.2. We initially assume that a 0 , 0 (i.e.,
0 is not a root of P (t)), and then remove this assumption at theend of the proof. We recall that a root of P (t) can appear withmultiplicity larger than 1 and that, by the complex conjugate root

0.8

0.60

0.7
0.55
0.6

0.5

0.50

0.4
0.45
0.3
0.40
-1.0

0.5

-0.5

1.0

-1.0

-0.5

0.5

1.0

Figure 4: Examples of collision probability functions obtained using Theorem 5.1. The polynomials used are t 2 , −t 2 , (−t 3 + t 2 −t)/3 (left), and (2t 2 − 1)/3, (4t 3 − 3t)/7, (8t 4 − 8t 2 + 1)/17, (16t 5 − 20t 3 + 5t)/41 (right).
theorem, if z = a + bi is a complex root then so is its conjugatez ′ = a − bi. We let Z be the multiset containing the k roots of P (t),with Z r + and Z r − being the multiset of positive and negative realroots, respectively, and with Zc being the multiset consisting ofpairs of conjugate complex roots. By factoring P (t), we get:ÖÖÖ
P (t) = ak(t − z) = |ak |(z − t)(t + |z|)·z ∈Zz ∈Z r +Öz ∈Z r −(t 2 − 2at + a 2 + b 2 ),(7)

z=a+bi ∈Z cÎÎwhere in the last step we exploited that ak z ∈Z r + (z−t) = |ak | z ∈Z r + (t−z) > 0. Indeed, P (t) is positive in (0, 1) and the multiplicative terms
associated with complex and negative real roots are positive in thisrange; this implies that the remaining terms are positive as well.
We need to introduce scaled and biased variations of bit-samplingor anti bit-sampling. Anti-bit sampling with scaling factor α ∈[0, 1] and bias β ∈ [0, 1] has the CPF f (t) = β/2 + αt/2 and isgiven by randomly selecting one of following two schemes: (1)with probability 1/2, the scheme is a standard hashing that maps
data and query points to 0 with probability β, and otherwise to
0 and 1 respectively; (2) with probability 1/2, the scheme is anti
bit-sampling where the sampled bit is set to 0 with probability
1 − α on both data and query points, or kept unchanged otherwise.
Similarly, bit-sampling with scaling factor α ∈ [0, 1] has the CPF
f (t) = (1 − αt) and is given by using bit-sampling, where thesampled bit is set to 0 with probability 1 − α on both data and query
points. (We do not need a biased version of bit-sampling.)
We now assign to each multiplicative term of (7) a scaled andbiased version of bit-sampling or anti bit-sampling as follows:• z is real and z < −1. We assign to z an anti bit-samplingwith bias 1 and scaling factor 1/|z| ≤ 1: the CPF is S 1 (t, z) =(1/2 + t/(2|z|)), and we have (t + |z|) = 2|z|S 1 (t, z).
• z is real and −1 ≤ z < 0. We assign to z an anti bit-samplingwith bias |z| ≤ 1 and scaling factor 1: the CPF is S 2 (t, z) =|z|/2 + t/2, and we have (t + |z|) = 2S 2 (t, z).
• z is real and z ≥ 1. We assign to z a bit-sampling withscaling factor 1/z ≤ 1: the CPF is S 3 (t, z) = (1 − t/z), and wehave (t − z) = zS 3 (t, z).

• (z, z ′ ) are conjugate complex roots and Real(z) < −1. Letz = a + bi and z ′ = a − bi. The assigned scheme has CPF

 !
a2
x
b2
1 2
+
S 4 (t, z) =+4(a 2 + b 2 ) a 2 + b 2 2|a| 2
and is obtained as follows: with probability b 2 /(a 2 + b 2 ), thescheme maps data and query points to 0 and 0 with probability 1/4, or to 0 and 1 with probability 3/4; with probability
a 2 /(a 2 + b 2 ), the schemes consists of the concatenation of
two anti bit-sampling with bias 1 and scaling factor 1/|a|.
Note that t 2 − 2at + a 2 + b 2 = 4(a 2 + b 2 )S 4 (t, z).
• (z, z ′ ) are conjugate complex roots and Real(z) ≥ 1. The
scheme is similar to the previous one where we use two
bit-sampling with scaling factor 1/a instead of the anti bitsampling. The CPF is


b2
a2 
x 2
S 5 (t, z) = 2+
1−aa + b 2 a2 + b 2, and we get t 2 − 2at + a 2 + b 2 = (a 2 + b 2 )S 5 (t, z).
• (z, z ′ ) are conjugate complex roots, −1 ≤ Real(z) ≤ 0,
and |z| = a 2 + b 2 ≥ 1. We assign the following scheme with
CPF


x2
|a|x
1
S 6 (t, z) =++.
4(a 2 + b 2 ) 2(a 2 + b 2 ) 4
With probability 1/4 the scheme maps data and query points
to 0; with probability 1/2, the scheme consists of anti bitsampling with bias 0 and scaling factor |a|/(a 2 + b 2 ) ≤ 1;with probability 1/4 the scheme consists√ of two anti bitsampling with bias 0 and scaling factor a 2 + b 2 each. We
have t 2 − 2at + a 2 + b 2 = 4(a 2 + b 2 )S 6 (t, z).
• (z, z ′ ) are conjugate complex roots, −1 ≤ Real(z) ≤ 0,
and |z| = a 2 + b 2 < 1. We use the scheme of the previous
point with different parameters, giving CPF
 2
x|a|x a 2 + b 2
S 7 (t, z) =
+
+
.
4
2
4
The scheme is the following: with probability 1/4, the scheme
is a standard hashing scheme where data points are always
mapped to 0 and where a query point is mapped to 0 with

probability a 2 +b 2 and to 1 with probability 1 − a 2 +b 2 ; withprobability 1/2, the scheme consists of anti bit-samplingwith bias 0 and scaling factor |a| ≤ 1; with probability 1/4,
the scheme consists of two anti bit-sampling with bias 0 andscaling factor 1 each. We have t 2 − 2at + a 2 + b 2 = 4S 7 (t, z).
Consider the scheme obtained by concatenating the above onesfor each real root and each pair of conjugate roots. Its CPF is S(t) =Î6 Î
i=1 z ∈Z i S i (t, z), where Z i contains root with CPF S i . Then, byletting ψ denote the number of roots with negative real part, we
get from Equation 7:
Ö©
ª
P (t) = ­2ψ |ak ||z| ® S(t) = ∆S(t).
z ∈Z, |Real(z) |>1 ¬«Consider now ak = 0 and let ℓ be the largest value such that
P (t) = t ℓ P ′ (x) with P ′ (0) , 0. We get the claimed result by
concatenating ℓ anti bit-sampling, which gives a CPF of x ℓ , and thescheme for P ′ (t) obtained by the procedure described above. □REFERENCES[1] Sofiane Abbar, Sihem Amer-Yahia, Piotr Indyk, Sepideh Mahabadi, and Kasturi R.
Varadarajan. 2013. Diverse near neighbor problem. In Symposium on Computational Geometry, SoCG ’13. 207–214. https://doi.org/10.1145/2462356.2462401[2] Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid
Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz,Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, andKe Yi. 2017. Research Directions for Principles of Data Management (Abridged).
SIGMOD Rec. 45, 4 (May 2017), 5–17. https://doi.org/10.1145/3092931.3092933[3] Dakshi Agrawal and Charu C. Aggarwal. 2001. On the Design and Quantificationof Privacy Preserving Data Mining Algorithms. In Proceedings of 20th Symposiumon Principles of Database Systems (PODS). ACM, New York, NY, USA, 247–255.
[4] Thomas D. Ahle, Martin Aumüller, and Rasmus Pagh. 2017. Parameter-freeLocality Sensitive Hashing for Spherical Range Reporting. In Proceedings of 28th
Symposium on Discrete Algorithms (SODA). 239–256. https://doi.org/10.1137/1.
9781611974782.16[5] Thomas D. Ahle, Rasmus Pagh, Ilya P. Razenshteyn, and Francesco Silvestri.
2016. On the Complexity of Inner Product Similarity Join. In Proceedings of
35th ACM Symposium on Principles of Database Systems (PODS). 151–164. https://doi.org/10.1145/2902251.2902285[6] Piotr Indyk Alexandr Andoni. 2017. Nearest Neighbors in High-Dimensional
Spaces. In Handbook of Discrete and Computational Geometry, Third Edition.
Chapman and Hall/CRC, 1133–1153.
[7] Alexandr Andoni and Piotr Indyk. 2006. Near-Optimal Hashing Algorithms
for Approximate Nearest Neighbor in High Dimensions. In Proceedings of 47th
Annual Symposium on Foundations of Computer Science (FOCS). 459–468. https://doi.org/10.1109/FOCS.2006.49[8] A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt. 2015. Practicaland optimal LSH for angular distance. In Proc. NIPS ’15. 1225–1233.
[9] A. Andoni, P. Indyk, H. L. Nguyen, and I. P. Razenshteyn. 2014. Beyond LocalitySensitive Hashing. In Proc. SODA ’14. 1018–1028.
[10] Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten.
2017. Optimal Hashing-based Time-Space Trade-offs for Approximate Near
Neighbors. In Proceedings of 28th Annual Symposium on Discrete Algorithms(SODA). 47–66. https://doi.org/10.1137/1.9781611974782.4[11] Alexandr Andoni and Ilya P. Razenshteyn. 2015. Optimal Data-Dependent Hashing for Approximate Near Neighbors. In Proceedings of 47th Annual Symposium on
Theory of Computing (STOC). 793–801. https://doi.org/10.1145/2746539.2746553[12] Alexandr Andoni and Ilya P. Razenshteyn. 2016. Tight Lower Bounds for DataDependent Locality-Sensitive Hashing. In Proceedings of 32nd International Symposium on Computational Geometry (SoCG). 9:1–9:11. https://doi.org/10.4230/
LIPIcs.SoCG.2016.9[13] Nikolaus Augsten and Michael H Böhlen. 2013. Similarity joins in relational
database systems. Synthesis Lectures on Data Management 5, 5 (2013), 1–124.
[14] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. 2016. New directions
in nearest neighbor searching with applications to lattice sieving. In Proceedingsof the 27th Symposium on Discrete Algorithms (SODA). 10–24. https://doi.org/10.
1137/1.9781611974331.ch2[15] Andrei Z. Broder. 1997. On the resemblance and containment of documents. In
Proceedings of Compression and Complexity of Sequences. IEEE, 21–29.

[16] Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig.
1997. Syntactic clustering of the web. Computer Networks and ISDN Systems 29,
8-13 (1997), 1157–1166.
[17] Moses Charikar. 2002. Similarity estimation techniques from rounding algorithms.
In Proceedings of 34th ACM Symposium on Theory of Computing (STOC). 380–388.
[18] Flavio Chierichetti and Ravi Kumar. 2015. LSH-preserving functions and theirapplications. Journal of the ACM (JACM) 62, 5 (2015), 33.
[19] Flavio Chierichetti, Ravi Kumar, and Mohammad Mahdian. 2014. The complexityof {LSH} feasibility. Theoretical Computer Science 530 (2014), 89 – 101. https://doi.org/10.1016/j.tcs.2014.02.030[20] Flavio Chierichetti, Alessandro Panconesi, Ravi Kumar, and Erisa Terolli. 2017.
The Distortion of Locality Sensitive Hashing. In Proceedings of ACM Conferenceon Innovations in Theoretical Computer Science (ITCS).
[21] Tobias Christiani. 2017. A Framework for Similarity Search with Space-Time
Tradeoffs using Locality-Sensitive Filtering. In Proceedings of 28th Symposium on
Discrete Algorithms (SODA). 31–46.
[22] Tobias Christiani and Rasmus Pagh. 2017. Set Similarity Search Beyond Minhash.
In Proceedings of 49th Annual Symposium on Theory of Computing (STOC), toappear.
[23] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Localitysensitive Hashing Scheme Based on P-stable Distributions. In Proceedings of the20th Annual Symposium on Computational Geometry (SoCG). ACM, 253–262.
[24] Emiliano De Cristofaro, Jihye Kim, and Gene Tsudik. 2010. Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model.. In Asiacrypt, Vol. 6477.
Springer, 213–231.
[25] Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, andRichard Harshman. 1990. Indexing by latent semantic analysis. Journal of theAmerican Society for Information Science 41, 6 (1990), 391.
[26] Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. 2004. Efficient Private
Matching and Set Intersection. In Proceedings of International Conference on the
Theory and Applications of Cryptographic Techniques (EUROCRYPT). 1–19.
[27] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search inHigh Dimensions via Hashing. In Proc. 25th International Conference on Very
Large Data Bases (VLDB). 518–529.
[28] Oded Goldreich. 2009. Foundations of cryptography: volume 2, basic applications.
Cambridge University Press.
[29] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. 2012. Approximate Nearest
Neighbor: Towards Removing the Curse of Dimensionality. Theory of Computing
8, 1 (2012), 321–350.
[30] Xiao Hu, Yufei Tao, and Ke Yi. 2017. Output-optimal Parallel Algorithms for
Similarity Joins. In Proceedings of Symposium on Principles of Database Systems(PODS). 79–90.
[31] Piotr Indyk. 2003. Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings. In Proceedings of 14th Symposium on Discrete
Algorithms (SODA). 539–545.
[32] Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards
Removing the Curse of Dimensionality. In Proceedings of 30th Annual ACM
Symposium on the Theory of Computing (STOC). 604–613.
[33] Prateek Jain, Sudheendra Vijayanarasimhan, and Kristen Grauman. 2010. Hashing
Hyperplane Queries to Near Points with Applications to Large-Scale Active
Learning. In NIPS.
[34] Michael Kapralov. 2015. 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. 329–342. https://doi.org/10.1145/2745754.
2745761[35] C. G. Lambert, S. E. Harrington, C. R. Harvey, and A. Glodjo. 1999. Efficient
On-Line Nonparametric Kernel Density Estimation. Algorithmica 25, 1 (1999),
37–57. https://doi.org/10.1007/PL00009282[36] Wei Liu, Jun Wang, Yadong Mu, Sanjiv Kumar, and Shih-Fu Chang. 2012. Compact
Hyperplane Hashing with Bilinear Functions. In ICML.
[37] R. Motwani, A. Naor, and R. Panigrahy. 2007. Lower Bounds on Locality Sensitive
Hashing. SIAM J. Discrete Math. 21, 4 (2007), 930–935.
[38] Behnam Neyshabur and Nathan Srebro. 2015. On Symmetric and Asymmetric LSHs for Inner Product Search. In Proceedings 32nd Conference on Machine
Learning (ICML). 1926–1934.
[39] Ryan O’Donnell. 2014. Analysis of Boolean Functions. Cambridge University
Press.
[40] Ryan O’Donnell, Yi Wu, and Yuan Zhou. 2014. Optimal lower bounds for localitysensitive hashing (except when q is tiny). ACM Transactions on Computation
Theory (TOCT) 6, 1 (2014), 5.
[41] Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, and Matthew Skala. 2017.
Approximate furthest neighbor with application to annulus query. Information
Systems 64 (2017), 152–162.
[42] Ninh Pham and Rasmus Pagh. 2013. Fast and scalable polynomial kernels via
explicit feature maps. In Proceedings of 19th International Conference on Knowledge
Discovery and Data Mining (KDD). ACM, 239–247.
[43] Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. 2017. Linear
Size Circuit-based PSI via Two-Dimensional Cuckoo Hashing. (2017). Manuscriptunder submission.
[44] Ali Rahimi and Benjamin Recht. 2007. Random Features for Large-Scale Kernel Machines. In Proceedings of 21st Annual Conference on Neural Information
Processing Systems (NIPS). 1177–1184.
[45] W. Rudin. 1990. Fourier Analysis on Groups. Wiley, New York.
[46] M. Sadegh Riazi, B. Chen, A. Shrivastava, D. Wallach, and F. Koushanfar. 2016.
Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on
Large-Scale Datasets. (2016). ArXiv:1612.01835.
[47] I. R. Savage. 1962. Mill’s Ratio for Multivariate Normal Distributions. Jour. Res.
NBS Math. Sci. 66, 3 (1962), 93–96.
[48] Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear
Time Maximum Inner Product Search (MIPS). In Proceedings of 27th Annual
Conference on Neural Information Processing Systems (NIPS). 2321–2329.
[49] Yasin N Silva, Walid G Aref, and Mohamed H Ali. 2010. The similarity join
database operator. In Proc. International Conference on Data Engineering (ICDE).
IEEE, 892–903.
[50] S. J. Szarek and E. Werner. 1999. A nonsymmetric correlation inequality for
Gaussian measure. Journal of Multivariate Analysis 68, 2 (1999), 193–211.
[51] Gregory Valiant. 2015. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. Journal of the ACM(JACM) 62, 2 (2015), 13.
[52] Sudheendra Vijayanarasimhan, Prateek Jain, and Kristen Grauman. 2014. Hashing
Hyperplane Queries to Near Points with Applications to Large-Scale Active
Learning. IEEE Trans. Pattern Anal. Mach. Intell. 36, 2 (Feb. 2014), 276–288.
https://doi.org/10.1109/TPAMI.2013.121[53] J. Wang, H. T. Shen, J. Song, and J. Ji. 2014. Hashing for Similarity Search: A
Survey. CoRR abs/1408.2927 (2014). http://arxiv.org/abs/1408.2927[54] Haoyu Zhang and Qin Zhang. 2017. EmbedJoin: Efficient Edit Similarity Joins via
Embeddings. In Proceedings of International Conference on Knowledge Discovery
and Data Mining (KDD). 585–594.