arXiv:1611.04999v1 [cs.DS] 15 Nov 2016

Massively-Parallel Similarity Join, Edge-Isoperimetry, and
Distance Correlations on the Hypercube
Paul Beame∗

Cyrus Rashtchian∗

Dept. of Computer Science & Engineering
University of Washington, Seattle
beame@cs.washington.edu

Dept. of Computer Science & Engineering
University of Washington, Seattle
cyrash@cs.washington.edu

November 16, 2016

Abstract
We study distributed protocols for finding all pairs of similar vectors in a large dataset. Our
results pertain to a variety of discrete metrics, and we give concrete instantiations for Hamming
distance. In particular, we give improved upper bounds on the overhead required for similarity
defined by Hamming distance r > 1 and prove a lower bound showing qualitative optimality
of the overhead required for similarity over any Hamming distance r. Our main conceptual
contribution is a connection between similarity search algorithms and certain graph-theoretic
quantities. For our upper bounds, we exhibit a general method for designing one-round protocols using edge-isoperimetric shapes in similarity graphs. For our lower bounds, we define a
new combinatorial optimization problem, which can be stated in purely graph-theoretic terms
yet also captures the core of the analysis in previous theoretical work on distributed similarity
joins. As one of our main technical results, we prove new bounds on distance correlations in
subsets of the Hamming cube.

1

Introduction

The task of reporting all pairs of similar items arises as a core computation in many applications.
Known as a similarity join in the database community, this task generalizes a relational join [1, 33,
53]. Similarity joins aid in the removal of near-duplicate data [16, 56, 57] and the search for images
with similar content [25, 39, 55]. In social media and other web applications, collaborative filtering
methods employ similarity joins to find related users and items [21, 26, 38, 60].
We give new parallel algorithms and prove new communication lower bounds for computing
a similarity join in a distributed, shared-nothing cluster. The similarity join problem is defined
relative to a metric space (V, ρ). Given an input set S of points in V and a distance threshold r, the
goal is to output all pairs x, y in S satisfying ρ( x, y) ≤ r. For the parallel version of this problem,
the input S starts equally partitioned among p processors. The challenge in designing an efficient
∗ Research

supported in part by NSF grants CCF-1217099 and CCF-1524246

1

parallel algorithm comes from outputting every close pair while balancing the workload among
the processors and completing the overall similarity join quickly.
Our algorithms and lower bounds are for a simultaneous model, where the processors have one
round to communicate input points before locally computing and outputting their portion of the
set of similar pairs. This model is consistent with previous work [4, 12, 49, 59], and with the fact
that each additional round of communication greatly increases the runtime in practice. We adopt
the natural assumption that the local computation time increases proportionally to the maximum
number of received vertices, and we focus on minimizing the latter quantity.
If there are p processors and n input points, an ideally balanced load with no replication of
data would send precisely n/p points to each processor. However, since every similar pair must
end up at some processor, some replication is required, and it will not be possible to achieve this
ideal. We measure the overhead of an algorithm as the ratio of the maximum number of points
any processor receives to the n/p ideal1 . To avoid large overhead in the worst case, any adequate
algorithm must employ a randomized load balancing strategy.
We exhibit new algorithms that improve on the overhead of the best previous similarity join
algorithms from [1, 2, 49] for Hamming distance on {0, 1}d with distance thresholds r > 1. Our
improvements are both quantitative in terms of the overhead bound and more general in terms
of the range of set sizes n for which they work. More fundamentally, we show that every randomized similarity join algorithm for Hamming distance r on {0, 1}d , even one that only weakly
approximates the similarity join, requires overhead dΩ(r) . This qualitatively matches the overhead
of the best algorithms. Moreover, ours is the first lower bound for similarity join that applies for
any r 6= 1, for any set size that is o (2d ), or for any algorithm that is only approximately correct.
We develop our improved similarity join algorithm as well as our lower bound by analyzing
certain graph-theoretic quantities of a similarity graph. For distance threshold r on {0, 1}d , the
Hamming similarity graph has edges between all pairs of points with Hamming distance at most r.
To approximate the similarity join, both endpoints of most edges of this graph must arrive together
at some processor. This criterion has a natural interpretation in graph terms. Let A1 , . . . , A p be
the sets of points that are sent to each of the p processors. Then, the collection of p subgraphs
induced by these sets must contain many of the edges in the input set. Since the input consists
of an arbitrary set of points, it follows that randomized algorithms correspond to distributions A
on approximate coverings ( A1 , . . . , A p ) of the edges of the similarity graph. We refer to such a
p-tuple as an edge-covering.
The design of edge-coverings connects the similarity join problem with the edge-isoperimetric
question in graph theory. To see this connection, notice two facts. First, our overhead measure is
minimized by reducing the number of input points contained by each set Ai . Second, an edgecovering is improved if each set Ai contains many edges relative to its size. Edge-isoperimetric sets
in a graph are sets of vertices of a given size that maximize the number of induced edges [14].
Therefore, we observe that it is good to build each set Ai as a union of randomly chosen edgeisoperimetric sets of suitable size in the similarity graph. In particular, we choose that size to
be roughly n/p, the ideal number of input elements sent to a processor. This ensures bounded
overhead and avoids imbalanced correlations of the input set with the edge-isoperimetric sets.
1 Overhead

resembles the replication rate used in analyzing MapReduce algorithms, but it does not depend on the
notion of reducer size [49], and thus it applies more generally than to just MapReduce algorithms.

2

In fact, this class of algorithms is a generic one that is suitable for use with any edge-transitive
similarity graph, such as the graphs defined by the Euclidean or Manhattan distance.
In the case of Hamming distance r = 1 on {0, 1}d , the optimal edge-isoperimetric sets are
near-subcubes [13, 29, 30, 40]. It is worth noting that random subcubes are a feature of the best
similarity join algorithm for this case [1, 49]. However, for r > 1, previous algorithms use other
methods [1, 2, 28, 44, 49, 56], and good edge-isoperimetric sets were not identified as suitable
constructs. Though the optimal edge-isoperimetric sets for r > 1 are not known, in our improved
similarity join algorithm we use Hamming balls (which interestingly are vertex-isoperimetric sets
for r = 1) and show that they are good approximations to optimal edge-isoperimetric sets.
Our general lower bound applies much more broadly than this edge-isoperimetric set construction. It holds for any randomized way of choosing sets ( A1 , . . . , A p ). We show that edgecovering and similarity join are hard even if the input set of points S is itself a random, subsampled Hamming ball.
The general intuition for our lower bound proof is that either the total number of elements
among the Ai is large, in which case large overhead follows immediately, or the sets Ai have a
large density of pairs of points in {0, 1}d of distance ≤ r. For this second case we derive our lower
bound on the overhead by proving a new connection between the density of different Hamming
distances of subsets on {0, 1}d . We show that for A ⊆ {0, 1}d that if there is a sufficiently high
density of pairs at Hamming distance r in A, then there is also a high density of pairs at much
larger Hamming distances. This property is likely to be of independent interest since it can be
viewed as a Sidorenko-type result [20, 24, 50] for shortest paths in the r-th power of the hypercube.

Related Work
We review two baseline algorithms for the similarity join problem under any metric. The first is a
√
randomized join algorithm and has overhead O( p). We discuss the details of this universal allpairs algorithm in Section 2. The second baseline (known as the “Ball-hashing-2” algorithm in [1])
works by randomly partitioning the points z of the metric space among the processors and sending
each input point x to the processors associated with all z at distance at most dr/2e from x. In other
words, processors are responsible for unions of balls of radius dr/2e. The expected overhead of
this algorithm is the size of balls of radius dr/2e in the metric space, which in the case of the
Hamming distance on {0, 1}d we denote by B(d, dr/2e) and is O(ddr/2e ).
Recent work [1, 2, 49] demonstrates improvements over the baseline algorithms for {0, 1}d
with Hamming distance. For distance r = 1, Afrati et al. [1] present an algorithm (called “Splitting”) based on a fixed grid of subcubes. They analyze how subcube dimensionality affects the
overall communication. We observe that choosing the dimension to be blog2 (n/p)c leads to an
edge-covering that achieves overhead O(d/ log(n/p)). For r > 1, in [1, 49] they also provide a variety of related algorithms. They analyze subcubes for larger distances, but this is not as effective
as the Ball-hashing-2 algorithm in terms of overall communication. Their Ball-hashing-1 algorithm
sends input points to processors based on balls of radius r centered at input points. However, the
Ball-hashing-1 communication scales with B(d, r ), worse than the Ball-hashing-2 algorithm.
The best previous algorithm for r > 1 is the A NCHOR P OINTS from [2], which improves
upon [1]. The basic building block of their algorithm is a covering code C of radius r, defined
as a set of points C in {0, 1}d with the property that every x ∈ {0, 1}d is within distance r of some
3

element of C . After randomly partitioning the elements z of the code C among the processors,
the algorithm sends each input point x to every processor associated with an element of the covering code that is at distance at most d3r/2e from x. In other words, processors are responsible
for unions of balls of radius d3r/2e. By using covering codes of density at most O(1/B(d, r )),
the work in [2] improves on the overhead of the Ball-hashing-2 algorithm by roughly a 2dr/2e factor. By basing our construction on nearly edge-isoperimetric sets and larger Hamming balls, our
algorithm improves the previous bound by factor of roughly ( 21 logd (n/p))dr/2e .
Similarity search algorithms often employ Locality Sensitive Hashing (LSH) [17, 28, 36]. An
LSH family is any distribution over hash functions such that near points map to the same bucket
with a higher probability than far points. For Hamming space, an example LSH family picks a
subset of k coordinates in {1, 2, . . . , d} and maps a vector to its k-bit projection on these coordinates [28]. LSH may be used as part of a similarity join algorithm by simply hashing the input
points, checking all pairs of points within the same hash bucket, and outputting the close pairs.
The success and approximation of such an algorithm depends on k and is amplified through independent trials.
The randomness in classical LSH schemes [17, 28, 36] leads to the possibility of both false
positives and false negatives, but recent work remedies things for false negatives [44, 48]. Their
LSH family for Hamming distance covers all close pairs with a correlated family of subcubes.
In a MapReduce setting, LSH buckets correspond to groups of points sent together. Hashing
a vector in {0, 1}d by choosing k coordinates corresponds to partitioning {0, 1}d into subcubes of
dimension k and determining the subcube to which the vector belongs. Achieving a balanced
load requires that each hash bucket contain a bounded number of vectors. In contrast, all-pairs
similarity search algorithms based on LSH ignore the sizes of each bucket. Instead they focus on
the total work done by the algorithm, and, over many rounds, maintain a counter for each vector
and simply abort after comparing it to too many far vectors [28, 45]. In fact, as we show, the
buckets maintained by LSH algorithms for distances r > 1 do not lead to the best load balance.
The approximate similarity join problem we study requires a sharp distance threshold – only
producing pairs with distance at most r; false positives can be easily filtered before being output. Therefore, our notion of approximation only refers to the fraction of false negatives. This
differs from problems such as Approximate Near Neighbor (ANN) search in terms of the notion
of approximation [27], where ANN benefits from allowing false positive pairs with distance ≤ cr,
where c > 1 determines the overall space usage and running time.
There are well-known lower bounds for LSH, such as [10, 41, 42], but these only apply for
r = Ω(d). Indeed, they employ analytic techniques, such as the Bonami-Beckner inequality, that
do not capture the small distances that are the focus of our work.
Panigrahy, Talwar, and Wieder [46, 47] prove cell-probe lower bounds for randomized algorithms solving the approximate near neighbor search problem (recent improvements appear
in [9]). Their approach resembles ours in that they consider (a generalization of) the edge expansion of the similarity graph for a metric space (i.e., the graph with edges connecting every pair of
points with distance at most r), though the specific application and techniques are different.
Recently, there has been work on proving strong conditional lower bounds (assuming the
strong exponential time hypothesis [32]) on the time complexity of computing all-pairs (approximate) nearest neighbors [3, 5, 6]. However these bounds do not apply to thresholded similarity

4

join or to our model, which measures the communication required for a single round.
There are also other kinds of algorithms for similarity search. In particular, there is a substantial body of work on the design and analysis of data structures that first preprocess the data and
then answer nearest-neighbor and range queries. Most of the analysis considers time complexity
and space usage for serial algorithms. Therefore, the majority of these results are orthogonal to
the study of distributed similarity joins and edge coverings (cf. [27]).
For metrics other than Hamming distance, objects resembling edge-coverings underlie stateof-the-art algorithms for similarity joins on datasets of real vectors: Working in Euclidean space,
Aiger, Kaplan, and Sharir [4] demonstrate an efficient edge-covering using randomly shifted and
rotated grids. In the `∞ metric, Lenhof and Smid [37] provide serial and shared-memory algorithms using a data-dependent partition of space into `∞ hypercubes. For angular distance, LSH
schemes use random half-spaces or spherical caps as randomized edge-coverings [8, 17, 28, 51, 54].
Many authors discovered the optimal edge-isoperimetric shape for the standard (distance one)
hypercube [13, 29, 30, 40]. Bezrukov’s survey [14] contains a thorough, modern treatment. Kahn,
Kalai, and Linial [34] consider the generalization for r greater than one, but leave asymptotic
results for all set sizes as a open question. Bollobás and Leader [15] prove a generalization of
the hypercube result for both Hamming and `1 distance on vectors over a larger alphabet (only
for distance one in both cases). Our edge-covering method implies that the Bollobás and Leader
result can be used to design protocols for this space.
Finally, in the combinatorics community, researchers have studied optimal coverings for pairs
of elements in designs [18, 31]. This relates to theoretical algorithms for parallel joins [12]. We
exploit the additional structure of the metric space to design vastly more efficient protocols and
algorithms than those for all-pairs joins when the number of processors is very large.

2

Similarity Graphs, Edge-Coverings, and Overhead

Similarity Graphs. Any undirected graph G = (V, E) can be viewed as defining a notion of
similarity on V in which similar pairs are joined by an edge. We study edge-transitive graphs, those
having automorphisms that make every neighborhood look like any other. We particularly focus
on the case that V is the set {0, 1}d equipped with the Hamming distance dist(u, v) that equals
the number of bits differing in u, v ∈ {0, 1}d . For a distance threshold r ∈ [d], let Γ≤r denote the
Hamming similarity graph with vertices {0, 1}d and edges connecting u, v whenever dist(u, v) ≤ r,
4
with self-loop edges for u = v. This regular graph has degree B(d, r ) = (dr) + (r−d 1) + . . . + d + 1.
For a subset A in {0, 1}d , let E≤r ( A) denote the set of edges in Γ≤r with both endpoints in A.
Similarly, define Γr as the graph with edges connecting vertices with distance exactly r, and define
Er ( A) as the set of edges in Γr with both endpoints in A. It will be convenient to define notation for
4
the average density of edges in the induced subgraphs Γ≤r [ A] and Γr [ A], so we define e≤r ( A) =
4 |E ( A )|
|E≤r ( A)|
and er ( A) = |r A| .
| A|

5

Similarity Join Algorithms and Overhead
We study a broad, natural class of one-round, p-processor similarity join algorithms. Each point x
in the input set S is sent to some non-empty subset of processors P( x ) ⊆ [ p]. The algorithm then
uses local operations at each destination processor to report all similar pairs among the elements
it receives from S. We allow the mapping P to depend on the (approximate) size n of the set S but
not S itself. The goal is to minimize the maximum number of elements received by any processor,
while ensuring that (almost) every similar pair in S goes to at least one processor.
The ideal load balancing would be a load of n/p elements per processor, but we show that
this is not always possible. Randomization is essential in defining P, since for any deterministic
mapping P any set S ⊆ P−1 (i ) for any i ∈ [ p] will yield a load of |S|. It is convenient to use
an equivalent and convenient perspective by considering the distribution ( P−1 (1), . . . , P−1 ( p))
of tuples of sets produced by the algorithm. This emphasizes the combinatorial aspects of the
problem, and is formalized in the following definition in terms of randomized edge-coverings.
Definition 2.1. A randomized ( p, δ)-edge covering for the n-subsets of Γ≤r is a distribution A on
p-tuples ( A1 , . . . , A p ) of subsets of {0, 1}d such that for every subset S ⊆ {0, 1}d of size n,
#
"
E

( A1 ,...,A p )∼A

|

[

E≤r ( Ai ∩ S)| ≥ δ · |E≤r (S)|.

i

There is an analogous definition of a ( p, δ)-edge covering for n-subsets of Γr with Er replacing E≤r .
As a way to capture the maximum load of randomized algorithms, our primary complexity
measure will be the expectation of the maximum ratio of | Ai ∩ S| to |S|/p.
Definition 2.2. Let A be a distribution on p-tuples ( A1 , . . . , A p ) of subsets of {0, 1}d . Let S ⊆ {0, 1}d
with p ≤ |S|. Define the overhead of A on set S,


p
overhead(A, S) =
max | Ai ∩ S| ·
,
E
|S|
( A1 ,...,A p )∼A i ∈[ p]
where the expectation is over the randomness of A. The n-overhead of A is defined as
overheadn (A) =

max

S⊆{0,1}d , |S|=n

overhead(A, S)

Note that defining the overhead in terms of the maximum value of | Ai ∩ S| is critical, since a
trivial algorithm that sends S entirely to a random processor achieves average load exactly |S|/p.
Any randomized ( p, δ)-edge covering A yields a natural one-round, p-processor, data-parallel
algorithm for computing a δ-approximate similarity join. First, choose ( A1 , . . . , A p ) ∼ A using
shared randomness. Then, send x to processor i whenever x ∈ Ai . In other words, on input S,
processor i receives Ai ∩ S for i ∈ [ p]. Over the random choices of the algorithm, this strategy
outputs in expectation at least a δ fraction of all pairs in S with Hamming distance at most r.
These local algorithms capture a very broad class of natural algorithms for similarity joins
including the ones discussed in the introduction. For example, in the ball-hashing-2 algorithm,
the sets A1 , . . . , A p are unions over a random partition of Hamming balls of radius dr/2e.
6

A Universal All-pairs Algorithm. As another example of such algorithms we present the other
baseline load-balancing algorithm mentioned in the introduction which works for any notion of
√
similarity and yields overhead O( p).
Proposition 2.3. There is a randomized 1-round local algorithm for any similarity measure that has ex√
pected per-processor load O(|S|/ p) on all sets S with p ≤ |S|.
Proof. Assume without loss of generality that p = (2q) for integer q. Choose a random mapping
h : {0, 1}d → [q]. Now send x ∈ {0, 1}d to processors indexed by the pair { h( x ), i } for every i ∈ [q]
not equal to h( x ). Every pair of inputs in S will be seen by some processor. The per-processor load
is almost surely O(|S|/q).
√
This yields a randomized ( p, 1)-edge-covering of {0, 1}d with overhead O( p) for all set sizes.
In Appendix B we note that for very small sets S, this bound essentially cannot be improved, even
on Γ≤r . For a limited number of available processors, this algorithm is still useful in practice, even
for large datasets. However, many important cases involve sets S that are a much larger portion of
{0, 1}d . In fact, some previous work on similarity join on the binary cube has often focused on the
case that the input set size is completely at the other extreme – a constant fraction of all possible
vectors. We consider a wide range of input sizes and not just these extremes.
Definition 2.4 (Main Complexity Measure). Let f ≤r (n, d, p, δ) be the minimum of overheadn (A) over
all randomized ( p, δ)-edge coverings for n-subsets of Γ≤r . Analogously define f r (n, d, p, δ) for Γr .
Lower bounds on f ≤r (n, d, p, δ) are lower bounds on the amount of overhead required for any
randomized p-processor 1-round local algorithm that approximately solves similarity join on the
binary cube with Hamming distance threshold r for subsets S ⊆ {0, 1}d of size n. Upper bounds
on f ≤r (n, d, p, δ) and f r (n, d, p, δ) will be particularly interesting when δ = 1, which implies no
error, or when δ is sufficiently close to 1, which implies the probability of missing any similar pair
in S is extremely small.
Comparison to MapReduce Measures. In MapReduce algorithms, there is a collection of individual tasks called reducers that are randomly assigned to one of the p processors. Previous
similarity join algorithms (as well as our edge-isoperimetric algorithm) define reducers for each
subset R1 , . . . , RK of {0, 1}d for some K  p. Then, during a shuffling phase, the sets A1 , . . . , A p
are formed randomly as unions of some of the { R j }. The key complexity measure analyzed in the
previous work [1, 2, 49] is the replication rate, defined as the average number of reducers to which
each point is sent. We claim that overhead is a better measure.
The replication rate is a useful measure only when the reducers are small enough that they
can be mapped randomly and uniformly to yield tasks that are nicely load-balanced across the
processors. Our measure, overhead, captures a much wider class of algorithms than replication
rate can. Moreover, in the regime where replication rate is a useful measure, overhead essentially
equals replication rate. The main advantage of overhead concerns very large reducers. For example, if one reducer was responsible for essentially the whole input, the replication rate would be
one, but this algorithm would behave badly in practice and has the worst possible overhead of p.
Therefore, overhead both captures the lower bounds using replication rate and defines a measure
of load balancing for large reducers.
7

3

Our Results

Theorem 3.1. Let 0 < δ ≤ 1 and r, d, n, p be such that r ≤ d, p ≤ n ≤ 2d , and γ = logn p.
(a) For all integers k with dr/2e ≤ k ≤ (1 − γ) logd n there is a MapReduce algorithm witnessing the
bound
)
(

  dr/2e
1
d
·
, 9 log2 p
f ≤r (n, d, p, δ) ≤ max 6 · 2dr/2e ln
1−δ
k
The algorithm has reducer size B(d, k ), and with probability 1 − 2−d , it maps each input to at most
(
  dr/2e )

1
d
7 · max d ln 2, 6 · 2dr/2e ln
·
1−δ
k
processors. Moreover, with δ = 1 − 1/n3 , the edge-covering of the input is error-free with probability
at least 1 − 1/n.
√
√
(b) There is constant cδ > 0 such that for every r, n, d, p, δ with r ≤ d/2, n ≥ dr log2 d , and δ ≥ 4/ d,
f ≤r (n, d, p, δ) ≥ (cδ /r )r · (d/ log2d n)γr/2 .
Further, if γr ≤ 1 then
f ≤r (n, d, p, δ) ≥ (cδ /r )r · (d/ logd n)γr .
(c) The bounds given in (a) and (b) also hold with f ≤r (n, d, p, δ) replaced by f r (n, d, p, δ).
Observe that our lower bound in (b) (in its range of applicability) is qualitatively very similar
to the upper bound in (a) with maximal choice of k, especially as the number of processors approaches the set size. The only previous lower bound on replication rate or overhead for similarity
join [49] used the edge-isoperimetric bound for r = 1 to derive a lower bound of (log2 n)/ log2 q
where q is an upper bound on the reducer size for input sets of size n that are dense subsets of a
subcubes; however, for q as large as n/p, the regime in which our bounds apply, this only yields a
nearly trivial lower bound of 1/(1 − γ).
We outline the upper bound improvements compared to previous algorithms [1, 49, 2]. Our
upper bound with maximal k comes from an algorithm with overhead O(2d/ logm (n/p))dr/2e .
This improves on the Ball-hashing-2 algorithm [1], which has overhead (2d/r )dr/2e using reducers of size B(d, dr/2e). Our algorithm also improves over the A NCHOR P OINTS algorithm
in [2], which has overhead O( B(d, d3r/2e)/B(d, r )), approximately (d/r )dr/2e , using reducers of
size B(d, d3r/2e). We finally note that the subcube algorithm [1, 49] has good overhead when
r = 1 and is not improved by our results, but it is not competitive for r > 1.
Our algorithm is best for large k with reducers of size B(d, k ) ≈ n/p. We improve the overhead
by up to a ( 21 logd (n/p))dr/2e factor, taking advantage of larger reducers to obtain better bounds.
√
√ 2
For a comparison using a natural range of parameters, consider d = log2 n and p = 2 d =
8

√

n. Our overhead for even r scales like (d log2 d)r/4 , which improves over the best previous
algorithm by a factor of roughly (d/r2 log2 d)r/4 .
Our algorithm is nearly-optimal for n = 2Θ(d) and p = nγ for constant γ < 1. In this case,
choosing δ = 1 − 1/23d we obtain an algorithm that is almost certainly correct and has overhead
only 2O(r) d logdr/2e d, since log2 p ≤ d. This is a significant improvement over the best previous
algorithm [2] which has overhead and replication rate (d/r )dr/2e in this regime.

4

Randomized Edge-Coverings using Edge-Isoperimetric Sets

In this section, we describe our randomized edge-covering for Γ≤r with overhead achieving the
upper bound in Theorem 3.1. This randomized edge-covering defines a one-round, data-parallel
protocol for reporting all pairs in S ⊆ {0, 1}d with Hamming distance at most r. It thus also
provides a MapReduce algorithm for Hamming similarity joins.
We begin with our general protocol for arbitrary edge-transitive similarity graphs, since it is
easy to state and explains the intuition. We then specialize this general protocol to Hamming
distance and provide the specific analysis in this case.

General Edge-Transitive Graph Covering
We build a randomized ( p, δ)-edge-covering for G using unions of random translates of a fixed
set U ∗ ⊆ V. An edge-isoperimetric set of size s is any set U ∗ (s) of vertices in G that maximizes
the number of edges among all induced subgraphs with s vertices. We will use translates of
4
U ∗ = U ∗ (s) for s ≤ n/p. Let π be a graph automorphism on G. Define π (U ∗ ) to be the set of
vertices π ( x ) for each x ∈ U ∗ . By edge-transitivity, π (U ∗ ) contains the same number of edges as
U ∗ does.
To construct the ( p, δ)-edge covering, we choose a parameter L and choose Lp automorphisms
π1 , . . . , π Lp of G uniformly at random, and define
Ai =

[

π j (U ∗ ) .

j ≡ i mod p

With Lp large enough compared to the ratio of the number of edges in G to that of U ∗ , the sets
Ai cover a δ-fraction of edges in S with high probability. As we show, the fact that |U ∗ | ≤ n/p
ensures a bounded overhead via Bernstein’s concentration inequality.
When interpreted as a one-round MapReduce algorithm, the construction above admits good
bounds on both the maximum reducer size and the maximum number of times a vertex is replicated by the mappers.
Lemma 4.1. Let U ∗ be a subset of vertices in G = (V, E). The MapReduce algorithm that chooses Lp
uniformly random automorphisms π1 , . . . , π Lp and maps x ∈ V to the reducer assigned π j (U ∗ ) whenever
x ∈ π j (U ∗ ) has reducer size |U ∗ |, and with probability 1 − |V |−1 , it maps each vertex to at most 7 ·
max{ln |V |, Lp|U ∗ |/|V |} reducers.
Proof. Any x ∈ V is contained in π j (U ∗ ) with probability |U ∗ |/|V |. The expected number of
indices j such that x ∈ π j (U ∗ ) is Lp|U ∗ |/|V |. By independence of the automorphisms, a standard
9

Chernoff bound implies that x is mapped to more than 7 · max{ln |V |, Lp|U ∗ |/|V |} reducers with
probability at most |V |−2 . Taking a union bound over V finishes the proof.
We now analyze the above algorithm for Γ≤r .

Edge-Isoperimetry for Hamming Distance
The classical edge-isoperimetric result for Γ1 states that s vertices contain at most 12 s log2 s edges [13,
29, 30, 40]. The optimal set is a subcube when log2 s is integral, and it is a natural interpolation
between subcubes for other s values.
For Γ≤r with r > 1, an exact edge-isoperimetric inequality is not known. Surprisingly, optimal
shapes must be far from subcubes. For example, Hamming balls, which are essentially the optimal vertex-isoperimetric sets for Γ1 , are not only much better than subcubes, they are also not too
far from optimal edge-isoperimetric sets for Γ≤r . We give an easy argument for very rough approximate optimality of Hamming balls below and state a much sharper bound that was recently
shown by the second author and co-author [23] in parallel work.
We start with preliminaries about the number of edges in a Hamming ball. We will lower
bound the average degree in Γ≤r of a ball of radius k, that is, the value e≤r (Ball(0d , k )).
Proposition 4.2. For k ∈ [d] with dr/2e ≤ k, we have


1
k
d
e≤r (Ball(0 , k )) ≥ ·
· B(d − k, br/2c)
2
dr/2e
Proof. Observe that e≤r (Ball(0d , k )) ≥

1
2

min

x ∈Ball(0d ,k )

|Ball(0d , k) ∩ Ball( x, r )|.

We first argue that the minimum occurs when | x | = k. Indeed, let | x 0 | < k and | x | = | x 0 | + 1
such that x ⊕ x 0 contains a single non-zero coordinate j.
C LAIM : |Ball(0d , k ) ∩ Ball( x 0 , r )| ≥ |Ball(0d , k ) ∩ Ball( x, r ))|.
First note that for any z ∈ {0, 1}d , Ball(z, r ) = z ⊕ Ball(0d , r ). Let y ∈ Ball(0d , r ) have y j = 0
and let y0 be the same as y except that bit y j = 1. Now x 0 ⊕ y = x ⊕ y0 and x ⊕ y = x 0 ⊕ y0 .
Therefore, (i) the number of such y for which x 0 ⊕ y ∈ Ball(0d , k ) but x ⊕ y ∈
/ Ball(0d , k) is equal
to (ii) the number of such y0 for which x ⊕ y0 ∈ Ball(0d , k ) but x 0 ⊕ y0 ∈
/ Ball(0d , k ). Observe
d
0
d
that (i) counts Ball(0 , k ) ∩ Ball( x , r ) \ (Ball(0 , k ) ∩ Ball( x, r )) and (ii) counts a (strict) superset of
Ball(0d , k ) ∩ Ball( x, r ) \ (Ball(0d , k ) ∩ Ball( x 0 , r )) since for any z0 ∈ Ball(0d , r ) with z0j = 1, the element z equal to z0 except that z j = 0 is also a member of Ball(0d , r ). (The strictness follows because
for those y ∈ Ball(0d , r ) with |y| = k have y0 ∈
/ Ball(0d , r ).) This proves the claim which implies
that the minimum occurs when | x | = k.
Now fix some x ∈ Ball(0d , k ) with | x | = k. We count vectors z in Ball(0d , k ) ∩ Ball( x, r ). The
vector z may be obtained from x by flipping i bits from one to zero, and j bits from zero to one, as
long as i ≤ k, i + j ≤ r, and j ≤ i. Therefore, by summing
(i, j) that meet these conditions,
 over 
k
d−k
the number of vectors z is at least
. This is a lower bound on the
∑
∑
i
j
i ≤min{r,k } j≤min{r −i,i }
minimum, and thus average, degree of Ball(0d , k ) in Γ≤r .
10

Hamming Balls are nearly optimal for r > 1. We sketch the ideas behind the edge-isoperimetric
inequality for r > 1. Consider A ⊆ {0, 1}d . Using standard down-shifting arguments, we may
assume A ⊆ Ball(0d , blog2 | A|c). Thus, the average degree of A in Γ≤r is roughly bounded by
that of a ball of radius blog2 | A|c. In particular, e≤r ( A) ≤ B(d, br/2c) · B(blog2 | A|c, dr/2e). Ellis
and Rashtchian [23] improve this estimate by roughly a factor of (log2 (d/ log2 | A|))br/2c , nearly
matching the Hamming ball upper bound.

4.1

Proof of Theorem 3.1(a)

Now we prove the upper bound in our main theorem by exhibiting a randomized ( p, δ)-edgecovering for sets of size n in Γ≤r achieving the claimed overhead.
For p ≤ (d/ logd n)r/2 we can achieve the bound simply using the universal algorithm. Our
construction for p > (d/ logd n)r/2 consists of a partition of a random set of Hamming balls. We
denote the radius of these balls by k, which will be carefully chosen to achieve efficient coverage
and ensure proper load balancing. Intuitively, if k is too small, then each ball has too few edges
and we will need too many balls to cover all the edges in Γ≤r . On the other hand, if k is too large,
then we risk having a large intersection |S ∩ Ai | on input S. We will see that the value of k that
achieves the best overhead bounds is such that B(d, k ) ≈ |S|/p = n/p, but we consider all values
of k for which the algorithm makes sense.

Randomized Edge-Covering Construction using Hamming Balls
Let n be the input set size and k ≥ dr/2e to be any integer such that
p B(d, k ) ≤ n/p. Observe that
by our assumption p > (d/ logd n)r/2 , we have that k ≤ d/2 − Ω( rd log d).
The number of Hamming balls in the covering will be proportional to the ratio of the number
of edges in Γ≤r and in Ball(0d , k ). Let this ratio `k be
4

`k =

|E≤r ({0, 1}d )|
.
|E≤r (Ball(0d , k))|

Define a random distribution Ak (δ) of p-tuples of subsets of {0, 1}d with ( A1 , . . . , A p ) ∼ Ak (δ)
chosen as follows: Let x1 , . . . , x Lp ⊆ {0, 1}d be a uniformly random sequence of vectors where
L = ln(1/(1 − δ)) · d`k /pe. Define the random sets Ai as
Ai =

[

Ball( xi , k ).

j ≡ i mod p

We begin by bounding `k , the ratio of the number of edges in Γ≤r to that in Ball(0d , k ). This
bound on `k (and thus Lp) combines with Lemma 4.1 to immediately provide the claimed upper
bounds in Theorem 3.1 on the reducer size and the number of times that a vector is replicated.
Proposition 4.3. Fix k ∈ [d] with dr/2e ≤ k ≤ d/2 − dr/2e. Then,

|E≤r ({0, 1}d )|
<
|E≤r (Ball(0d , k))|



2d
k

dr/2e

·

2d +1
.
B(d, k )

11

Proof. The definition of E≤r ({0, 1}d ) and the lower bound on e≤r (Ball(0d , k )) in Proposition 4.2
imply that

`k =

B(d, r )2d
|E≤r ({0, 1}d )|
≤
.
k
|E≤r (Ball(0d , k))|
(dr/2
e) · B ( d − k, br/2c) · B ( d, k )

We invoke Proposition A.1 from the appendix and use the assumption d/2 ≥ 2dr/2e to bound
B(d, r )/B(d, br/2c) ≤ 45 ddr/2e /r br/2c . Then, combining this with the simple bound (kj) ≥ (k/j) j we
obtain that the upper bound on `k is at most
 dr/2e
 dr/2e
5 (dr/2e)dr/2e
B(d, br/2c)
d
2d
d
2d +1
dbr/2c
·
·
·
·
·
·
<
.
4
B(d − k, br/2c)
k
B(d, k )
k
B(d, k )
r br/2c
(d − k)br/2c
We used that (dr/2e)dr/2e /r br/2c is at most 1 with r even and achieves its maximum value of 1.35
for r odd at r = 5. Finally, since d − k − br/2c ≥ d/2, this is at most (2d/k )dr/2e · 2d+1 /B(d, k ).
The upper bound on the overhead in Theorem 3.1 follows from the following two lemmas, and
the fact that B(d, k ) ≤ dk , which implies that B(d, k ) for k ≤ (1 − γ) logd n = logd (n/p) is at
most n/p.
Lemma 4.4. For all S ⊆ {0, 1}d with |S| = n, for k ≥ dr/2e and B(d, k ) ≤ n/p, we have
E[overhead(Ak (δ), S)] ≤ max{6 ln(1/(1 − δ)) · (2d/k )dr/2e , 9 log2 p}.
Moreover, the bound on the overhead holds almost surely.
Proof. Let S ⊆ {0, 1}d with |S| = n. We will upper bound E[maxi |S ∩ Ai |] by proving an upper
bound on E[|S ∩ Ai |] for each i ∈ [ p], where the latter expectation is over the distribution on
Ai induced by Ak (δ). After doing so, we union bound over [ p] to guarantee the bound on the
expected max with high probability.
Fix i ∈ [ p]. The set Ai is the union of Ball( x j , k ) for L vectors x j chosen uniformly and independently from {0, 1}d . Define the random variable Zj = |S ∩ Ball( x j , k)| for j ∈ [ L]. Then,
defining Z = ∑ j Zj , we have |S ∩ Ai | ≤ ∑ j Zj = Z. We first upper bound E[ Z ] ≥ E[|S ∩ Ai |].
Observe that for a uniformly random x j from {0, 1}d , every element of {0, 1}d is equally likely to
be in Ball( x j , k ). Therefore every j ∈ [ L],
E[ Zj ] = E[|S ∩ Ball( x j , k)|] =

∑ Pr[y ∈ Ball(x j , k)] = ∑

y∈S

y∈S

B(d, k )
n · B(d, k )
=
.
d
2
2d

Thus, recalling L = ln(1/(1 − δ)) · d`k /pe, and using the upper bound on `k (the ratio of the
number of edges in Ball(0d , k ) and in Γ≤r ) from Proposition 4.3, we compute
E[ Z ] = L ·

n · B(d, k )
n · B(d, k )
n
= ln(1/(1 − δ)) · d`k /pe ·
< 3 ln(1/(1 − δ)) · (2d/k)dr/2e · .
d
d
p
2
2

For concentration, we use Bernstein’s inequality (e.g., Thm. 3.6 in [19]), which applies since 0 ≤
Zj ≤ B(d, k ) and E[ Zj2 ] ≤ B(d, k )E[ Zj ]. Therefore, for any λ ≥ E[ Z ],
1

Pr [ Z > 2λ] ≤ e− 2 λ

2 / ( B ( d,k )E[ Z ]+ λB ( d,k ) /3)

3

≤ e− 8 λ/B(d,k) .
12

For every λ = λ(θ ) ≥ max{E[ Z ], 4B(d, k )(log2 p + θ )} the probability that |S ∩ Ai | ≥ 2λ is at most
e−θ /p3/2 . By the union bound over [ p], the probability that maxi |S ∩ Ai | exceeds 2λ is at most
e−θ /p1/2 . In particular, we have an upper bound on overhead(Ak (δ), S) of 2λ.
We conclude with the correctness argument.
Lemma 4.5. For any n, Ak (δ) forms a ( p, δ)-edge-covering of the n-subsets of {0, 1}d . Further, if δ is
chosen to be 1 − 1/n3 , then ( A1 , . . . , A p ) ∼ Ak (δ) covers all edges of any fixed input set of size n with
probability at least 1 − 1/n.
Proof. Fix S ∈ {0, 1}d with |S| = n. Since Γ≤r is edge-transitive, for x j ∈ {0, 1}d chosen uniformly
at random, each pair {u, v} ∈ S of distance at most r satisfies {u, v} ⊆ Ball( x j , k ) with probability
1/`k = |E≤r (Ball(0d , k ))|/|E≤r ({0, 1}d )|.
Therefore, the probability that a fixed {u, v} is not covered by ( A1 , . . . , A p ) ∈ Ak (δ) is at most

(1 − 1/`k ) Lp ≤ (1 − 1/`k )ln(1/(1−δ))`k ≤ e− ln(1/(1−δ)) = 1 − δ.
Each edge of E≤r (S) is covered with probability at least δ, and in expectation ( A1 , . . . , A p ) ∼ Ak (δ)
covers at least a δ fraction of E≤r (S).
There are at most n2 pairs in S so with δ = 1 − 1/n3 (in which case Ak (δ) chooses 3pd`k /pe ln n
uniformly random balls of radius k) a union bound implies that the probability that ( A1 , . . . , A p ) ∼
Ak (δ) covers all pairs in S is at least 1 − 1/n.

5

The Lower Bound

We now prove the lower bound of Theorem 3.1(b). Let A be any randomized ( p, δ)-edge cover of
the n-subsets of {0, 1}d for Γ≤r .
We will use a variant of Yao’s minimax principle by exhibiting a “hard” distribution on subsets
S of {0, 1}d of size n. The usual form of the argument would then be to show that the distribution has the property that the expected overhead of any fixed ( A1 , . . . , A p ) in the support of A is
large and conclude that the expected overhead for A on some element of the support of the hard
distribution is large.
However, this does not quite work. Since A produces a large fraction of the similar pairs of
S only in expectation, its support may contain ( A1 , . . . , A p ) that achieve low overhead but without
producing many similar pairs. Instead, we show that (1) the expected overhead under the hard
S
distribution must be large for any tuple ( A1 , . . . , A p ) such that | i∈[ p] E≤r ( Ai )| is at least a δ/2
fraction of |edges(Γ≤r )| and that (2) any ( A1 , . . . , A p ) that fails to have this property does badly
at covering subsets S chosen according to this distribution and hence such tuples must only be a
small fraction of the probability mass of A.
The hard input distribution Dn,d over sets S ⊆ {0, 1}d of size n will choose S to be a random
sub-sampled Hamming ball of suitable size so that S has relatively high density within that ball.

13

Definition 5.1. Let d ∈ Z+ and r ∈ [d] be positive integers. Given n ∈ [2d−1 ], let R = R(n, d, r ) ∈ Z+
denote the unique positive integer such that r divides R and
B(d, R − r ) < n ≤ B(d, R).
Define distribution Dn,d on subsets S of {0, 1}d of size n by first choosing x ∈ {0, 1}d uniformly at random,
then choosing a random subset of n elements of Ball( x, R).
Using the fact that Dn,d samples edges uniformly from Γ≤r we have the following simple property of potential covers.
[

Proposition 5.2. If ( A1 , . . . , A p ) satisfies |

E≤r ( Ai )| ≤ α · |edges(Γ≤r )| for some α ∈ [0, 1], then

i ∈[ p]

E

[

S∼Dn,d

E≤r ( Ai ∩ S) ≤ α · |E≤r (S)|.

i ∈[ p]

Proof. Observe that

S

i ∈[ p]

E≤r ( A i ∩ S ) =

S

i ∈[ p]


E≤r ( Ai ) ∩ E≤r (S). For S chosen according to

Dn,d , the set E≤r (S) contains each edge of Γ≤r with equal probability, so the claim follows by
linearity of expectation.
Observing that f ≤r (n, d, p, δ) is precisely
f ≤r (n, d, p, δ) = min
A

max

S⊆{0,1}d : |S|=n

overhead(A, S),

Yao’s minimax principle [58] applied to distribution Dn,d yields the following.
good

Lemma 5.3. Let δ ∈ [0, 1] and Aδ
be the set of tuples ( A1 , . . . , A p ) of subsets of {0, 1}d such that
S
| i∈[ p] E≤r ( Ai )| ≥ 2δ · |edges(Γ≤r )|. Then,


p
δ
max
max | Ai ∩ S| ·
.
f ≤r (n, d, p, δ) ≥ ·
E
2 ( A1 ,...,A p )∈ Agood S∼Dn,d
n
i
δ

Proof. Let A be a randomized ( p, δ)-edge cover for the n subsets of Γ≤r . Therefore the expectation
S
over ( A1 , . . . , A p ) ∼ A and S ∼ Dn,d of | i∈[ p] E≤r ( Ai ∩ S)| must be at least δ|E≤r (S)|, since
good

the δ|E≤r (S)| bound holds for every choice of S. By Proposition 5.2 for ( A1 , . . . , A p ) ∈
/ Aδ we
S
have E | i∈[ p] E≤r ( Ai ∩ S)| ≤ δ|E≤r (S)|/2. Since the most this quantity can be is |E≤r (S)|, by
S∼Dn,d

good

Markov’s inequality, the probability that A produces ( A1 , . . . , A p ) that is in Aδ
and since all quantities are non-negative, the lower bound follows.
good

For the remainder of this section we fix ( A1 , . . . , A p ) in Aδ

|

[

E≤r ( Ai )| ≥

i ∈[ p]

We prove that

E

S∼Dn,d

δ
|edges(Γ≤r )| = δB(d, r )2d−2 .
2

is at least δ/2

, so that
(1)

maxi | Ai ∩ S| must be large. Note that for sufficiently small r, and sufficiently

large δ, equation (1) implies a lower bound on the total number of edges of Γr covered by the Ai .
14

√
√
good
Proposition 5.4. Suppose that r ≤ d/2 and δ ≥ 4/ d. If ( A1 , . . . , A p ) ∈ Aδ , then
 
[
δ
d
Er ( Ai )| ≥ ·
|
· 2d −1
4
r
i ∈[ p]

Proof. There are B(d, r − 1)2d−1 edges of Γ≤r that are not in Γr . For r ≤

(r−d 1)
(dr)

=

√

d/2, we see that

1
r
<√
d−r+1
d+1

√
and hence B(d, r − 1) ≤ B(d, r )/ d ≤ 4δ · B(d, r ). Combining with (1), we have that at least
δ
d−1 ≥ δ d 2d−1 edges of Γ are contained in S
r
i ∈[ p] Er ( Ai ).
4 B ( d, r )2
4 (r)
Next, we reduce the problem to reasoning about covers that only include necessary elements.
Intuitively, it suffices to cover each vertex with fewer sets than its degree.
Definition 5.5. A tuple ( A1 , . . . , A p ) is r-pruned if for every x ∈ {0, 1}d , |{i : x ∈ Ai }| ≤ B(d, r ) − 1.
Lemma 5.6. For any ( A1 , . . . , A p ) there exists a r-pruned ( A10 , . . . , A0p ) such that Ai0 ⊆ Ai for all i ∈ [ p]
S
S
and i∈[ p] E≤r ( Ai0 ) = i∈[ p] E≤r ( Ai ).
Proof. Define w( x ) = |{i ∈ [ p] : x ∈ Ai }|. For i ∈ [ p], say that a set Ai is pivotal with respect to x if
there exists an edge { x, y} in Γ≤r with x 6= y such that { x, y} ⊆ Ai while { x, y} ( A j for all j < i.
For each x ∈ {0, 1}d , remove x from all but the pivotal sets for x. Let ( A10 , . . . , A0p ) be the resulting
S
S
tuple of sets. Clearly, i E≤r ( Ai0 ) = i E≤r ( Ai ) by construction. For each x, the number of pivotal
sets for is at most the size of the open neighborhood of x in Γ≤r , which is B(d, r ) − 1. Therefore,
w( x ) ≤ B(d, r ) − 1 for all x, and hence, ( A10 , . . . , A0p ) is r-pruned.
With these basic preliminaries out of the way we describe the overall proof strategy.
Proof Strategy
Lemma 5.6 allows us to assume without loss of generality that ( A1 , . . . , A p ) is r-pruned since
pruning yields the same set of similar pairs covered and does not increase overhead.
Our argument capitalizes on the following tradeoff. We have two cases: For the first case, if
∑i∈[ p] | Ai | is much larger than 2d then the algorithm will replicate vertices many times, implying a
large overhead. For the second case, if ∑i∈[ p] | Ai | is closer to 2d , then we will prove that the average
edge density of induced edges of Γ≤r in the sets Ai must be large. In other words, in the second
case, the weighted average of e≤r ( Ai ) is large. By Proposition 5.4, this means that the weighted
average of er ( Ai ) is also large.
Using a key combinatorial lemma which shows that sets A with large er ( A) must also have
large e≤ R ( A) where R is the distance defined by distribution Dn,d and hence, in the second case,
the sum of the |E≤ R ( Ai )| is large.
Finally, it is not hard to see that |E≤ R ( Ai )| being large is equivalent to saying that the expected
size of | Ai ∩ Ball( x, R)| is large for x a randomly chosen element of Ai and it is not hard to see

15

that a similar property also applies to high density random subsets S of Ball( x, R); like elements
chosen according to Dn,d .
This roughly suggests that a set S chosen from Dn,d will end up producing a large overhead at
some set Ai that contains the center x of the ball Ball( x, R) used to define S. However, as x varies,
which of these sets Ai are possible also varies and the choice of x and the set index i are correlated
so choosing just one Ai would not let the rough argument succeed. Instead, using the fact that,
without loss of generality, no element of {0, 1}d needs to appear in too many sets Ai , we show that
we can eliminate the bias by lower bounding the maximum overhead by the average overhead
over all sets Ai with x ∈ Ai .
We begin by proving the last part of this strategy; i.e., we first relate the expected maximum
size of Ai ∩ S to the number of pairs with distance at most R in Ai .
Lemma 5.7. Let d ∈ Z+ , r ∈ [d], n ∈ [2d−1 ] and R = R(n, d, r ) = kr ≤ d/2 for integer k ≥ 2. Then for
any r-pruned { A1 , . . . , A p } with each Ai ⊆ {0, 1}d ,


B(d, R − r )
R(r) r!
max
|
A
∩
S
|
> d −1
|E≤ R ( Ai )| ≥ 2r ∑ |E≤ R ( Ai )|/2d .
E
i
∑
d
2 B(d, R)( B(d, r ) − 1) i∈[ p]
i ∈[ p]
S∼Dn,d
i ∈[ p]
Proof. The distribution Dn,d first chooses a center x ∈ {0, 1}d uniformly at random and then
x denote the
chooses S ⊆ Ball( x, R) uniformly at random from all subsets of size n. Let Dn,d
conditional distribution of S given a fixed choice of x. Then, since { A1 , . . . , A p }, for all x ∈ {0, 1}d ,
we have
w( x ) = |{i ∈ [ p] : x ∈ Ai }| ≤ B(d, r ) − 1.
We can restrict our choice of maximum to sets containing the center x and lower bound the maximum over such sets by their average to obtain




1
max | Ai ∩ S| = d ∑
E
E x max | Ai ∩ S|
2 x∈{0,1}d S∼Dn,d
i ∈[ p]
S∼Dn,d i ∈[ p]


1
≥ d ∑
E x max | Ai ∩ S|
2 x∈S Ai S∼Dn,d
i ∈[ p]
i


1
≥ d ∑
E x max | Ai ∩ S|
i: x ∈ Ai
2 x∈S Ai S∼Dn,d
i
"
#
| Ai ∩ S |
1
≥ d ∑
since 0 < w( x ) ≤ B(d, r ) − 1
Ex
∑ B(d, r) − 1
2 x∈S Ai S∼Dn,d
i:
x
∈
A
i
i


1
| Ai ∩ S | 
= d ∑
E x  ∑ 1 x ∈ Ai ·
B
(d, r ) − 1
2 x∈S Ai S∼Dn,d
i ∈[ p]
i


1
| Ai ∩ S |
= d ∑ ∑ 1 x ∈ Ai · E
x
B(d, r ) − 1
2 x∈S Ai i∈[ p]
S∼Dn,d
i

=

1
2d ( B(d, r ) − 1)

∑ ∑

E

x
i ∈[ p] x ∈ Ai S∼Dn,d

16

[| Ai ∩ S|] .

(2)

Now for each i ∈ [ p] and x ∈ Ai , we have S ⊆ Ball( x, R); therefore



∑

E

x
x ∈ Ai S∼Dn,d

[| Ai ∩ S|] =
=

∑

E

x
x ∈ Ai S∼Dn,d



∑

∑

∑

∑

∑

1y ∈ S 

y∈Ball( x,R)∩ Ai

Ex

x ∈ Ai y∈Ball( x,R)∩ Ai S∼Dn,d

=

x ∈ Ai y∈Ball( x,R)∩ Ai

=



1y ∈ S



n
B(d, R)

n
· 2|E≤ R ( Ai )|
B(d, R)

since the double summation counts each pair { x, y} in Ai of Hamming distance at most R exactly
twice. Now, by construction of distribution Dn,d , n is larger than B(d, R − r ), so inserting this
B(d,R−r )
bound in (2) yields that E [maxi | Ai ∩ S|] is larger than 2d−1 B(d,R)( B(d,r)−1) ∑i∈[ p] |E≤ R ( Ai )| as
S∼Dn,d

required. Now, B(d, r ) ≤ dr /r! and, since R > r, Proposition A.1 proved in the appendix shows
that B(d, R)/B(d, R − r ) ≤ (d + 1)dr−1 /R(r) which is at most 2dr /R(r) . Together these yield the
final claimed bound.
To apply Lemma 5.7, we need a lower bound on |E≤ R ( Ai )|. We obtain such a lower bound
by proving a purely graph-theoretic result. This result relates different distances in subsets of
the hypercube. More precisely, we prove that subsets of {0, 1}d with sufficiently large density of
Hamming distance r pairs (i.e., sufficiently dense induced subgraphs of Γr ) also have a relatively
large density of pairs at Hamming distance at most R when R is a multiple of r. This means that
we can reduce the problem of lower bounding |E≤ R ( Ai )| to that of lower bounding er ( Ai ). We
give this lemma and its proof in the next subsection.

5.1

Relating distance r density and distance R density on the hypercube

Lemma 5.8. Fix b ∈ {0, 1, . . . , br/2c}, and assume that r divides R with r < R . Assume that A ⊆
{0, 1}d satisfies er ( A) ≥ 4( Rb+−1r)(r−bd−1). Then
e≤ R ( A ) ≥

er ( A) R/r
.
4R/r · R! · dbR/r

This lemma is nearly tight; examples include Hamming balls of varying radii and subcubes of
varying dimensionality. Some lower bound on er ( A) is necessary for this to hold since unions of
well-separated balls of radius r have many pairs at distance up to r, but there are no pairs precisely
at distances between 2r and R.
The overall approach to proving Lemma 5.8 is to define a certain class of paths of total length
R/r in the induced subgraph Γr [ A] and prove that this set of paths is large. The start and end of
each such path yields a pair vertices of A at distance at most R in the hypercube. We then show
that any pair of vertices in the hypercube can be connected by relatively few such paths, yielding
a large lower bound on the total number of pairs of vertices in A of distance at most R.

17

Definition 5.9. Fix b ∈ {0, 1, . . . , br/2c}, and assume that r divides R with r < R . An ( R, b)-path is
a sequence (v0 , v1 , . . . , v R/r ) ∈ {0, 1}d×( R/r+1) with dist(v j−1 , v j ) = r and dist(v0 , v j ) ≥ j(r − 2b) for
every j ∈ [ R/r ]. Let π R,b ( A) denote the number of ( R, b)-paths with all vectors in A ⊆ {0, 1}d .
Note that an ( R, b)-path generalizes a Γr shortest path, which is an ( R, 0)-path. Lemma 5.8 is
the immediate consequence of the following two lemmas.
Lemma 5.10. Fix b ∈ {0, 1, . . . , br/2c}, and assume that r divides R with r < R . Let A ⊆ {0, 1}d be a
R −r
d
subset and define N = | A| and M = |Er ( A)|. If M
N ≥ 4( b+1 )(r −b−1), then

π R,b ( A) ≥ N

M
4N

 R/r
.

Lemma 5.11. Fix b ∈ {0, 1, . . . , br/2c}, and assume that r divides R with r < R . For any A ⊆ {0, 1}d ,

|E≤ R ( A)| ≥

π R,b ( A)
.
R! · dbR/r

More precisely, from Lemmas 5.10 and 5.11 we have the following, which yields Lemma 5.8,
e≤ R ( A ) =

π R,b ( A)
|E≤ R ( A)|
er ( A) R/r
≥
≥
.
| A|
R! · d Rb/r · | A|
4R/r · R! · d Rb/r

We begin by proving Lemma 5.10; its proof is similar to proofs of lower bounds on the number
of walks in a graph given by Alon and Rusza [7] and Katz and Tao [35].
Proof of Lemma 5.10. We prove the bound by induction on N. For N ≤ 2, the bound holds trivially.
Let δ∗ denote the minimum degree in the subgraph of Γr induced by A. We first consider the case
with δ∗ ≥ M/(2N ). We will count ( R, b)-paths (v0 , . . . , v R/r ) by lower bounding the number of
choices for v j+1 given the path up to v j . We will argue that

∗

π R,b ( A) ≥ δ N

R/r −1 

∏
j =1



jr
δ −
b+1
∗



d
r−b−1


.

(3)

There are δ∗ N possibilities for v0 . For j = 1, 2, . . . , R/r − 1, we say that a vertex v j+1 is bad if
dist(v0 , v j+1 ) < dist(v0 , v j ) + (r − 2b).
We must exclude the bad neighbors of v j when choosing v j+1 . Each neighbor v j+1 of v j in Γr differs
from v j in exactly r coordinates. Crucially, for v j+1 to be bad, at least b + 1 of the differing coordinates must be in the support of v0 ⊕ v j because each such coordinate used in this step reduces the
distance of v j+1 from v0 by exactly 2. Since |v0 ⊕ v j | = dist(v0 , v j ) ≤ jr, and the other r − b − 1 cojr
ordinates are arbitrary, there are at most (b+
)( d ) bad neighbors of v j in Γr . We have assumed
1 r − b −1
that δ∗ satisfies






R−r
d
jr
d
M
∗
≥2
≥2
.
δ ≥
2N
b+1
r−b−1
b+1
r−b−1
18


M R/r
.
Since each term in the product in (3) is at least δ∗ /2, we conclude π R,b ( A) ≥ N 4N
Now assume that the minimum degree δ∗ is less than M/(2N ). Remove a vertex with degree
δ∗ . The resulting graph on N − 1 vertices has larger average degree. By induction, the number of
( R, b)-paths on N − 1 vertices is at least


M − δ∗ R/r
( N − 1)
.
4( N − 1)
We claim this is at least N ( M/(4N )) R/r . Rearranging both sides, we need to show


M − δ∗
M

( R/r)/(( R/r)−1)

≥

N−1
.
N

By the assumptions δ∗ < M/(2N ) and R/r ≥ 2, we have, as desired,


δ∗
1−
M

( R/r)/(( R/r)−1)



>

1
1−
2N

( R/r)/(( R/r)−1)



≥

1
1−
2N

2

> 1−

1
.
N

We now finish the proof of Lemma 5.8 by proving Lemma 5.11 which says that the number of
pairs of distance ≤ R in A is relatively large compared to the number of ( R, b)-paths in A.
Proof of Lemma 5.11. Consider a pair (u, v) ∈ A × A with dist(u, v) ≤ R. We claim that the number
of ( R, b)-paths between u and v is at most R! · dbR/r . Such a path is specified by a sequence of
edges in Γr , and once we fix u and v, this sequence is specified by
1. a size R multiset M containing coordinates in [d] differing between adjacent vertices,
2. a partition Π of M into R/r sets of size r.
We claim that there are at most dbR/r choices for M and R! choices for Π. We simply upper bound
the count for Π by the number of permutations of R elements. Moving on to M, let k = dist(u, v)
and recall that the ( R, b)-path definition requires k ≥ R − 2bR/r. Observe that M contains the k
elements in the support of u ⊕ v. Additionally, M contains ( R − k ) elements that come in identical
pairs. That is, they form a partition into ( R − k )/2 pairs of identical elements. Once u ⊕ v is fixed,
these pairs determine M, and there are at most d( R−k)/2 ≤ dbR/r choices for the pairs.

5.2

Proof of Theorem 3.1(b)

As described in our overall proof strategy, our lower bound involves a tradeoff between the average number of times t = ∑i∈[ p] | Ai |/2d that elements of {0, 1}d are covered by { A1 , . . . , A p } and
the edge density of the individual Ai , and hence the size of the intersections of sets S ∼ Dn,d ,
which are similar to Hamming balls in structure. The function g that we define below helps us
capture this overhead tradeoff.


p
+
Definition 5.12. Define g : [1, ∞) → R by g(τ ) =
min
max | Ai ∩ S| ·
E
good S ∼D
n
i
n,d
( A1 ,...,A p )∈ A
δ

∑ i | A i | ≤ τ ·2d

19

In particular, our overhead tradeoff is encapsulated in the following lemma.
good

Lemma 5.13. Let ( A1 , . . . , A p ) ∈ Aδ

and let t = 2−d ∑i | Ai |. Then,

E [ max | Ai ∩ S| ] ≥ max{t, g(t)} ·

S∼Dn,d

i

n
p

Proof. We first prove the result for f ≤r (n, d, p, δ). The bound in terms of g(t) follows immediately
from the definition of g. For the bound in terms of t, observe that, since each x ∈ {0, 1}d has
PrS [ x ∈ S] = n2−d , by linearity of expectation we have


1
n
1
n
| Ai | · d = t · .
E [ max | Ai ∩ S| ] ≥ E  ∑ | Ai ∩ S| =
∑
p i∈[ p]
p
i
2
S∼Dn,d
S∼Dn,d p i ∈[ p]

We prove Theorem 3.1(b) by bounding max{t, g(t)}. A lower bound on max{t, g(t)} is a value
such that either t ≥ t∗ or g(t) ≥ t∗ for any t. Therefore, we must prove g(t) ≥ t∗ whenever
t ≤ t∗ . To prove this, we will use the fact that g is a decreasing function and show that the value
t∗ is such that g(t) ≥ t whenever t ≤ t∗ . Indeed, this implies g(t) ≥ g(t∗ ) ≥ t∗ for all t ≤ t∗ .
t∗

Proof of Theorem 3.1(b). We first state the value of a threshold t∗ such that g(t) ≥ t for all t ≤ t∗ and
then argue that it implies Theorem 3.1(b).
Lemma 5.14. Let n, d, r, p be as in the statement of Theorem 3.1(b) and R = R(n, d, r ) be as in Definition 5.1. Define
(
γ/2 if γr > 1
β=
γ
if γr ≤ 1.
2

Then, g(t) ≥ t whenever 1 ≤ t ≤

t∗

for

t∗

=

t∗ (n, d,

δd βr−2r /R
p, r ) =
.
64rr Rγr
4

2

By construction, R is Θ(logd n) and the assumption that n ≥ dr log2 d implies that d2r /R is at
most cr for some constant c. Plugging these values into the formula for t∗ , the two bounds of
Theorem 3.1(b) follow immediately by combining Lemma 5.3 and Lemma 5.13.
The lower bound proof for f r (n, d, p, δ) is almost identical, but it uses a variant definition of
good
g and Lemma 5.13 that replaces the condition ( A1 , . . . , A p ) ∈ Aδ
with the condition that the
good

conclusion of Proposition 5.4 holds, which is the only place that membership in Aδ
the proof of Lemma 5.13.

is used in

It only remains to prove Lemma 5.14.
good

Proof of Lemma 5.14. Let t ≤ t∗ and ( A1 , . . . , A p ) ∈ Aδ be a tuple satisfying ∑i∈[ p] | Ai | = t · 2d
p
and g(t) = E [maxi | Ai ∩ S|] · n . Since Lemma 5.7 gives us a lower bound on g(t) in terms of
S∼Dn,d

20

∑i |E≤ R ( Ai )|, our goal is to lower bound the latter quantity, assuming t ≤ t∗ . We rewrite this
quantity in terms of the distribution µ over [ p] with µ(i ) = |t2Adi | as
1
2d

∑

|E≤ R ( Ai )| =

i ∈[ p]

1
2d

∑

e≤ R ( Ai )| Ai | = t · E [e≤ R ( Ai )].

(4)

i ∼µ

i ∈[ p]

We apply Lemma 5.8 to lower bound the RHS in (4). Let I ⊆ [ p] be the indices i such that Ai
satisfies er ( Ai ) ≥ 4( Rb+−1r)(r−bd−1) for b = bγr/2c. Observe that with this choice of b, we have
βr ≤ b + 1 since either βr = γr ≤ 1 ≤ b + 1 or βr = γr/2 ≤ bγr/2c + 1 = b + 1. Using Jensen’s
inequality for z 7→ z R/r , we obtain
! R/r
er ( Ai ) R/r
1
≥ ∑ µ ( i ) er ( A i )
· R/r
.
(5)
E [e≤ R ( Ai )] ≥ ∑ µ(i ) · R/r
bR/r
4
· R! · d
4
· R! · dbR/r
i ∼µ
i∈ I
i∈ I
Now, since µ(i )er ( Ai ) =

| A i | er ( A i )
t2d

|Er ( Ai )|
,
t2d

=

good

and ( A1 , . . . , A p ) ∈ Aδ

, Proposition 5.4 implies that

 
δ d
∑ µ(i)er ( Ai ) ≥ 8t r .
i ∈[ p]
Therefore, to lower bound E [e≤ R ( Ai )], it suffices to upper bound ∑i∈/ I µ(i )er ( Ai ), which is at
i ∼µ

most
have

4( Rb+−1r)(r−bd−1)

by definition. Now, since t ≤ t∗ , (dr) ≥ (d/r )r and βr ≤ min{b + 1, γr }, we

 
 
2
δ d
d
δ
≥ 4Rγr dr− βr+2r /R > 4Rb+1 dr−b−1 ≥
≥
16t r
16t∗ r

∑ µ ( i ) er ( A i ) .
i∈
/I

Therefore,
 
2
δ d
∑ µ(i)er ( Ai ) ≥ 16t r ≥ 4Rγr dr−βr+2r /R ,
i∈ I
and from (5) we have
E [e≤ R ( Ai )] ≥

i ∼µ



4Rγr dr− βr+2r

2 /R

 R/r

·

RγR d R−( βR+bR/r)+2r
1
≥
R!
4R/r · R! · dbR/r

(6)

Now if γr ≤ 1 then b = 0 and β = γ so βR + bR/r = γR; alternatively, if γr > 1, then b ≤ γr/2
and β = γ/2 and we have βR + bR/r ≤ γR. Therefore, from (6) we have
E [e≤ R ( Ai )] ≥

i ∼µ

RγR d R−γR+2r
.
R!

(7)

Using Lemma 5.7 and plugging in (4) and (7) and the definition of γ = logn p into the definition
of g(t), we have
E

g(t) =

S∼Dn,d

[maxi | Ai ∩ S|]
n 1− γ

≥ t·

Since R ≥ 2r ≥ 2, we see that g(t) ≥ t ·
as required.

R(r) r!
RγR d R−γR+2r
·
.
R!
2d2r · n1−γ

RγR d(1−γ) R
.
n 1− γ

21

Since n ≤ B(d, R) ≤ d R /R!, we derive g(t) ≥ t

6

Discussion and Future Work

We provided improved parallel algorithms for similarity joins under Hamming distance. We also
proved communication lower bounds for one-round, local algorithms. Qualitatively, we showed
that an overhead of dΘ(r) is necessary and sufficient. Although we stated our technical results for
Hamming distance, we gave a template for upper and lower bounds in general edge-transitive
similarity graphs. A main algorithmic theme running through our results was to perform upfront
data replication so that the processors need only one round of communication. This methodology
may lead to improved algorithms for other distributed computation tasks.
Local Computation. We optimized for the maximum number of vertices assigned to any one
processor and hence the maximum difficulty of the local computation required; however, our
focus on communication leaves unanswered details about the actual computation of the close
pairs. After the communication, any local algorithm may be used to compare candidates and
output pairs satisfying the distance threshold. For example, processors could simply compare
all received pairs. Clearly, by enlarging the groups of points sent to each processor compared
to [1, 2, 49] we lose the efficiency of being able to only check pairs of points within small subcubes
or balls. However, during the local computation stage, the processor may use a local partitioning
scheme, possibly involving subcubes or balls, to reduce the overall number of comparisons.
Locality Sensitive Hashing (LSH) has been used successfully in practice for range queries and
nearest neighbor search [8, 11, 28, 54]. Recent work [44, 48] exhibits an LSH-scheme for Hamming
distance without false negatives.
Overall, we believe that further optimizations are needed to implement an efficient all-pairs
similarly search. In the `2 metric, Aiger, Kaplan, and Sharir [4] design an algorithm for finding all
close pairs using an edge-covering consisting of randomly shifted and rotated grids. Moreover,
they demonstrate improvements over direct LSH approaches.
Our approach also extends naturally to support dynamic and streaming data efficiently: only
the processors responsible for a vector need to be notified for its addition or deletion. Regarding randomness used for communication, work in the theoretical computer science community
suggests bounded independence often suffices and improves performance [22, 43, 52].
Open Questions. We point out five concrete future directions left open by our work.
1. Can we close the gap between our upper and lower bounds on f ≤r (n, d, p, δ)? Currently,
there is a gap between the exponents of γr/2 versus r/2.
2. Our randomized edge-covering needed a random construction to find a family of Hamming
balls that cover all edges with high probability. Is it possible to remove the error and decrease
the communication by exhibiting an explicit construction?
3. Our lower bound holds for the restricted model where processors must communicate sets of
vertices. Can we generalize our result and prove a lower bound on the maximum number
of bits some processor must receive during the one round of communication?

22

4. The protocol for arbitrary similarity graphs uses copies of the optimal edge-isoperimetric
shape. Can we determine this shape and analyze the resulting protocol for other metrics?
Prime candidates include the `1 distance and the edit distance over small alphabets.
5. Does our edge-covering methodology lead to improvements in practice? Empirical research
on similarity joins often employs a “filter-then-verify” strategy. First, the algorithm or data
structure coarsely prunes the set of candidates, often conservatively. Then, a brute force
search reveals actual close pairs. It is worth exploring filters based on edge-optimal sets.

Acknowledgements
We thank Sivaramakrishnan Natarajan Ramamoorthy for bringing Sidorenko’s conjecture and related results to our attention.

References
[1] Foto N Afrati, Anish Das Sarma, David Menestrina, Aditya Parameswaran, and Jeffrey D
Ullman. Fuzzy Joins using MapReduce. In ICDE. IEEE, 2012.
[2] Foto N. Afrati, Anish Das Sarma, Anand Rajaraman, Pokey Rule, Semih Salihoglu, and Jeffrey D. Ullman. Anchor-Points Algorithms for Hamming and Edit Distances Using MapReduce. In ICDT, 2014.
[3] Thomas D Ahle, Rasmus Pagh, Ilya Razenshteyn, and Francesco Silvestri. On the Complexity
of Inner Product Similarity Join. arXiv, abs/1510.02824, 2015.
[4] Dror Aiger, Haim Kaplan, and Micha Sharir. Reporting Neighbors in High-Dimensional
Euclidean Space. SIAM J. Comput., 43(4):1363–1395, 2014.
[5] Josh Alman, Timothy M Chan, and Ryan Williams. Polynomial representations of threshold
functions and algorithmic applications. arXiv, abs/1608.04355, 2016.
[6] Josh Alman and Ryan Williams. Probabilistic Polynomials and Hamming Nearest Neighbors.
In Proceedings, 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages
136–150, 2015.
[7] Noga Alon and Imre Z Ruzsa. Non-averaging subsets and non-vanishing transversals. Journal of Combinatorial Theory, Series A, 86(1):1–13, 1999.
[8] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt.
Practical and Optimal LSH for Angular Distance. In NIPS, pages 1225–1233, 2015.
[9] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten.
mal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors.
abs/1608.03580, 2016.

23

OptiarXiv,

[10] Alexandr Andoni and Ilya Razenshteyn. Tight Lower Bounds for Data-dependent Localitysensitive Hashing. In 32nd Intl. Symp. on Comp. Geom. (SoCG), pages 9:1–9:11, 2016.
[11] Bahman Bahmani, Ashish Goel, and Rajendra Shinde. Efficient distributed locality sensitive
hashing. In Proceedings of the 21st ACM International Conference on Information and Knowledge
Management, CIKM ’12, pages 2174–2178, New York, NY, USA, 2012. ACM.
[12] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query
Processing. In PODS. ACM, 2013.
[13] Arthur J Bernstein. Maximally connected arrays on the n-cube. SIAM J. Applied Mathematics,
15(6):1485–1489, 1967.
[14] Sergei Bezrukov. Edge Isoperimetric Problems on Graphs. Graph Theory and Combinatorial
Biology, 7:157–197, 1999.
[15] Béla Bollobás and Imre Leader. Sums in the grid. Discrete Mathematics, 162(1-3):31–48, 1996.
[16] Andrei Z Broder. Identifying and filtering near-duplicate documents. In Combinatorial pattern
matching, pages 1–10. Springer, 2000.
[17] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings
of the thiry-fourth annual ACM symposium on Theory of computing, pages 380–388. ACM, 2002.
[18] Yeow Meng Chee, Charles J Colbourn, Alan CH Ling, and Richard M Wilson. Covering and
packing for pairs. Journal of Combinatorial Theory, Series A, 120(7):1440–1449, 2013.
[19] Fan Chung and Linyuan Lu. Concentration Inequalities and Martingale Inequalities: a Survey. Internet Mathematics, 3(1):79–127, 2006.
[20] David Conlon, Jacob Fox, and Benny Sudakov. An Approximate Version of Sidorenkos Conjecture. Geometric and Functional Analysis, 20(6):1354–1366, 2010.
[21] Abhinandan S Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google News Personalization: Scalable Online Collaborative Filtering. In Proceedings of the 16th international
conference on World Wide Web, pages 271–280. ACM, 2007.
[22] Martin Dietzfelbinger. Universal Hashing and k-Wise Independent Random Variables via
Integer Arithmetic Without Primes. In STACS, 1996.
[23] David Ellis and Cyrus Rashtchian. Edge-Isoperimetric Inequalities for Powers of the Hypercube. In Preparation, 2016.
[24] Paul Erdos and Miklos Simonovits. Compactness Results in Extremal Graph Theory. Combinatorica, 2(3):275–288, 1982.
[25] Yunchao Gong and Svetlana Lazebnik. Iterative Quantization: A Procrustean Approach to
Learning Binary Codes. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 817–824. IEEE, 2011.
24

[26] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. WTF:
The Who to Follow Service at Twitter. In WWW, 2013.
[27] Sariel Har-Peled. Geometric Approximation Algorithms, volume 173. American mathematical
society Providence, 2011.
[28] 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.
[29] Lawrence H Harper. Optimal assignments of numbers to vertices. Journal of the Society for
Industrial and Applied Mathematics, pages 131–135, 1964.
[30] Sergiu Hart. A note on the edges of the n-cube. Discrete Mathematics, 14(2):157–163, 1976.
[31] Daniel Horsley. Generalising fisher’s inequality to coverings and packings.
abs/1409.0485, 2014.

arXiv,

[32] R. Impagliazzo and R. Paturi. On the complexity of k-SAT. J. Comp. Sys. Sci., 67:367–375, 2001.
[33] Yu Jiang, Guoliang Li, Jianhua Feng, and Wen-Syan Li. String Similarity Joins: An Experimental Evaluation. Proceedings of the VLDB Endowment, 7(8):625–636, 2014.
[34] Jeff Kahn, Gil Kalai, and Nati Linial. The Influence of Variables on Boolean Functions. In
SFCS, 1988.
[35] Nets Hawk Katz and Terence Tao. A New Bound on Partial Sum-sets and Difference-sets,
and Applications to the Kakeya Conjecture. arXiv, abs/9906.097, 1999.
[36] Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing, 30(2):457–474, 2000.
[37] Hans-Peter Lenhof and Michiel Smid. Sequential and Parallel Algorithms for the k-closest
Pairs Problem. International J. Comput. Geometry & Applications, 5(03):273–288, 1995.
[38] Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of Massive Datasets.
Cambridge University Press, 2014.
[39] Yeqing Li, Chen Chen, Wei Liu, and Junzhou Huang. Sub-Selective Quantization for LargeScale Image Search. In AAAI, 2014.
[40] John H Lindsey. Assignment of Numbers to Vertices. The American Mathematical Monthly,
71(5):508–516, 1964.
[41] Rajeev Motwani, Assaf Naor, and Rina Panigrahy. Lower bounds on locality sensitive hashing. SIAM J. Discrete Mathematics, 21(4):930–935, 2007.
[42] Ryan O’Donnell, Yi Wu, and Yuan Zhou. Optimal lower bounds for locality-sensitive hashing
(except when q is tiny). ACM Transactions on Computation Theory, 6(1):5, 2014.

25

[43] Anna Pagh, Rasmus Pagh, and Milan Ružić. Linear Probing with Constant Independence.
SIAM J. Comput., 39(3):1107–1120, September 2009.
[44] Rasmus Pagh. Locality-sensitive hashing without false negatives. In SODA, pages 1–9. SIAM,
2016.
[45] Rasmus Pagh, Ninh Pham, Francesco Silvestri, and Morten Stöckel. I/O-Efficient Similarity
Join. In Algorithms-ESA 2015, pages 941–952. Springer, 2015.
[46] Rina Panigrahy, Kunal Talwar, and Udi Wieder. A Geometric Approach to Lower Bounds for
Approximate Near-Neighbor Search and Partial Match. In FOCS, 2008.
[47] Rina Panigrahy, Kunal Talwar, and Udi Wieder. Lower Bounds on Near Neighbor Search via
Metric Expansion. In FOCS, 2010.
[48] Ninh Pham and Rasmus Pagh. Scalability and total recall with Fast CoveringLSH. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management,
CIKM, pages 1109–1118, 2016.
[49] Anish Das Sarma, Foto N. Afrati, Semih Salihoglu, and Jeffrey D. Ullman. Upper and Lower
Bounds on the Cost of a Map-reduce Computation. Proc. VLDB Endow., 6(4):277–288, February 2013.
[50] Alexander Sidorenko. A Correlation Inequality for Bipartite Graphs. Graphs and Combinatorics, 9(2-4):201–204, 1993.
[51] Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk, Samuel Madden, and Pradeep Dubey. Streaming Similarity Search Over One Billion Tweets Using Parallel Locality-Sensitive Hashing. Proceedings of the VLDB Endowment,
6(14):1930–1941, 2013.
[52] Mikkel Thorup. High Speed Hashing for Integers and Strings. arXiv, abs/1504.06804, 2015.
[53] Rares Vernica, Michael J Carey, and Chen Li. Efficient Parallel Set-similarity Joins using
MapReduce. In SIGMOD, pages 495–506. ACM, 2010.
[54] Hongya Wang, Jiao Cao, LihChyun Shu, and Davood Rafiei. Locality Sensitive Hashing
Revisited: Filling the Gap Between Theory and Algorithm Analysis. In CIKM, 2013.
[55] Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to Hash for Indexing Big
Data — A Survey. Proceedings of the IEEE, 104(1):34–57, 2016.
[56] Chuan Xiao, Wei Wang, Xuemin Lin, Jeffrey Xu Yu, and Guoren Wang. Efficient Similarity
Joins for Near-duplicate Detection. ACM Transactions on Database Systems, 36(3):15, 2011.
[57] Ismet Zeki Yalniz, Ethem F. Can, and R. Manmatha. Partial Duplicate Detection for Large
Book Collections. In CIKM, 2011.
[58] Andrew C. Yao. Lower Bounds by Probabilistic Arguments. In FOCS, 1983.
26

[59] Reza Bosagh Zadeh and Ashish Goel. Dimension Independent Similarity Computation. The
Journal of Machine Learning Research, 14(1):1605–1626, 2013.
[60] Hanwang Zhang, Fumin Shen, Wei Liu, Xiangnan He, Huanbo Luan, and Tat-Seng Chua.
Discrete Collaborative Filtering. In SIGIR, 2016.

27

A

Ball Ratios

Proposition A.1. For r < R ≤ (d + 1)/2, we have

( d + 1 ) d r −1
B(d, R)
≤
.
B(d, R − r )
R (r )
Proof. For i ≥ 0 define
4

bi =

( Rd−i) + · · · + ( Rd )
( Rd−i)

.

d
d
Both B(d, R) and B(d, R − r ) contain the common terms (d0) + · · · + ( R−
r ) ≥ ( R−r ) and so
d
d
( R−
B(d, R)
r ) + · · · + ( R)
≤ br =
.
B(d, R − r )
( d )
R −r

Observe that by definition b0 = 1 and for i ≥ 0 we have the recurrence
bi + 1 = 1 +

( Rd−i)
( R−di−1)

· bi = 1 +

d−R+i+1
· bi .
R−i

We prove by induction that for i ≥ 1 we have 2 ≤ bi ≤ (d + 1)di−1 /R(i) . For the base case, since
b0 = 1 we have b1 = 1 + d−RR−+1 2 b0 = (d + 1)/R and since R ≤ (d + 1)/2, we have b1 ≥ 2. For
i ≥ 1,
d−R+i+1
· bi

 R−i
R−i−1
d
−
· bi
= 1+
R−i
R−i
d
R−i−1
≤ 1+
· bi −
·2
R−i
R−i
d
≤
· bi .
since R > r ≥ i.
R−i

bi + 1 = 1 +

since bi ≥ 2 by the inductive hypothesis

Now applying the inductive hypothesis we have
bi + 1 ≤

d
d
· bi =
· (d + 1)di−1 /R(i) = (d + 1)di /R(i+1)
R−i
R−i

as claimed.

B

Other Lower Bounds

We sketch two simple, but nontrivial, lower bounds for Hamming distance that achieve a different
dependence on |S| than the bounds we obtain using isoperimetric inequalities. For the discussion,
let L denote the number of vertices a processor receives, not bits.
28

For the first hard distribution, pick one random ball of radius r/2 and include each vector in
this ball in S with probability half. A processor may output at most all pairs among vertices it
receives. On the other hand, all pairs in the input S are within distance r. Thus, we need
  

L
B(d, r/2)
≥
.
p
2
2

√
Since |S| = Θ( B(d, r/2)), we can rewrite this as L ≥ Ω(|S|/ p).
For another hard distribution, consider picking |S|/B(d, r/2) random balls each of radius r/2,
then subsampling each vector with probably half. Receiving L vertices leads to at most ( L2 ) close
pairs. The input has Θ(|S| · B(d, r/2)) close pairs. This gives
q

q
L≥Ω
B(d, r/2) · |S|/p .

29

