Heavy hitters via cluster-preserving clustering
Kasper Green Larsen∗

Jelani Nelson†

Huy L. Nguy˜ên‡

Mikkel Thorup§.

arXiv:1604.01357v1 [] 5 Apr 2016

April 6, 2016

Abstract
In the turnstile `p heavy hitters problem with parameter ε, one must maintain a highdimensional vector x ∈ Rn subject to updates of the form update(i, ∆) causing the change
xi ← xi + ∆, where i ∈ [n], ∆ ∈ R. Upon receiving a query, the goal is to report every “heavy
hitter” i ∈ [n] with |xi | ≥ εkxkp as part of a list L ⊆ [n] of size O(1/εp ), i.e. proportional to the
maximum possible number of heavy hitters. In fact we solve the stronger tail version, in which
L should include every i such that |xi | ≥ εkx[1/εp ] kp , where x[k] denotes the vector obtained by
zeroing out the largest k entries of x in magnitude.
For any p ∈ (0, 2] the CountSketch of [CCFC04] solves `p heavy hitters using O(ε−p lg n)
words of space with O(lg n) update time, O(n lg n) query time to output L, and whose output
after any query is correct with high probability (whp) 1 − 1/ poly(n) [JST11, Section 4.4]. This
space bound is optimal even in the strict turnstile model [JST11] in which it is promised that
xi ≥ 0 for all i ∈ [n] at all points in the stream, but unfortunately the query time is very slow.
To remedy this, the work [CM05] proposed the “dyadic trick” for the CountMin sketch for
p = 1 in the strict turnstile model, which to maintain whp correctness achieves suboptimal space
O(ε−1 lg2 n), worse update time O(lg2 n), but much better query time O(ε−1 poly(lg n)). An
extension to all p ∈ (0, 2] appears in [KNPW11, Theorem 1], and can be obtained from [Pag13].
We show that this tradeoff between space and update time versus query time is unnecessary.
We provide a new algorithm, ExpanderSketch, which in the most general turnstile model
achieves optimal O(ε−p lg n) space, O(lg n) update time, and fast O(ε−p poly(lg n)) query time,
providing correctness whp. In fact, a simpler version of our algorithm for p = 1 in the strict
turnstile model answers queries even faster than the “dyadic trick” by roughly a lg n factor,
dominating it in all regards. Our main innovation is an efficient reduction from the heavy
hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy
spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every
heavy hitter must be found, correctness requires that every cluster be found. We thus need
a “cluster-preserving clustering” algorithm, that partitions the graph into clusters with the
promise of not destroying any original cluster. To do this we first apply standard spectral graph
partitioning, and then we use some novel combinatorial techniques to modify the cuts obtained
so as to make sure that the original clusters are sufficiently preserved. Our cluster-preserving
clustering may be of broader interest much beyond heavy hitters.
∗
Aarhus University. larsen@cs.au.dk. Supported by Center for Massive Data Algorithmics, a Center of the
Danish National Research Foundation, grant DNRF84, a Villum Young Investigator Grant and an AUFF Starting
Grant.
†
Harvard University. minilek@seas.harvard.edu. Supported by NSF grant IIS-1447471 and CAREER award
CCF-1350670, ONR Young Investigator award N00014-15-1-2388, and a Google Faculty Research Award.
‡
Toyota Technological Institute at Chicago. hlnguyen@cs.princeton.edu.
§
University of Copenhagen. mikkel2thorup@gmail.com. Supported in part by Advanced Grant DFF-0602-02499B
from the Danish Council for Independent Research under the Sapere Aude research career programme.

1

Introduction

Finding heavy hitters in a data stream, also known as elephants or frequent items, is one of the
most practically important and core problems in the study of streaming algorithms. The most basic
form of the problem is simple: given a long stream of elements coming from some large universe,
the goal is to report all frequent items in the stream using an algorithm with very low memory
consumption, much smaller than both the stream length and universe size.
In practice, heavy hitters algorithms have been used to find popular destination addresses
and heavy bandwidth users by AT&T [CJK+ 04], to find popular search query terms at Google
[PDGQ05], and to answer so-called “iceberg queries” in databases [FSG+ 98] (to name a few of
many applications). A related problem is finding superspreaders [LCG13], the “heavy hitters” in
terms of number of distinct connections, not total bandwidth.
In the theoretical study of streaming algorithms, finding heavy hitters has played a key role
as a subroutine in solving many other problems. For example, the first algorithm providing nearoptimal space complexity for estimating `p norms in a stream for p > 2 needed to find heavy
hitters as a subroutine [IW05], as did several follow-up works on the same problem [GB09, AKO11,
BO13, BKSV14, Gan15]. Heavy hitters algorithms are also used as a subroutine in streaming
entropy estimation [CCM10, HNO08], `p -sampling [MW10], cascaded norm estimation and finding
block heavy hitters [JW09], finding duplicates [GR09, JST11], fast `p estimation for 0 < p < 2
[NW10, KNPW11], and for estimating more general classes of functions of vectors updated in a
data stream [BO10, BC15].
In this work we develop a new heavy hitters algorithm, ExpanderSketch, which reduces the
heavy hitters problem to a new problem we define concerning graph clustering, which is an area of
interest in its own right. Our special goal is to identify all clusters of a particular type, even if they
are much smaller than the graph we are asked to find them in. While our algorithm as presented is
rather theoretical with large constants, the ideas in it are simple with potential practical impact.
The particular formulation we focus on is finding clusters with low external conductance in
the graph, and with good connectivity properties internally (a precise definition of these clusters,
which we call -spectral clusters, will be given soon). Similar models have been used for finding
a community within a large network, and algorithms for identifying them have applications in
community detection and network analysis. In computer vision, many segmentation algorithms
such as [SM00, AMFM11] model images as graphs and use graph partitioning to segment the
images. In theory, there has been extensive study on the problem with many approximation
algorithms [LR88, ARV09]. Our focus in this work is on theoretical results, with constants that
may be unacceptable in practice.

2

Previous work

In this work we consider the `p heavy hitters problem for 0 < p ≤ 2. A vector x ∈ Rn is maintained,
initialized to the all zero vector. A parameter ε ∈ (0, 1/2) is also given. This is a data structural
problem with updates and one allowed query that are defined as follows.
• update(i, ∆): Updatexi ← xi + ∆, where i ∈ [n] and ∆ ∈ R has finite precision.
• query(): Return a set L ⊆ [n] of size |L| = O(ε−p ) containing all ε-heavy hitters i ∈ [n]
under `p . Here we say i is an ε-heavy hitter under `p if |xi | ≥ εkx[1/εp ] kp , where x[k] denotes
1

the vector x with the largest k entries (in absolute value) set to zero. Note the number of
heavy hitters never exceeds 2/εp .
Unless stated otherwise we consider randomized data structures in which any individual query
has some failure probability δ. Note our definition of ε-heavy hitters includes all coordinates
satisfying the usual definition requiring |xi | ≥ εkxkp , and potentially more. One can thus recover
all the usual heavy hitters from our result by, in post-processing, filtering L to only contain indices
that are deemed large by a separate CountSketch run in parallel. A nice feature of the more
stringent version we solve is that, by a reduction in [JST11, Section 4.4], solving the `2 version of
the problem with error ε0 = εp/2 implies a solution for the `p ε-heavy hitters for any p ∈ (0, 2].
Hence for the remainder of the assume we discuss p = 2 unless stated otherwise. We also note
that any solution to `p heavy hitters for p > 2, even for constant ε, δ, must use polynomial space
Ω(n1−2/p ) bits [BYJKS04].
Before describing previous work, we first describe, in the terminology of [Mut05], three different
streaming models that are frequently considered.
• Cash-register: This model is also known as the insertion-only model, and it is characterized
by the fact that all updates update(i, ∆) have ∆ = 1.
• Strict turnstile: Each update ∆ may be an arbitrary positive or negative number, but we
are promised that xi ≥ 0 for all i ∈ [n] at all points in the stream.
• General turnstile: Each update ∆ may be an arbitrary positive or negative number, and
there is no promise that xi ≥ 0 always. Entries in x may be negative.
It should be clear from the definitions that algorithms that work correctly in the general turnstile
model are the most general, followed by strict turnstile, then followed by the cash-register model.
Similarly, lower bounds proven in the cash-register model are the strongest, and those proven in
the general turnstile model are the weakest. The strict turnstile model makes sense in situations
when deletions are allowed, but items are never deleted more than they are inserted. The general
turnstile model is useful when computing distances or similarity measures between two vectors z, z 0 ,
e.g. treating updates (i, ∆) to z as +∆ and to z 0 as −∆, so that x represents z − z 0 .
For the heavy hitters problem, the first algorithm with provable guarantees was a deterministic
algorithm for finding `1 heavy hitters in the cash-register model [MG82], for solving the non-tail
version of the problem in which heavy hitters satisfy |xi | ≥ εkxk1 . The space complexity and
query time of this algorithm are both O(1/ε), and the algorithm can be implemented so that the
update time is that of insertion into a dynamic dictionary on O(1/ε) items [DLM02] (and thus
expected O(1) time if one allows randomness, via hashing). We measure running time in the word
RAM model and space in machine words, where a single word is assumed large enough to hold
the maximum kxk∞ over all time as well as any lg n bit integer. The bounds achieved by [MG82]
are all optimal, and hence `1 heavy hitters in the cash-register model is completely resolved. An
improved analysis of [BICS10] shows that this algorithm also solves the tail version of heavy hitters.
In another version of the problem in which one simultaneously wants the list L of ε heavy hitters
together with additive ε0 kxk1 estimates for every i ∈ L, [BDW16] gives space upper and lower
bounds which are simultaneously optimal in terms of ε, ε0 , n, and the stream length.
For `2 heavy hitters in the cash-register model, the CountSketch achieves O(ε−2 lg n) space.
Recent works gave new algorithms using space O(ε−2 lg(1/ε) lg lg n) [BCIW16] and O(ε−2 lg(1/ε))
2

reference
[CM05]∗
[CM05]∗
[NNW14]
[CCFC04]
[KNPW11, Pag13]∗
[CH08]
This work

space
ε−1 lg n
ε−1 lg2 n
ε−2 lg n
ε−p lg n
ε−p lg2 n
ε−p lg n
ε−p lg n

update time
lg n
lg2 n
−1
ε lg n
lg n
lg2 n
lg n
lg n

query time
n lg n
−1
ε lg2 n
n lg n
n lg n
ε−p lg2 n
ε−p · nγ
−p
ε poly(lg n)

randomized?
Y
Y
N
Y
Y
Y
Y

`p ,
`p ,
`p ,
`p ,

norm
`1
`1
`1
p ∈ (0, 2]
p ∈ (0, 2]
p ∈ (0, 2]
p ∈ (0, 2]

Figure 1: Comparison of turnstile results from previous work and this work for `p heavy hitters
when desired failure probability is 1/poly(n). Space is measured in machine words. For [CH08],
γ > 0 can be an arbitrarily small constant. If a larger failure probability δ  1/ poly(n) is tolerable,
one lg n factor in space, update time, and query time in each row with an asterisk can be replaced
with lg((lg n)/(εδ)). For [Pag13], one lg n in each of those bounds can be replaced with lg(1/(εδ)).
For [CH08], the query time can be made (ε−p lg n)((lg n)/(εδ))γ .

[BCI+ 16]. A folklore lower bound in the cash-register model is Ω(1/ε2 ) machine words, which
n
follows since simply encoding the names of the up to 1/ε2 heavy hitters requires Ω(lg( 1/ε
2 )) bits.
Despite the `1 and `2 heavy hitters algorithms above in the cash-register model requiring
o(ε−p lg n) machine words, it is known finding ε-heavy hitters under `p for any 0 < p ≤ 2 in
the strict turnstile model requires Ω(ε−p lg n) words of memory, even for constant probability of
success [JST11]. This optimal space complexity is achieved even in the more general turnstile model
by the CountSketch of [CCFC04] for all p ∈ (0, 2] (the original work [CCFC04] only analyzed the
CountSketch for p = 2, but a a very short argument of [JST11, Section 4.4] shows that finding
`p heavy hitters for p ∈ (0, 2) reduces to finding `2 heavy hitters by appropriately altering ε).
For any p ∈ (0, 2], the CountSketch achieves optimal O(ε−p lg n) space, the update time is
O(lg n), the success probability of any query is with high probability (whp) 1 − 1/ poly(n), but the
query time is a very slow Θ(n lg n). In [CM05], for p = 1 in the strict turnstile model the authors
described a modification of the CountMin sketch they dubbed the “dyadic trick” which maintains
whp correctness for queries and significantly improves the query time to O(ε−1 lg2 n), but at the
cost of worsening the update time to O(lg2 n) and space to a suboptimal O(ε−1 lg2 n). An easy
modification of the dyadic trick extends the same bounds to the general turnstile model and also
to ε-heavy hitters under `p for any 0 < p ≤ 2 with the same bounds [KNPW11, Theorem 1] (but
with ε−1 replaced by ε−p ). A different scheme using error-correcting codes in [Pag13, Theorem 4.1]
achieves the same exact bounds for `p heavy hitters when whp success is desired. This tradeoff in
sacrificing space and update time for better query time has been the best known for over a decade
for any 0 < p ≤ 2.
From the perspective of time lower bounds, [LNN15] showed that any “non-adaptive”
turnstile
p
algorithm for constant ε and using poly(lg n) space must have update time Ω( lg n/ lg lg n). A
non-adaptive algorithm is one in which, once the randomness used by the algorithm is fixed (e.g. to
specify hash functions), the cells of memory probed when processing update(i, ∆) depend only on
i and not on the history of the algorithm. Note every known turnstile algorithm for a non-promise
problem is non-adaptive.

3

In summary, there are several axes on which to measure the quality of a heavy hitters algorithm:
space, update time, query time, and failure probability. The ideal algorithm should achieve optimal
space, fast update time (O(lg n) is the best we know), nearly linear query time e.g. O(ε−p poly(lg n)),
and 1/ poly(n) failure probability. Various previous works were able to achieve various subsets of
at most three out of four of these desiderata, but none could achieve all four simultaneously.
Our contribution I: We show the tradeoffs between space, update time, query time, and failure
probability in previous works are unnecessary (see Figure 1). Specifically, in the most general
turnstile model we provide a new streaming algorithm, ExpanderSketch, which for any 0 < p ≤ 2
provides whp correctness for queries with O(lg n) update time, O(ε−p poly(lg n)) query time, and
optimal O(ε−p lg n) space. In fact in the strict turnstile model and for p = 1, we are able to provide
a simpler variant of our algorithm with query time O(ε−1 lg1+γ n) for any constant γ > 0, answering
queries even faster than the fastest previous known algorithms achieving suboptimal update time
and space, by nearly a lg n factor, thus maintaining whp correctness while dominating it in all of
the three axes: space, update time, and query time (see Section D).

2.1

Cluster-preserving clustering

Our algorithm ExpanderSketch operates by reducing the heavy hitters problem to a new clustering problem we formulate of finding clusters in a graph, and we then devise a new algorithm
CutGrabClose which solves that problem. Specifically, the ExpanderSketch first outputs
a graph in which each heavy hitter is encoded by a well-connected cluster (which may be much
smaller than the size of the total graph), then CutGrabClose recovers the clusters, i.e. the heavy
hitters, from the graph. There have been many works on finding clusters S in a graph such that the
conductance of the cut (S, S̄) is small. We will only mention some of them with features similar to
our setting. Roughly speaking, our goal is to find all clusters that are low conductance sets in the
graph, and furthermore induce subgraphs that satisfy something weaker than having good spectral
expansion. It is necessary for us to (1) be able to identify all clusters in the graph; and (2) have
a quality guarantee that does not degrade with the number of clusters nor the relative size of the
clusters compared with the size of the whole graph. As a bonus, our algorithm is also (3) able to
work without knowing the number of clusters.
In the context of heavy hitters, requirement (1) arises since all heavy hitters need to be returned.
The number of heavy hitters is not known and can be large, as is the ratio between the size of
the graph and the size of a cluster (both can be roughly the square root of the size of our graph),
leading to the requirement (2) above. One line of previous works [ST04, AP09, GT12] gives excellent
algorithms for finding small clusters in a much larger graph with runtime proportional to the size of
the clusters, but their approximation guarantees depend on the size of the whole graph, violating
our requirement (2). In fact, requirement (2) is related to finding non-expanding small sets in
a graph, an issue at the forefront of hardness of approximation [RS10]. As resolving this issue in
general is beyond current techniques, many other works including ours attempt to solve the problem
in structured special cases. There are many other excellent works for graph clustering, but whose
performance guarantees deterioriate as k increases, also violating (2). The work [GT14] shows
results in the same spirit as ours: if there are k clusters and a multiplicative poly(k) gap between
the kth and (k +1)st smallest eigenvalues of the Laplacian of a graph, then it is possible to partition
the graph into at most k high conductance induced subgraphs. Unfortunately, such a guarantee is
unacceptable for our application due to more stringent requirements on the clusters being required
4

as k increases, i.e. the poly(k) gap in eigenvalues — our application provides no such promise.
Another work with a goal similar in spirit to ours is [PSZ15], which given the conductances in our
graphs deriving from heavy hitters would promise to find k clusters W up to error poly(k) · |W |
symmetric difference each. Unfortunately such a result is also not applicable to our problem, since
in our application we could have k  |W | so that the guarantee becomes meaningless.
A different line of works [MMV12, MMV14] give algorithms with constant approximation guarantees but without being able to identify the planted clusters, which is not possible in their models
in general. In their setting, edges inside each cluster are adversarially chosen but there is randomness in the edges between clusters. Our setting is the opposite: the edges inside each cluster have
nice structure while the edges between clusters are adversarial as long as there are few of them.
From the practical point of view, a drawback with several previous approaches is the required
knowledge of the number of clusters. While perhaps not the most pressing issue in theory, it is
known to cause problems in practice. For instance, in computer vision, if the number of clusters is
not chosen correctly, algorithms like k-means tend to break up uniform regions in image segmentation [AMFM11]. Instead, a preferred approach is hierarchical clustering [AMFM11], which is in
the same spirit as our solution.
Definition 1. An -spectral cluster is a vertex set W ⊆ V of any size satisfying the following two
conditions: First, only an -fraction of the edges incident to W leave W , that is, |∂(W )| ≤  vol(W ),
where vol(W ) is the sum of edge degrees of vertices inside W . Second, given any subset A of W ,
let r = vol(A)/ vol(W ) and B = W \ A. Then
|E(A, B)| ≥ (r(1 − r) − ) vol(W ).
Note r(1 − r) vol(W ) is the number of edges one would expect to see between A and B had W been
a random graph with a prescribed degree distribution.
Our contribution II: We give a hierarchical graph partitioning algorithm combining traditional
spectral methods and novel local search moves that can identify all -spectral clusters in a potentially
much larger graph for  below some universal constant, independent of the number of clusters or
the ratio between the graph size and cluster sizes. More precisely, consider a graph G = (V, E).
In polynomial time, our algorithm can partition the vertices in a graph G = (V, E) into subsets
V1 , . . . V` so that every -spectral cluster W matches some subset Vi up to an O( vol(W )) symmetric
difference. The algorithm is described in Section 6, with guarantee given by Theorem 1 below.
Theorem 1. For any given  ≤ 1/2000000 and graph G = (V, E), in polynomial time and linear
space, we can find a family of disjoint vertex sets U1 , . . . U` so that every -spectral cluster W of G
matches some set Ui in the sense that
• vol(W \ Ui ) ≤ 3  vol(W ).
• vol(Ui \ W ) ≤ 2250000  vol(W )
Moreover, if v ∈ Ui , then > 4/9 of its neighbors are in Ui .
An interesting feature of our solution is that in optimization in practice, it is usually expected
to perform local search to finish off any optimization algorithm but it is rarely the case that one
can prove the benefit of the local search step. In contrast, for our algorithm, it is exactly our local
search moves which guarantee that every cluster is found.
5

3

Preliminaries

The letter C denotes a positive constant that may change from line to line, and [n] = {1, . . . , n}.
We use “with high probability” (whp) to denote probability 1 − 1/ poly(n).
All graphs G = (V, E) discussed are simple and undirected. We say that a graph is a λ-spectral
expander if the second largest eigenvalue, in magnitude, of its unnormalized adjacency matrix is at
most λ. Given two
P vertex sets S, T ⊆ V , we define E(S, T ) = E ∩ (S × T ). For S, we define the
volume vol(S) = v∈S deg(v), and boundary ∂S = E(S, S) where S = V \ S. We specify volG and
∂G when the graph may not be clear from context. We define the conductance of the cut (S, S) as
φ(G, S) =

|∂S|
.
min{vol(S), vol(S)}

If S or S is empty, the conductance is ∞. We define the conductance of the entire graph G by
φ(G) = min φ(G, S).
∅(S(V

4

Overview of approach

We now provide an overview of our algorithm, ExpanderSketch. In Section A we show turnstile
heavy hitters with arbitrary ε reduces to several heavy hitters problems for which ε is “large”.
Specifically, after the reduction whp we are guaranteed each of the ε-heavy hitters
√ i in the original
stream now appears in some substream updating a vector x0 ∈ Rn , and |x0i | ≥ (1/ C lg n)kx0[C lg n] k2 .
√
√
That is, i is an Ω(1/ lg n)-heavy hitter in x0 . One then finds all the Ω(1/ lg n) heavy hitters in
each substream then outputs their union as the final query
overview
√ result. For the remainder of this
2
we thus focus on solving ε-heavy hitters for ε > 1/ C lg n, so there are at most 2/ε = O(lg n)
heavy hitters. Our goal is to achieve failure probability 1/ poly(n) with space O(ε−2 lg n), update
time O(lg n), and query time ε−2 poly(lg n) = poly(lg n).
There is a solution, which we call the “b-tree” (based on [CH08]), which is almost ideal (see
Section B.2 and Corollary 1). It achieves O(ε−2 lg n) space and O(lg n) update time, but query
time inverse polynomial in the failure probability δ, which for us is δ = 1/ poly(n). Our main idea is
to reduce to the case of much larger failure probability (specifically 1/ poly(lg n)) so that using the
b-tree then becomes viable for fast query. We accomplish this reduction while maintaining O(lg n)
update time and optimal space by reducing our heavy hitter problem into m = Θ(lg n/ lg lg n)
separate partition heavy hitters problems, which we now describe.
In the partition ε-heavy hitters problem, there is some parameter ε ∈ (0, 1/2). There is also
some partition P = {S1 , . . . , SN } of [n], and it is presented in the form of an oracle O : [n] → [N ]
such that for any i ∈ [n], O(i) gives the j ∈ [N ] such that i ∈ Sj . In what follows the partitions will
be random, with Oj depending on some random hash functions (in the case of adapting the b-tree
to partition heavy hitters the Oj are deterministic; see Section B.2). Define a vector y ∈ RN such
that for each j ∈ [N ], yj = kxSj k2 , where xS is the projection of x onto a subset S of coordinates.
The goal then is to solve the ε-heavy hitters problem on y subject to streaming updates to x: we
should output a list L ⊂ [N ], |L| = O(1/ε2 ), containing all the ε-heavy hitters of y. See Section B
for more details.
6

update(29, ∆)
m = 3 chunks

enc(i) = 0

1

1

update(1, v)

1
update(3, v)

P1

P2

t
0

1
update(1, v)

P3

Figure 2: Simplified version of final data structure. The update is x29 ← x29 + ∆ with m = 3, t = 2
in this example. Each Pj is a b-tree operating on a partition of size 2t .
Now we explain how we make use of partition heavy hitters. For each index i ∈ [n] we can
view i as a length lg n bitstring. Let enc(i) be an encoding of i into T = O(lg n) bits by an errorcorrecting code with constant rate that can correct an Ω(1)-fraction of errors. Such codes exist with
linear time encoding and decoding [Spi96]. We partition enc(i) into m contiguous bitstrings each
of length t = T /m = Θ(lg lg n). We let enc(i)j for j ∈ [m] denote the jth bitstring of length t when
partitioning enc(i) in this way. For our data structure, we instantiate m separate partition heavy
hitter data structures from Section B.2 (a partition heavy hitter variant of the b-tree), P1 , . . . , Pm ,
each with failure probability 1/ poly(lg n). What remains is to describe the m partitions Pj . We
now describe these partitions, where each will have N = 2O(t) = poly(lg n) sets.
Now, how we would like to define the partition is as follows, which unfortunately does not quite
work. For each j ∈ [m], we let the jth partition Pj have oracle Oj (i) = enc(i)j . That is, we partition
the universe according to the jth chunks of their codewords. See Figure 2 for an illustration, where
upon an update (i, ∆) we write for each Pj the name of the partition that is being updated. The
key insight is that, by definition of the partition heavy hitters problem, any partition containing
a heavy hitter i ∈ [n] is itself a heavy partition in Pj . Then, during a query, we would query
each Pj separately to obtain lists Lj ⊆ [2t ]. Thus the Pj which succeed produce Lj that contain
the jth chunks of encodings of heavy hitters (plus potentially other t-bit chunks). Now, let us
perform some wishful thinking: suppose there was only one heavy hitter i∗ , and furthermore each
Lj contained exactly enc(i∗ )j and nothing else. Then we could obtain i∗ simply by concatenating
the elements of each Lj then decoding. In fact one can show that whp no more than an arbitrarily
small fraction (say 1%) of the Pj fail, implying we would still be able to obtain 99% of the chunks
of enc(i∗ ), which is sufficient to decode. The main complication is that, in general, there may be
more than one heavy hitter (there may be up to Θ(lg n) of them). Thus, even if we performed
wishful thinking and pretended that every Pj succeeded, and furthermore that every Lj contained
exactly the jth chunks of the encodings of heavy hitters and nothing else, it is not clear how to
perform the concatenation. For example, if there are two heavy hitters with encoded indices 1100
and 0110 with m = t = 2, suppose the Pj return L1 = {11, 01} and L2 = {00, 10} (i.e. the first
and second chunks of the encodings of the heavy hitters). How would we then know which chunks
matched with which for concatenation? That is, are the heavy hitter encodings 1100, 0110, or are
they 1110, 0100? Brute force trying all possibilities is too slow, since m = Θ(lg n/ lg lg n) and each
|Lj | could be as big as Θ(lg n), yielding (C lg n)m = poly(n) possibilities. In fact this question is
quite related to the problem of list-recoverable codes (see Section C), but since no explicit codes are
7

Layer #:

Layer #:

Layer #:

Layer #:

1

2

3

..

..

..

..

..

..

..

..

..

..

..

..

m

(a)

(b)

(c)

(d)

Figure 3: Each vertex in row j corresponds to an element of Lj , i.e. the heavy hitter chunks output
by Pj . When indices in Pj are partitioned by hj (i) ◦ enc(i)j ◦ hj+1 (i), we connect chunks along
paths. Case (a) is the ideal case, when all j are good. In (b) P2 failed, producing a wrong output
that triggered incorrect edge insertions. In (c) both P2 and P3 failed, triggering an incorrect edge
and a missing vertex, respectively. In (d) two heavy hitters collided under h3 , causing their vertices
to have the same name thereby giving the appearance of a merged vertex. Alternatively, light items
masking as a heavy hitter might have appeared in L3 with the same h3 evaluation as a heavy hitter
but different h4 evaluation, causing the red vertex to have two outgoing edges to level 4.
known to exist with the efficiency guarantees we desire, we proceed in a different direction.
To aid us in knowing which chunks to concatenate with which across the Lj , a first attempt
(which also does not quite work) is as follows. Define m pairwise independent hash functions
h1 , . . . , hm : [n] → [poly(lg n)]. Since there are O(lg n) heavy hitters, any given hj perfectly hashes
them with decent probability. Now rather than partitioning according to Oj (i) = enc(i)j , we
imagine setting Oj (i) = hj (i) ◦ enc(i)j ◦ hj+1 (i) where ◦ denotes concatenation of bitstrings. Define
an index j ∈ [m] to be good if (a) Pj succeeds, (b) hj perfectly hashes all heavy hitters i ∈ [n],
and (c)
√ for each heavy hitter i, the total `2 weight from non-heavy hitters hashing to hj (i) is
o((1/ lg n)kx[1/ε2 ] k2 . A simple argument shows that whp a 1 −  fraction of the j ∈ [m] are good,
where  can be made an arbitrarily small positive constant. Now let us perform some wishful
thinking: if all j ∈ [m] are good, and furthermore no non-heavy elements appear in Lj with the
same hj but different hj+1 evaluation as an actual heavy hitter, then the indices in Lj tell us which
chunks to concatenate within Lj+1 , so we can concatenate, decode, then be done. Unfortunately
a small constant fraction of the j ∈ [m] are not good, which prevents this scheme from working
(see Figure 3). Indeed, in order to succeed in a query, for each heavy hitter we must correctly
identify a large connected component of the vertices corresponding to that heavy hitter’s path —
that would correspond to containing a large fraction of the chunks, which would allow for decoding.
Unfortunately, paths are not robust in having large connected component subgraphs remaining
even for O(1) bad levels.
The above consideration motivates our final scheme, which uses an expander-based idea first
proposed in [GLPS14] in the context of “for all” `1 /`1 sparse recovery, a problem in compressed
sensing. Although our precise motivation for the next step is slightly different than in [GLPS14],
and our query algorithm and our definition of “robustness” for a graph will be completely different,
the idea of connecting chunks using expander graphs is very similar to an ingredient in that work.

8

The idea is to replace the path in the last paragraph by a graph which is robust to a small fraction
of edge insertions and deletions, still allowing the identification of a large connected component in
such scenarios. Expander graphs will allow us to accomplish this. For us, “robust” will mean that
over the randomness in our algorithm, whp each corrupted expander is still a spectral cluster as
defined in Section 6. For [GLPS14], robustness meant that each corrupted expander still contains
an induced small-diameter subgraph (in fact an expander) on a small but constant fraction of the
vertices, which allowed them a recovery procedure based on a shallow breadth-first search. They
then feed the output of this breadth-first search into a recovery algorithm for an existing listrecoverable code (namely Parvaresh-Vardy codes). Due to suboptimality of known list-recoverable
codes, such an approach would not allow us to obtain our optimal results.
An expander-based approach: Let F be an arbitrary d-regular connected graph on the vertex
set [m] for some d = O(1). For j ∈ [m], let Γ(j) ⊂ [m] be the set of neighbors of vertex j. We
partition [n] according to Oj (i) = z(i)j = hj (i) ◦ enc(i)j ◦ hΓ(j)1 ◦ · · · ◦ hΓ(j)d where Γ(j)k is the kth
neighbor of j in F . Given some such z, we say its name is the first s = O(lg lg n) bits comprising
the hj portion of the concatenation. Now, we can imagine a graph G on the layered vertex set
V = [m] × [2s ] with m layers. If Lj is the output of a heavy hitter query on Pj , we can view each
element z of Lj as suggesting d edges to add to G, where each such z connects d vertices in various
layers of V to the vertex in layer j corresponding to the name of z. The way we actually insert
the edges is as follows. First, for each j ∈ [m] we instantiate a partition point query structure Qj
as per Lemma 14 with partition Pj , failure probability 1/ poly(lg n), and error parameter cε for a
small constant c. We modify the definition of a level j ∈ [m] being “good” earlier to say that Qj
must also succeed on queries to every z ∈ Lj . We point query every partition z ∈ Lj to obtain an
estimate ỹz approximating yz (for the exact form of approximation, see Eq. (4) from Lemma 14).
We then group all z ∈ Lj by name, and within each group we remove all z from Lj except for the
one with the largest ỹz , breaking ties arbitrarily. This filtering step guarantees that the vertices in
layer j have unique names, and furthermore, when j is good all vertices corresponding to heavy
hitters appear in Lj and none of them arePthrown out by this filtering. We then let G be the graph
created by including the at most (d/2) · j |Lj | edges suggested by the z’s across all Lj (we only
include an edge if both endpoints suggest it). Note G will have many isolated vertices since only
m · maxj |Lj | = O(lg2 n/ lg lg n) edges are added, but the number of vertices in each layer is 2s ,
which may be a large power of lg n. We let G be its restriction to the union of non-isolated vertices
and vertices whose names match the hash value of a heavy hitter at the m different levels. This
ensures G has O(lg2 n/ lg lg n) vertices and edges. We call this G the chunk graph.
Now, the intuitive picture is that G should be the vertex-disjoint union of several copies of
the expander F , one for each heavy hitter, plus other junk edges and vertices coming from other
non-heavy hitters in the Lj . Due to certain bad levels j however, some expanders might be missing
a small constant -fraction of their edges, and also the m bad levels may cause spurious edges
to connect these expanders to the rest of the graph. The key insight is as follows. Let W be the
vertices of G corresponding to some particular heavy hitter, so that in the ideal case W would be
a single connected component whose induced graph is F . What one can say, even with m bad
levels, is that every heavy hitter’s such vertices W forms an O()-spectral cluster as per Definition 1.
Roughly this means that (a) the cut separating W from the rest of G has O() conductance (i.e.
it is a very sparse cut), and (b) for any cut (A, W \A) within W , the number of edges crossing the
cut is what is guaranteed from a spectral expander, minus O() · vol(W ). Our task then reduces to

9

move
right

to
the
hi there

move
right

...

to
the
hi there

...
(a)

(b)

again

again

Figure 4: Each small oval is a spectral cluster. They are well-connected internally, with sparse
cuts to the outside. The large oval is the rest of the graph, which can look like anything. Cut (a)
represents a good low-conductance cut, which makes much progress (cutting the graph in roughly
half) while not losing any mass from any cluster. Cut (b) is also a low-conductance cut as long
as the number of small ovals is large, since then cutting one cluster in half has negligible effect on
the cut’s conductance. However, (b) is problematic since recursing on both sides loses half of one
cluster forever.
finding all -spectral clusters in a given graph. We show in Section 6 that for each such cluster W ,
we are able to find a (1 − O())-fraction of its volume with at most O() · vol(W ) erroneous volume
from outside W . This suffices for decoding for  a sufficiently small constant, since this means we
find most vertices, i.e. chunks of the encoding, of the heavy hitter.
For the special case of `1 heavy hitters in the strict turnstile model, we are able to devise a
much simpler query algorithm that works; see Section D for details. For this special case we also
give in Section E a space-optimal algorithm with O(lg n) update time, whp success, and expected
query time O(ε−1 lg n) (though unfortunately the variance of the query time may be quite high).

4.1

Cluster-preserving clustering

An -spectral cluster is a subset W of the vertices in a graph G = (V, E) such that (1) |∂W | ≤
 vol(W ), and (2) for any A ( W with vol(A)/ vol(W ) = r, |E(A, W \A)| ≥ (r(1 − r) − ) vol(W ).
Item (2) means the number of edges crossing a cut within W is what you would expect from a
random graph, up to  vol(W ). Our goal is to, given G, find a partition of V such that every
-spectral cluster W in G matches some partition up to  vol(W ) symmetric difference.
Our algorithm CutGrabClose is somewhat similar to the spectral clustering algorithm of
[KVV04, Section 4], but with local search. That algorithm is quite simple: find a low-conductance
cut (e.g. a Fiedler cut) to split G into two pieces, then recurse on both pieces. Details aside, Fiedler
√
cuts are guaranteed by Cheeger’s inequality to find a cut of conductance O( γ) as long as a cut
of conductance at most γ exists in the graph. The problem with this basic recursive approach is
shown in Figure 4 (in particular cut (b)). Note that a cluster can be completely segmented after a
few levels of recursion, so that a large portion of the cluster is never found.
Our approach is as follows. Like the above, we find a low-conductance cut then recurse on both
sides. However, before recursing on both sides we make certain “improvements” to the cut. We
10

say A ⊂ V is closed in G if there is no vertex v ∈ G\A with at least 5/9ths of its neighbors in A.
Our algorithm maintains that all recursive subcalls are to closed subsets in G as follows. Suppose
we are calling CutGrabClose on some set A. We first try to find a low-conductance cut within
A. If we do not find one, we terminate and let A be one of the sets in the partition. Otherwise,
if we cut A into (S, S̄), then we close both S, S̄ by finding vertices violating closure and simply
moving them. It can be shown that if the (S, S̄) cut had sufficiently low conductance, then these
local moves can only improve conductance further. Now both S and S̄ are closed in A (which by a
transitivity lemma we show, implies they are closed in G as well). We then show that if (1) some
set S is closed, and (2) S has much more than half the volume of some spectral cluster W (e.g. a
2/3rds fraction), then in fact S contains a (1 − O())-fraction of W . Thus after closing both S, S̄,
we have that S either: (a) has almost none of W , (b) has almost all of W , or (c) has roughly half
of W (between 1/3 and 2/3, say). To fix the latter case, we then “grab” all vertices in S̄ with
some Ω(1)-fraction, e.g. 1/6th, of their neighbors in S and simply move them all to S. Doing this
some constant number of times implies S has much more than 2/3rds of W (and if S was in case
(a), then we show it still has almost none of W ). Then by doing another round of closure moves,
one can ensure that both S, S̄ are closed, and each of them has either an O()-fraction of W or a
(1 − O())-fraction. The details are in Section 6. It is worth noting that our algorithm can make
use of any spectral cutting algorithm as a black box and not just Fiedler cuts, followed by our
grab and closure steps. For example, algorithms from [OV11, OSV12] run in nearly linear time
and either (1) report that no γ-conductance cut exists (in which case we could terminate), (2) find
√
a balanced cut of conductance O( γ) (where both sides have nearly equal volume), or (3) find an
√
O( γ)-conductance cut in which every W ⊂ G with vol(W ) ≤ (1/2) vol(G) and φ(W ) ≤ O(γ) has
more than half its volume on the smaller side of the cut. Item (2), if it always occurred, would
give a divide-and-conquer recurrence to yield nearly linear time for finding all clusters. It turns
out item (3) though is even better! If the small side of the cut has half of every cluster W , then
by grabs and closure moves we could ensure it is still small and has almost all of W , so we could
recurse just on the smaller side. It appears an O(|E| lg |V |)-space implementation of such a cutting
algorithm achieving this guarantee would lead to O(ε−2 lg2+o(1) n) query time for whp heavy hitters
(with O(ε−2 lg1+o(1) n) expected query time), but in this version of our work we simply focus on
achieving O(ε−2 poly(lg n)).

5

General turnstile updates

In this section we analyze our algorithm ExpanderSketch described in Section 4. Recall that our
final algorithm, including the reduction in Section A, is as follows. First we pick a hash function
h : [n] → [q] from a Θ(lg n)-wise independent hash family for q = d1/(ε2 lg n)e. Then we initialize
q data structures D1 , . . . , Dq , where
each Dk is an ε0 -heavy hitters data structure as described
√
in Section 4, for ε0 = max{ε, 1/ C lg n}. We also during intialization construct a d-regular λ0 spectral expander F on m = Θ(lg n/ lg lg n) vertices for some d = O(1), where λ0 = d for some
(small) constant  > 0 to be specified later. Such an F can be constructed in time poly(lg n) with
d = poly(1/) deterministically [RVW02], then stored in adjacency list representation consuming
O(lg n/ lg lg n) words of memory.
The Dk are independent, and for each Dk we pick hash functions hk1 , . . . , hkm : [n] → [poly(lg n)]
independently from a pairwise independent family and instantiate partition ε0 -heavy hitter data
k (as b-trees; see Section B.2) with O k : [n] → [2O(t) ] for j ∈ [m] defined by
structures P1k , . . . , Pm
j
11

Ojk (i) = hkj (i) ◦ enc(i)j ◦ hkΓ(j)1 ◦ · · · ◦ hkΓ(j)d . Each Pjk has failure probability 1/ poly(lg n). We
also instantiate partition cε-point query data structures Qk1 , . . . , Qkm with small constant c and
failure probability 1/ poly(lg n) as per Lemma 14, with the same Ojk . Here enc is an encoding as in
Section 4 mapping into T = O(lg n) bits, and t = T /m = Θ(lg lg n). Γ(j)k is the kth neighbor of
j in F . To answer a query to our overall data structure, we query each Dk separately then output
the union of their results. To answer a query to Dk , we form a chunk graph Gk from the outputs of
the Pjk as in Section 4. We then find all 0 -spectral clusters using Theorem 1 for a sufficiently small
constant 0 , throw away all clusters of size less than m/2, then from each remaining cluster W 0 we:
(1) remove all vertices of degree ≤ d/2, (2) remove v ∈ W 0 coming from the same layer j ∈ [m]
as some other v 0 ∈ W 0 , then (3) form a (partially corrupted) codeword using the bits associated
with vertices left in W 0 . We then decode to obtain a set B k containing all heavy hitter indices
i ∈ h−1 (k) with high probability. We then output L = ∪qk=1 B k as our final result.
Henceforth we condition on the event E that every heavy hitter i ∈ [n] is ε0 -heavy in Dh(i) ,
which happens whp by Theorem 5. Our final analysis makes use of the following.
Lemma 1. Suppose E occurs. Focus on a particular k ∈ [q]. Let x0 = xh−1 (k) be the projection of
x onto vertices hashing to k. As in Section 4, we say an index j ∈ [m] is good if (a) Pjk succeeded,
(b) hkj perfectly hashes all ε0 -heavy hitters in x0 , (c) for each ε0 -heavy hitter i, the total `2 weight
√
from non-heavy hitters in h−1 (k) hashing to hj (i) is under hj is o((1/ lg n))kx[1/ε02 ] k2 , and (d) Qkj
succeeded on every z ∈ Lkj . Call j bad otherwise. Then if the failure probability of each Pjk , Qkj is
1/ lgC+1 n, the range of each hkj is [lgC+3 n], and m = C lg n/ lg lg n for some constant C > 0, then
with probability 1 − 1/nc the number of bad levels is at most βm, where c can be made an arbitrarily
large constant and β an arbitrarily small constant by increasing C.
Proof. The probability of (b), that hkj perfectly hashes all O(lg n) ε0 -heavy hitters, is 1 −
O(1/ lgC+1 n). For (c), focus on a particular heavy hitter i. The expected squared `2 mass
from non-ε0 heavy hitters colliding i under hj is (1/ lgC+3 n)kx[1/ε02 ] k22 by pairwise independence
of hj . Thus by Markov, the probability that more than (1/ lg2 n)kx[1/ε02 ] k22 squared `2 mass collided with i from light items is at most 1/ lgC+1 n. Since there are only O(lg n) ε0 -heavy hitters, by a union bound we have
√ that (c) holds, i.e. that no heavy hitter collides with more
than (1/ lg n)kx[1/ε02 ] k2 = o(1/ lg n)kx[1/ε02 ] k2 `2 mass from light items under `j , with probability 1 − O(1/ lgC n). For (d), we perform O(1/ε02 ) = O(lg n) point queries on Qkj , and each point
query has failure probability 1/ lgC+1 n, so the probability that any of the point query fails is at
most 1/ lgC n. Thus j is bad with probability O(1/ lgC n). Now also choose m = C lg n/ lg lg n.
Then the probability that there are more than βm bad levels is at most, for some constant C 0
independent of C,
   0 βm 
βC lg n/ lg lg n  0 βC lg n/ lg lg n
m
C
C 0e
Ce
1
1
≤
=
· βC 2 = βC 2 −o (1) ,
C
C
n
βm
β
n
n
lg n
β lg n

using ab ≤ (ea/b)b . Thus the lemma holds for β = 1/C, and c = C/2 for sufficiently large n. 
Our correctness analysis also makes use of the following lemma [AC88, Lemma 2.3] to show
that, with high probability, each heavy hitter is represented by an 0 -spectral cluster. The lemma
states that for spectral expanders, sets expand with small sets S satisfying even better expansion
properties. Some version of this lemma is known in the literature as the expander mixing lemma.
12

Lemma 2. [AC88] Let A be the adjacency matrix of a d-regular graph with vertex set V . Suppose
the second largest eigenvalue of A in magnitude is λ > 0. Then for any S ⊆ V , writing |S| = r|V |,
|∂S| ≥ (d − λ)(1 − r)|S|.
Theorem 2. Assume n is larger than some constant. Let A be the algorithm from Theorem 1
which finds all 0 -spectral clusters in a graph on O(ε0−2 lg n/ lg lg n) vertices and edges whp in time
T and space S. For any 0 < ε < 1/2, there is an algorithm solving the ε-heavy hitters problem
in general turnstile streams on vectors of length n whp with space and update time O(ε−2 lg n) and
O(lg n), respectively. Answering a query uses an additional O(S) = o(ε−2 lg n) space and runs in
time O(ε−2 lg1+γ n + qT ) = O(ε−2 poly(lg n)), by q successive calls to A. Here γ > 0 can be chosen
as an arbitrarily small constant.
Proof. We first analyze space and running times. We store F , taking O(lg n/ lg lg n) space, which
can be ignored as it is dominated by other parts of the algorithm. Storing h requires O(lg n) words
of memory. Let us now focus on a specific Dk . It stores m hash functions drawn independently
from a pairwise family mapping [n] to [poly(lg n)], consuming O(m) = O(lg n/ lg lg n) space. The
m b-trees combined Pjk consume space m · O(ε0−2 t) = O(ε0−2 lg n), and the same for the Qkj . Thus
the total space per Dk is O(ε0−2 lg n), and thus the total space across the entire algorithm is
O(qε0−2 lg n) = O(ε−2 lg n). We also need an additional O(S) space to run A repeatedly during
a query. For the update time, we first hash using h, taking O(lg n) time. Then within a Dk we
perform m hash evaluations hkj , taking total time O(m). We then compute the encoding enc(i) of
i, taking O(lg n) time, then perform m b-tree updates taking total time m · O(t) = O(lg n). Thus
the total update time is O(lg n). For the query time, for a given Dk we have to query m b-trees,
taking time m · O(ε0−2 t lgγ n) = O(ε0−2 lg1+γ n). We also run A on Gk , taking time T . Thus the
total query time is O(q(ε0−2 lg1+γ n + T )) = O(ε−2 lg1+γ n + qT ).
Now it only remains to argue correctness. Each Lk has size O(1/ε02 ) with probability 1, which
is a guarantee of the b-tree. Then when we form the chunk graph Gk , it has O(ε0−2 lg n/ lg lg n)
vertices. We only insert a decoded spectral cluster into L if its size is at least m/2, so there can be
at most O(1/ε02 ) such clusters found. Thus |L| ≤ O(q/ε02 ) = O(1/ε2 ) with probability 1.
It now only remains to show that each heavy hitter i ∈ [n] is represented by some spectral
cluster of size at least m/2 in Gh(i) . We assume event E, which happens whp. Now let us focus on
a particular Gk . Define x0 = xh−1 (k) . We will show that each ε0 -heavy hitter in x0 is represented
by such a cluster in Gk . Focus on a particular ε0 -heavy hitter i. Let W be the set of m vertices
{(j, hkj (i))}m
j=1 . Suppose that all levels j ∈ [m] were good. We claim that in this case, W would be
an isolated connected component in Gk , and furthermore the induced graph on W would be F . To
see this, observe that before filtering by Qkj , z k (i)j appears in Lkj (see Section 4 for the definitions
of Lj and z(i)j ; Lkj , z k (i)j are then the natural modifications corresponding to k ∈ [q]). Once we
group the z ∈ Lkj by name and filter according to Qkj , let z 6= z k (i)j be such that its name also
equals hkj (i). Since level j is good, none of the mass of z is from a heavy hitter. Thus by condition
√
(c) in the definition of goodness, the `2 weight yz of partition z is at most o(1/ lg n)kx[1/ε02 ] k2 .
Thus by the condition of Eq. (4), since Qkj succeeds we will will have ỹz k (i)j > ỹz and not remove
z k (i)j from Lkj . Thus z k (i)j remains in Lkj even after filtering. Since this is true across all j ∈ [m],
we will add all edges of F to W . Furthermore no vertices outside W will connect to W , since edge
insertion requires mutual suggestion of the edge by both endpoints. Thus, in the case of all good

13

levels, by Lemma 2 for any subset A of W with |A| = r|W | = rm,
|E(A, W \A)| ≥ (d − λ0 )r(1 − r)|W | = (r(1 − r) − r(1 − r)

λ0
λ0
)d|W | ≥ (r(1 − r) − )dm.
d
4d

By Lemma 1, the number of bad levels is at most βm with high probability, for β an arbitrarily
small constant. Let us now understand the possible effects of a bad level on W . Suppose j is bad.
Then the Lkj obtained after filtering by Qkj may not include z k (i)j . Thus W may lose at most d
edges from F (those corresponding to edges incident upon vertex j in F ). Second, Lkj after filtering
may instead contain some z whose name is hkj (i), but whose edge suggestions differ from z k (i)j ,
possibly causing edges to be inserted within W which do not agree with F , or even inserting edges
that cross the cut (W, G\W ). At most d such edges are inserted in this way. Thus, across all bad
levels, the total number of F -edges deleted within W is at most βdm, and the total number of
edges crossing the cut (W, G\W ) is also at most βdm. Also, the volume vol(W ) is always at most
dm and at least (1 − β)dm. Thus after considering bad levels, for any subset A of W as above,
|E(A, W \A)| ≥ (r(1 − r) −

λ0
− β)dm ≥ (r(1 − r) − 0 ) vol(W ).
4d

for 0 ≥ β + λ0 /(4d). Furthermore, the number of edges leaving W to G\W is
|∂(W )| ≤ βdm ≤

β
vol(W ) ≤ 0 vol(W )
1−β

for 0 ≥ β/(1 − β). Thus W is an 0 -spectral cluster in Gk representing i for 0 = max{β +
λ0 /(4d), β/(1 − β)} = max{β + /4, β/(1 − β)}. Thus by Theorem 1, A recovers a W 0 missing at
most 30 vol(W ) volume from W , and containing at most 22500000 volume from G\W . Note we
remove any vertex from W 0 of degree ≤ d/2, so W 0 contains at most 55000000 m vertices from
outside W . Furthermore, since there are at most βdm edges lost from W due to bad levels, at
most 2βm vertices in W had their degrees reduced to ≤ d/2, and thus removing low-degree vertices
removed at most 2βm additional vertices from W . Also, since the max degree in Gk is d and at
most a 2β fraction of vertices in W have ≤ d/2 degree, since W 0 is missing at most 30 vol(W )
vertices from W , this corresponds to at most 2βm + 60 m vertices missing from W . We then form
a (corrupted) codeword C 0 ∈ {0, 1}mt by concatenating encoding chunks specified by the vertices
in W 0 . Since then at most a (55000060 + 2β)-fraction of entries in enc(i) and C 0 differ, for , β
sufficiently small constants we successfully decode and obtain the binary encoding of i, which is
included in L.

Remark 1. It is possible to slightly modify our algorithm so that the ε−2 lg1+γ n summand in
the query time becomes ε−2 lg1+o(1) n. We state the modification here without providing the full
details. Specifically, rather than implement the Pjk as b-trees, one could instead implement them
as recursive versions of the ExpanderSketch on a smaller universe. Then, after a single level of
recursion down, one switches back to using b-trees. Then the b-trees at the second level of recursion
have query time which includes an arbitrarily small power of lg lg n, which is lgo(1) n. One may be
tempted to avoid b-trees altogether and simply continue the recursion to the leaves, but due to the
blowup in bitlength of the partition sizes stemming from concatenating hj values, it seems such an
∗
approach would result in the space complexity being multiplied by an additional 2O(lg n) factor.

14

6

Cluster-preserving clustering

In this section we present our cluster-preserving clustering, partitioning the graph into clusters with
the promise to preserve and identify all -spectral clusters as per Definition 1.
The main goal of this section is to prove Theorem 1. To prove Theorem 1, we shall use cuts
based on Cheeger’s inequality. Given an undirected graph G = (V, E), let its Laplacian matrix be
LG (normalized so that (LG )i,i = 1 for all i). It is known that that LG is positive semidefinite
with eigenvalues 0 = λ1 ≤ λ2 ≤ . . . ≤ λ|V | with λk = 0 iff G has at least k connected components.
A fundamental result in spectral graph theory is the following, which is a robust form of this fact
when k = 2.
Theorem 3 (Cheeger’s inequality for graphs [AM85, Alo86, SJ89]). For G = (V, E) an undirected
graph, let λ2 be the second smallest eigenvalue of LG . Then a cut (S, S) satisfying
p
p
λ2
≤ φ(G) ≤ φ(G, S) ≤ 2λ2 ≤ 2 φ(G)
2

(1)

can be found in time poly(|V |) and space O(|V | + |E|).
Algorithm 1 Top level of cluster preserving clustering of G0 as stated in Theorem 1.
1: function Main(G0 )
2:
{U1 . . . , U` } ← CutGrabClose(G0 )
3:
For each Ui , recursively remove v ∈ Ui with ≥ 5/9ths neigbors outside Ui .
. Cleaning
4:
return {U1 . . . , U` }
5: end function

Algorithm 2 Cluster preserving clustering of G = G0 |V , approximately isolating clusters W of
G0 .
1: function CutGrabClose(G = G0 |V )
2:
Use Theorem 3 to find a cut (S, S) satisfying Eq. (1); say |S| ≤ |S|.
3:
if φ(G, S) ≥ 1/500 then return {V }
. We’ve identified a potential cluster.
4:
else
5:
LocalImprovements(G, S, V )
. Local improvements of both S, S.
6:
Grab(G, S)
7:
LocalImprovements(G, S, S)
. Local improvements of S.
8:
Grab(G, S)
9:
LocalImprovements(G, S, S)
. Local improvements of S.
10:
LocalImprovements(G, S, S)
. Local improvements of S.
11:
C ←CutGrabClose(G|S) ∪ CutGrabClose(G|S)
12:
return C
13:
end if
14: end function
We are now ready to describe our algorithm, presented in pseudo-code in Algorithms 2–4.
At the top level, from Main, the function CutGrabClose is fed as input the graph G = (V, E)
from Theorem 1. We denote this top level graph G0 = (V0 , E0 ). CutGrabClose is a recursive
15

Algorithm 3 Local improvements across cut (S, S) only moving vertices from T .
function LocalImprovements(G, S, T )
. (S, S) is a cut in G = (V, E)
while ∃v ∈ T with at least 5/9ths of its edges crossing the cut do . Local improvement.
3:
Move v to the other side of the cut.
4:
end while
5: end function

1:

2:

Algorithm 4 Expanding S by grabbing all vertices with 1/6th neighbors in S.
1: function Grab(G, S)
2:
Let T be set of vertices from G \ V with at least 1/6th of its neighbors in S.
3:
S ← S ∪ T.
4: end function
algorithm, working on induced subgraphs G = G0 |V of G0 , producing a family of disjoint subsets
of the vertices. Suppose G0 has an -spectral cluster W . Our goal is to show that one set in the
final partition produced by CutGrabClose matches W in a slightly weaker sense than Theorem 1
(namely volUi (Ui \ W ) = O( vol(W )) instead of the second matching condition). At the end of the
section, we describe how the last cleaning step in Main removes extraneous mass from candidate
clusters and achieves the stronger conditions in Theorem 1.
On input G = (V, E), CutGrabClose works as follows: if there is no low-conductance cut,
it returns just the single-element partition {V }. Otherwise, it finds a low-conductance cut (S, S).
It then performs a sequence of recursive local improvements and two grabs to maintain certain
invariants in our analysis. Namely, we want to maintain the invariant that throughout all levels of
recursion, most of W stays in the same recursive branch. Here, by most of W , we mean relative to
the volume of W in the original G0 . This will ensure that the final output C of the topmost level
of recursion contains a single set S matching W .
We now proceed with a formal description. Since we will be talking both about the original
graph G0 and the recursive induced subgraphs G = G0 |V , we will sometimes use a subscript to
indicate which graph we are working in, e.g., if A ⊆ V , then volG (A) and volG0 (A) are the volumes
of A in G and G0 respectively. Since the subgraphs are all induced, the edge sets are always
determined from the vertices included.
Closure We say set A of vertices from G is closed in G if there is no vertex v ∈ G\A with at least
5/9 of its neighbors in A. The closure property is transitive, which is very useful for our recursion:
Lemma 3. If A ⊆ V ⊆ V (G0 ), A is closed in G0 |V , and V is closed in G0 , then A is closed in
G0 .
Proof. Suppose for a contradiction that we have a vertex v ∈ G0 \A with at least 5/9ths of its
neighbors in A. Then v also has 5/9ths of its neighbors in V , but V is closed in G0 , so v should be
in V . However, in G0 |V , the vertex v can only have lost neighbors from outside A, so in G0 |V , v
also has at least 5/9ths of its neighbors in A. This contradicts that A is closed in G0 |V .

We say that a vertex set A ⊆ V0 dominates the -spectral cluster W if volG0 (W ∩ V ) >
(1 − 3 ) volG0 (W ). We will show that if A is closed and has more than 2/3 of the volume of W ,
then it dominates W :
16

Lemma 4. If A is closed in G0 and volG0 (W ∩ A) ≥

2
3

volG0 (W ), then A dominates W .

Proof. By assumption r = volG0 (W \ A)/ volG0 (W ) ≤ 1/3. By the spectral expansion of W , we
have
E(W \ A, W ∩ A) ≥ (r(1 − r) − ) vol(W ) ≥ (1 − r − /r) vol(W \ A).
G0

G0

The average degree from W \ A to A is thus at least (1 − r − /r), which is bigger than 5/9 if
3 ≤ r ≤ 1/3 and  ≤ 1/27 (we have  < 1/2000000). This would contradict that A is closed, so we

conclude that r < 3, and hence that volG0 (W ∩ A)/ volG0 (W ) = 1 − r > 1 − 3.
We shall frequently use the fact that if V dominates W , then within V ∩ W , there is not much
difference between volume in G and G0 . More precisely,
Lemma 5. Consider an arbitrary set S ⊂ V . If V dominates W then volG0 (W ∩ V ) ≤ volG (W ∩
S) + 4  volG0 (W ).
Proof. The edges from W ∩ S in G0 that are not in G, are either edges leaving W , of which,
by isolation of W , there are at most  volG0 (W ), or edges to W \ V , of which there at at most
volG0 (W \ V ) = volG0 (W ) − volG0 (V ∩ W ) ≤ 3 volG0 (W ).

We now continue describing our algorithm to isolate W (plus any other -spectral cluster). As
our invariant, we are given some induced subgraph G = (V, E) of G0 such that
(1) V is closed in G0 .
(2) V dominates W .
To maintain this invariant, we want to show that CutGrabClose finds a cut (S, S) where both
sides are closed and one side dominates W . We also want to make sure that both sides are nonempty. By definition, this follows if the conductance is below 1, and we will, in fact, always keep
the conductance below 1/9.
The first step of CutGrabClose is to use Theorem 3 to find a cut (S, S) of G satisfying
Eq. (1); say |S| ≤ |S| (line 2 of Algorithm 2). If φ(G, S) ≥ 1/500, we will just return {V }. The
following lemma states that V does not have too much volume in G outside W .
Lemma 6. If φ(G, S) ≥ 1/500, then volG (V \ W ) ≤ 1000000  volG0 (W ).
Proof. By isolation of the -cluster W in G0 , we have |∂G0 (W )| ≤  volG0 (W ). However, ∂G (V \
W ) = ∂G (V ∩ W ) ⊆ ∂G0 (W ), so |∂G (V \ W )| ≤  volG0 (W ).
Suppose volG (V \ W ) > 1000000  volG0 (W ). We want to conclude that φ(G, V \ W ) <
1/1000000. To do that, we also need to argue that volG (V ∩ W ) > 1000000  volG0 (W ). Since
V dominates W , we have volG0 (V ∩ W ) > (1 − 3 ) volG0 (W ) and by Lemma 5, we have
vol(V ∩ W ) ≥ vol(V ∩ W ) − 4  vol(W ) ≤ (1 − 7 ) vol(W ) > 1000000  vol(W ).
G

G0

G0

G0

G0

The last equality follows because  ≤ 1/2000000. We have now proved that volG (V \ W ) >
1000000  volG0 (W ) implies that φ(G) ≤ φ(G,
p V \ W ) < 1/1000000. By Eq. (1) this contradicts
that we did not find a cut of size less than 2 φ(G) < 1/500.

The last cleaning in Main will reduce the volume of V \ W in G0 as required for Theorem 1.
We shall return to that later. Below we assume that we found a low conductance cut (S, S) of G
with φ(G, S) ≤ 1/500. We are going to move vertices between S and S, and will always maintain
a conductance below 1/9.
17

Local improvements towards closure We are now going to move vertices between S and S
to make sure that W is mostly contained in one side. As a first step, we will make sure that both
sides are closed (line 5 of Algorithm 2). This is done iteratively. If one vertex has at least 5/9ths
fraction of its neighbors on the other side of the cut, we move it to the other side, calling it a local
improvement (c.f. Algorithm 3). When no more local improvements are possible, both sides S and
S must be closed in G. We call these moves improving because they always improve both cut size
and conductance, as described more formally below.
Lemma 7. Consider a local improvement moving a vertex v. It reduces the cut size by at least
dG (v)/9. It also improves the conductance if it was below 1/9 before the move.
Proof. When we move v, we replace at least 95 dG (v) cut edges by at most 49 dG (v) cut edges,
reducing the cut size by at least dG (v)/9. The volume moved is dG (v), so if φ(G, S) < 1/9 and the
0
new cut is (S 0 , S ), we get
φ(G, S 0 ) =

|∂G (S 0 )|
min{volG

(S 0 ), vol

G (S

0

)}

≤

|∂G (S)| − dG (v)/9
< φ(G, S).
min{volG (S), volG (S)} − dG (v)


When both sides are closed under local improvements, we have a situation where either W is
almost completely dominated by one side, or it roughly balanced between the two sides. More
precisely,
Lemma 8. When both S and S are closed in G (and hence in G0 ), then either volG0 (S ∩ W ) <
3  volG0 (W ), or (1/3 − 3 ) volG0 (W ) < volG0 (S ∩ W ) < (2/3) volG0 (W ), or volG0 (S ∩ W ) >
(1 − 3 ) volG0 (W ).
Proof. This follows almost directly from Lemma 4. We just note that since volG0 (S ∩ W ) +
volG0 (S ∩ W ) = volG0 (V ∩ W ) ≥ (1 − 3 ) volG0 (W ), if volG0 (S) ≤ (1/3 − 3 ) volG0 (W ), then
volG0 (S ∩ W ) ≥ 2/3 volG0 (W ), and then, by Lemma 4, we have volG0 (S ∩ W ) > (1 − 3 ) volG0 (W ),
and hence volG0 (S ∩ W ) < 3  volG0 (W ).

Grabbing for dominance Having made sure that both sides are closed, as described in Lemma 8,
we now have W either almost completely dominated by one side, or roughly balanced between both
sides. We will now introduce a grab operation (c.f. Algorithm 4) that in the balanced case will
help S get dominance. The grab operation itself is simple. In one round, it moves every vertex
to S that before the grab has more than 1/6th of its neighbors in S. An important point here is
that contrary to the local improvements, the grabbing is not recursive. We are actually going to do
this grabbing twice, interspersed with local improvements (c.f., Algorithm 2): First we grab from
S, then we do local improvements of S, only moving vertices to S, thus only closing S. We do this
grabbing followed by local improvements from S twice, calling it the big expansion of S (Algorithm
2 lines 6–9). Finally we do local improvements of S. We will prove that when all this is completed,
then one of the two sides dominate W , but first we have to argue that the conductance stays low.
Lemma 9. With the above grabs and local improvements, the conductance always stays below 1/9.
Proof. Our starting point is a Cheeger cut (S, S) with conductance φ(G, S) ≤ 1/500. From
Lemma 7 will never increase the conductance if it is below 1/9. Thus, it is only the grabs that can
18

increase the conductance. Let S 0 be the result of the grab from S. We know that all the vertices
grabbed from S have at least 1/6th of their neighbors in S. This means that |∂G (S 0 )| ≤ 5|∂G (S)|
and volG (S 0 ) ≤ volG (S) + 6∂G (S). It follows that
φ(G, S 0 ) ≤

5|∂G (S)|
|∂G (S 0 )|
≤
0
0
min{volG (S), volG (S)} − 6|∂G (S)|
min{volG (S ), volG (S )}
5
5|∂G (S)|
=
≤
φ(G, S).
(1 − 6φ(G, S))
(1 − 6φ(G, S)) min{volG (S), volG (S)}

Before the first grab, we have conductance below 1/500, which the grab now increases to at most
6/((1 − 6/500)500) < 1/80. The second grab can then increase the conductance to at most 6/((1 −
6/80)80) < 1/12, so, in fact, the conductance will always stay below 1/12.

Below we first argue that if we started with balance, then after the big expansion of S, we have
volG0 (S ∩ W ) ≥ (1 − 3 ) volG0 (W ).
Lemma 10. If S is closed and volG0 (W \ S) ≤ (2/3) volG0 (W ), then S dominates W after the big
expansion from S.
Proof. Let r = volG0 (W \ S)/ volG0 (W ) ≤ 2/3. If we can show that the big expansion of
S brings r ≤ 1/3 − 3 , then we are done by Lemma 4 since S is closed and volG0 (S ∩ W ) ≥
(1 − r − 3 ) volG0 (W \ S).
We study the effect of a single grab from a closed set S. By spectral expansion, we have
|E(W \ S, S ∩ W )| ≥ (r(1 − r) − ) volG0 (W ).
Let T be the set of vertices from W moved by the grab, that is, T is the set of vertices from
W \ S with at least 1/6th of their neigbors in S. Also, let B be the set of vertices from W \ S that
are not moved, that is, B = W \ (S ∪ T ). Then
|E(S ∩ W, B)| ≤ |E(S, B)| < vol(B)/6 ≤ vol(W \ S)/6 = r vol(W )/6.
G

G0

G0

The number of edges from S ∩ W to vertices from W \ S that will be grabbed is therefore at least
|E(S∩W, T )| = |E(S∩W, W \S)|−E(S∩W, B) ≥ (r(1−r)− −r/6) vol(W ) = (5r/6−r2 − ) vol(W ).
G0

G0

The function f (r) = 5r/6 − r2 is convex, having its minimum over any interval in its end points.
We are only concerned with r ∈ [(1/3 − 3 ), 2/3], where the smallest value is f (2/3) = 1/9. The
number of edges to grabbed vertices is thus |E(S ∩ W, T )| ≥ (1/9 − ) volG0 (W ).
We also know that before a grab, the set S is closed. Therefore, every vertex v outside S has
less than 59 dG (v) edges going to S, and no more going to S ∩ W . We conclude that
9
9
vol(T ) ≥ vol(T ) ≥ |E(S ∩ W, T )| ≥ (1/9 − ) vol(W ) ≥ (1/5 − 2 ) vol(W ).
G0
G
G0
G0
5
5
Each grab thus decreases r = volG0 (W \S)/ volG0 (W ) by (1/5−2 ). Starting from r ≤ 2/3, with two
grabs followed by local improvements of S, we thus end up with r ≤ 2/3 − 2(1/5 − 2 ) ≤ 4/15 + 4 .
This is less than the desired 1/3 − 3  if  < 1/105, which is indeed the case.

Next, we will show that S dominated W before the big expansion of S, then S will also dominate
W at the end.
19

Lemma 11. Suppose that S and S are closed and that S dominate W . Then S will also dominate
W after a big expansion from S followed by local improvements of S.
Proof. We want to show that after the big expansion of S, we still have volG0 (W ∩S) ≥ 23 volG0 (W ).
This can only increase when we subsequently do local improvements of S, closing S, and then the
result follows from Lemma 4.
Stepping back to S before the big expansion, we are trying to bound how much volume from
volG (W \ S) that can be moved to S. Both for local improvements and for grabbing, the chance of
moving v to S increases the more neighbors v has in S. Thus, we maximize the potential of moving
vertices from W to S if we assume that we start with all of V \ W in S. The only cut edges are
now those between S and W \ S.
When a local improvement moves a vertex v to S, we replace at least 95 dG (v) cut edges with at
most 49 dG (v) cut edges while increasing volG (W ∩ S) by dG (v). It follows that if local improvements
increase volG (S) by x, then they decrease |∂G (S)| by at least x/9.
When we grab a set T of vertices to S, we know that each vertex v ∈ T had at least 16 dG (v) of
its edges to S. When the grab is done, setting S 0 = S ∪ T , we have at most 56 dG (v) edges from v to
W \ S 0 . We conclude that |∂G (S 0 )| ≤ 5|∂G (S)| and that volG (S 0 ) ≤ volG (S) + 6|∂G (S)|. Subsequent
local improvements can further increase the volume by at most 9|∂G (S 0 )| ≤ 45|∂G (S)|. Thus, when
we from S do one grab followed by local improvements, we increase the volume volG (S) by at most
51|∂G (S)|.
We now note that if we did local improvements of S before the grab, then we would only get
a smaller bound. More precisely, if the the local improvements moved volume x to volG (S), then
|∂G (S)| would be reduced by x/9 before the grab, and then the total volume increase would be at
most x + 51(|∂G (S)| − x/9) ≤ 51|∂G (S)|.
We now study the big expansion from S, starting with a grab followed by any number of local
improvements followed by another grab followed any number of local improvements. From the above
analysis, it follows that the total increase in volG (S) is at most 6|∂G (S)|+51·5|∂G (S)| ≤ 261|∂G (S)|.
This bounds the total volume moved from volG (W \ S) to volG (S).
We started with volG (W ∩ S) ≤ 3  volG0 (W ). Also, originally, before the big expansion, the set
S was closed, so vertices from S had less than a fraction 5/9 of their neighbors in S. This fraction
could only be reduced when we artificially added all of V \W to S. After this artificial change, which
only improved movement of vertices from W \ S to S, we had |∂S| ≤ 59 volG (W ∩ S) + |∂G (W )| ≤
(5/3 + 1) volG0 (W ). Thus, after the big expansion, we end up with
vol(W ∩ S) ≤ (3 + 261(5/3 + 1) vol(W ) < 699  vol(W ).
G

G0

G0

Finally, by Lemma 5, we have volG0 (W ∩ S) ≤ volG (W ∩ S) + 4  volG0 (W ) ≤ 703  volG0 (W ),
which with  ≤ 1/1000000, is much less than the required (1/3 − 3 ) volG0 (W ).

Finally we need
Lemma 12. Suppose that S is closed and dominates W . Then both of these properties are preserved
if we do local improvements of S.
Proof. It sufficies to consider a local improvement moving a single vertex v to S.
First we show that S being closed is preserved when we do a local improvement from S moving
a vertex v to S. Suppose for contradiction that we afterwards had some vertex u ∈ S with 5/9ths
20

of its neighbors in S. Then we cannot have u = v; for we moved v because it had 5/9ths of its
neighbors in S. However, any other u 6= v can only have fewer neighbors in S after the move.
Since S starts dominating, we start with volG0 (W \ S) ≤ 3  volG0 (W ). The dominance can
only be affected if v ∈ W , and we only move v to S because it has at least 5/9ths of its neighbors
in S. Trivially v can have at most volG0 (W ∩ S) + |∂G0 (W )| ≤ 4  volG0 (W ) neighbors in S, so
we conclude that dG (v) ≤ 95 · 4  volG0 (W ) < 8  volG0 (W ), and by Lemma 5, we have dG0 (v) ≤
dG (v) + 4  volG0 (W ) < 12  volG0 (W ). Thus we end up with volG0 (W \ S) < 15  volG0 (W ). This
is much less that (1/3 − 3 ) volG0 (W ). Since S remains closed, we conclude from Lemma 4 that S

still dominates W , hence that volG0 (W \ S) ≤ 3  volG0 (W ).
Let us now sum up what we have proved. Suppose we found an initial cut (S, S) of conductance
below 1/500. This is when we start modifying the cut, and we need to show that our invariants
are preserved for the recursive calls.
By Lemma 12, the local improvements of S followed by the final local improvements of S imply
that both sets end up closed, so invariant (1) is satisfied. The hard part was ensure that one side
dominates W . We had Lemma 9 showing that we keep the conductance below 1/9. First we did
local improvements of both sides. By Lemma 8, we end up either with one side dominating W , or
with W roughly balanced between the sides. If W is balanced or dominated by S, then after by
big expansion from S, by Lemma 10, S dominates W . By Lemma 12, this dominance is preserved
when we do the final local improvements of S. If instead S dominated W , then, by Lemma 11 this
is dominance is preserved. Thus we always end up with one side dominating W , so invariant (2) is
satisfied. We conclude that W is always dominated by one branch of the recursion.
The recursion finishes when no small cut is found. We have V dominating S, and by Lemma 6,
we have volG (V \ W ) ≤ 1000000  volG0 (W ). Thus we have proved
Theorem 4. For any given  ≤ 1/2000000 and graph G0 , in polynomial time, CutGrabClose
(Algorithm 2) finds a partitioning {U1 , . . . U` } of the vertex set so that every -spectral cluster W
of G0 matches some set Ui in the sense that
• vol(W \ Ui ) ≤ 3  vol(W ).
• volG0 |Ui (Ui \ W ) ≤ 1000000  vol(W )
The only detail missing in proving Theorem 1 is that we want a bound on volG0 (Ui \ W ) rather
than volG0 |Ui (Ui \ W ). This is where the last cleaning of Main (Algorithm 1) comes in. It removes
all vertices from Ui with more than 5/9ths of their neighbors outside Ui , so now, for all v ∈ Ui , we
have dG0 (v) ≤ 94 dG0 |Ui (v).
Lemma 13. The cleaning of Ui preserves that Ui dominates W , and now volG0 (Ui \ W ) ≤
9
4 volG0 |Ui (Ui \ W ) ≤ 225000000  vol(W ).
Proof. Recall that Ui before the cleaning is closed and dominates W . The cleaning has exactly
the same effect as if we did local improvements of V (G0 ) \ Ui , so by Lemma 12, we preserve both
that Ui is closed, and that it dominates W .

Theorem 4 and Lemma 13 immediately imply the statement of Theorem 1.

Acknowledgments
We thank Noga Alon for pointing us to [AC88, Lemma 2.3], Jonathan Kelner for the reference
[OSV12], Lorenzo Orecchia and Sushant Sachdeva for answering several questions about [OV11,
21

OSV12], Piotr Indyk for the reference [GLPS14], Graham Cormode for the reference [Pag13], Yi
Li for answering several questions about [GLPS14], Mary Wootters for making us aware of the
formulation of the list-recovery problem in coding theory and its appearance in prior work in
compressed sensing and group testing, Atri Rudra for useful discussions on list-recovery algorithms
for Parvaresh-Vardy and Folded Reed-Solomon codes, and Fan Chung Graham and Olivia Simpson
for useful conversations about graph partitioning algorithms.

References
[AC88]

Noga Alon and Fan R. K. Chung. Explicit construction of linear sized tolerant networks.
Discrete Mathematics, 72:15–19, 1988.

[AKO11]

Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via
precision sampling. In 52nd Annual Symposium on Foundations of Computer Science
(FOCS), pages 363–372, 2011.

[Alo86]

Noga Alon. Eigenvalues and expanders. Combinatorica, 6:83–96, 1986.

[AM85]

Noga Alon and Vitali Milman. Isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73–88, 1985.

[AMFM11] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis
and Machine Intelligence, 33(5):898–916, 2011.
[AP09]

Reid Andersen and Yuval Peres. Finding sparse cuts locally using evolving sets. In
Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC),
pages 235–244, 2009.

[ARV09]

Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009.

[ASS08]

Noga Alon, Oded Schwartz, and Asaf Shapira. An elementary construction of constantdegree expanders. Combinatorics, Probability and Computing, 17(3):319–327, May
2008.

[BC15]

Vladimir Braverman and Stephen R. Chestnut. Universal sketches for the frequency
negative moments and other decreasing streaming sums. In RANDOM, pages 591–605,
2015.

[BCI+ 16]

Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, Jelani Nelson, David P
Woodruff, and Zhengyu Wang. BPTree: an `2 heavy hitters algorithm using constant
memory. abs/1603.00759, 2016.

[BCIW16] Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff. Beating CountSketch for heavy hitters in insertion streams. In Proceedings of the 48th
Annual ACM Symposium on Theory of Computing (STOC), to appear, 2016.

22

[BDW16]

Arnab Bhattacharyya, Palash Dey, and David P. Woodruff. An optimal algorithm
for `1 -heavy hitters in insertion streams and related problems. In Proceedings of the
35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
(PODS), 2016.

[BICS10]

Radu Berinde, Piotr Indyk, Graham Cormode, and Martin J. Strauss. Space-optimal
heavy hitters with strong error bounds. ACM Trans. Database Syst., 35(4):26, 2010.

[BKSV14]

Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger. An
optimal algorithm for large frequency moments using O(n1−2/k ) bits. In RANDOM,
pages 531–544, 2014.

[BO10]

Vladimir Braverman and Rafail Ostrovsky. Zero-one frequency laws. In Proceedings of
the 42nd ACM Symposium on Theory of Computing (STOC), pages 281–290, 2010.

[BO13]

Vladimir Braverman and Rafail Ostrovsky. Approximating large frequency moments
with pick-and-drop sampling. In APPROX, pages 42–57, 2013.

[BYJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci.,
68(4):702–732, 2004.
[CCFC04]

Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in
data streams. Theor. Comput. Sci., 312(1):3–15, 2004.

[CCM10]

Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A near-optimal algorithm for estimating the entropy of a stream. ACM Transactions on Algorithms, 6(3),
2010.

[CH08]

Graham Cormode and Marios Hadjieleftheriou. Finding frequent items in data streams.
PVLDB, 1(2):1530–1541, 2008.

[Che09]

Mahdi Cheraghchi. Noise-resilient group testing: Limitations and constructions. In
17th International Symposium on Fundamentals of Computation Theory (FCT), pages
62–73, 2009.

[CJK+ 04]

Graham Cormode, Theodore Johnson, Flip Korn, S. Muthukrishnan, Oliver
Spatscheck, and Divesh Srivastava. Holistic UDAFs at streaming speeds. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages
35–46, 2004.

[CM05]

Graham Cormode and S. Muthukrishnan. An improved data stream summary: the
count-min sketch and its applications. J. Algorithms, 55(1):58–75, 2005.

[CW79]

Larry Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput.
Syst. Sci., 18(2):143–154, 1979.

[DKN10]

Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson. Bounded independence fools
degree-2 threshold functions. In Proceedings of the 51th Annual IEEE Symposium on
Foundations of Computer Science (FOCS), pages 11–20, 2010.
23

[DLM02]

Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Frequency estimation of
internet packet streams with limited space. In Proceedings of the 10th Annual European
Symposium on Algorithms (ESA), pages 348–360, 2002.

[FSG+ 98]

Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman. Computing iceberg queries efficiently. In Proceedings of 24rd International Conference on Very Large Data Bases (VLDB), pages 299–310, 1998.

[Gan15]

Sumit Ganguly. Taylor polynomial estimator for estimating frequency moments. In
42nd International Colloquium on Automata, Languages, and Programming (ICALP),
pages 542–553, 2015.

[GB09]

Sumit Ganguly and Lakshminath Bhuvanagiri. Hierarchical sampling from sketches:
Estimating functions over data streams. Algorithmica, 53(4):549–582, 2009.

[GLPS14]

Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. For-all sparse recovery in
near-optimal time. In 41st International Colloquium on Automata, Languages, and
Programming (ICALP), pages 538–550, 2014.

[GNP+ 13] Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, and Martin J. Strauss. `2 /`2 foreach sparse recovery with low risk. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 461–472, 2013.
[GR09]

Parikshit Gopalan and Jaikumar Radhakrishnan. Finding duplicates in a data stream.
In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 402–411, 2009.

[GT12]

Shayan Oveis Gharan and Luca Trevisan. Approximating the expansion profile and
almost optimal local graph clustering. In Foundations of Computer Science (FOCS),
2012 IEEE 53rd Annual Symposium on, pages 187–196. IEEE, 2012.

[GT14]

Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In Proceedings
of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
1256–1266, 2014.

[HNO08]

Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming
entropy via approximation theory. In 49th Annual IEEE Symposium on Foundations
of Computer Science (FOCS), pages 489–498, 2008.

[HW15]

Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander
codes. In 42nd International Colloquium on Automata, Languages, and Programming
(ICALP), pages 701–712, 2015.

[INR10]

Piotr Indyk, Hung Q. Ngo, and Atri Rudra. Efficiently decodable non-adaptive group
testing. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1126–1142, 2010.

[IW05]

Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments
of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of
Computing (STOC), pages 202–208, 2005.
24

[JST11]

Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for Lp samplers,
finding duplicates in streams, and related problems. In Proceedings of the 30th ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS),
pages 49–58, 2011.

[JW09]

T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded
norms. In 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 765–774, 2009.

[KNPW11] Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. Fast moment estimation in data streams in optimal space. In Proceedings of the 43rd ACM Symposium
on Theory of Computing (STOC), pages 745–754, 2011.
[KNW10]

Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity
of sketching and streaming small norms. In Proceedings of the Twenty-First Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1161–1178, 2010.

[KVV04]

Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and
spectral. J. ACM, 51(3):497–515, 2004.

[LCG13]

Yang Liu, Wenji Chen, and Yong Guan. Identifying high-cardinality hosts from
network-wide traffic measurements. In IEEE Conference on Communications and Network Security, (CNS), pages 287–295, 2013.

[LNN15]

Kasper Green Larsen, Jelani Nelson, and Huy L. Nguy˜ên. Time lower bounds for nonadaptive turnstile streaming algorithms. In Proceedings of the Forty-Seventh Annual
ACM on Symposium on Theory of Computing (STOC), pages 803–812, 2015.

[LR88]

Tom Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms.
In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 422–431, 1988.

[MG82]

Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program.,
2(2):143–152, 1982.

[MMV12]

Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Proceedings of the 44th
Annual ACM Symposium on Theory of Computing Conference (STOC), pages 367–384,
2012.

[MMV14]

Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Constant
factor approximation for balanced cut in the PIE model. In Proceedings of the 46th
Annual ACM Symposium on Theory of Computing (STOC), pages 41–49, 2014.

[Mut05]

S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and
Trends in Theoretical Computer Science, 1(2), 2005.

[MW10]

Morteza Monemizadeh and David P. Woodruff. 1-pass relative-error Lp -sampling with
applications. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 1143–1160, 2010.
25

[NNW14]

Jelani Nelson, Huy L. Nguy˜ên, and David P. Woodruff. On deterministic sketching
and streaming for sparse recovery and norm estimation. Lin. Alg. Appl., 441:152–167,
January 2014. Preliminary version in RANDOM 2012.

[NPR12]

Hung Q. Ngo, Ely Porat, and Atri Rudra. Efficiently decodable compressed sensing by
list-recoverable codes and recursion. In 29th International Symposium on Theoretical
Aspects of Computer Science (STACS), pages 230–241, 2012.

[NW10]

Jelani Nelson and David P. Woodruff. Fast manhattan sketches in data streams. In
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on
Principles of Database Systems (PODS), pages 99–110, 2010.

[OSV12]

Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the
exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced
separator. In Proceedings of the 44th Symposium on Theory of Computing Conference,
(STOC), pages 1141–1160, 2012.

[OV11]

Lorenzo Orecchia and Nisheeth K. Vishnoi. Towards an SDP-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 532–545, 2011.

[Pag13]

Rasmus Pagh. Compressed matrix multiplication. TOCT, 5(3):9, 2013.

[PDGQ05] Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan. Interpreting the data:
Parallel analysis with Sawzall. Scientific Programming, 13(4):277–298, 2005.
[PSZ15]

Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral
clustering works! In Proceedings of The 28th Conference on Learning Theory (COLT),
pages 1423–1455, 2015.

[RS10]

Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC),
pages 755–764, 2010.

[RVW02]

Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph
product, and new constant-degree expanders. Annals of Mathematics, 155(1):157–187,
2002.

[SJ89]

Alistair J. Sinclair and Mark R. Jerrum. Approximative counting, uniform generation
and rapidly mixing Markov chains. Information and Computation, 82(1):93–133, 1989.

[SM00]

Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000.

[Spi96]

Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE
Trans. Information Theory, 42(6):1723–1731, 1996.

[ST04]

Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph
partitioning, graph sparsification, and solving linear systems. In Proceedings of the
36th Annual ACM Symposium on Theory of Computing (STOC), pages 81–90, 2004.
26

Appendix
A

Heavy hitters reduction from small to large 

The main theorem of this section is the following.
Theorem 5. Let 0 < , δ < 1/2 be such that 1/2 > lg(1/δ). Then there is a reduction from
turnstile
`2 heavy hitters with parameter  and failure probability δ to z = d1/(2 lg(1/δ))e separate
√
(1/ t)-heavy hitters problems for t = C lg(1/δ) for some constant C > 0, and where each such
0
problem must
√ be solved with failure probability at most δ = δ/(3z). Specifically, given an algorithm
for the (1/ t)-heavy hitters problem with these parameters using space S, update time tu and query
time tq , the resulting algorithm for -heavy hitters from this reduction uses space O(z · S + lg(1/δ)),
and has update time tu + O(lg(1/δ)) and query time O(z · tq ).
Proof. We pick a hash function h : [n] → [z] at random from a Θ(lg(1/δ))-wise independent family
as in [CW79]. Such h requires O(lg(1/δ))
√ space to store and can be evaluated in O(lg(1/δ)) time.
We also instantiate z independent (1/ t)-heavy hitter data structures P1 , . . . , Pz each with failure
probability δ 0 . Upon receiving an update (i, v) in the stream, we feed the update (i, v) to Ph(i) . To
answer a query, we first query each Pj to obtain a list Lj , then we output L = ∪zj=1 Lj .
This concludes the description of the data structures stored, and the implementations of update
and query. The space bound and running times thus follow.
We now argue correctness. Let H be the set of -heavy hitters of x, so that |H| ≤ 2/2 . It
follows by the Chernoff bound and union bound over all j ∈ [z] that, for some constant C > 0,
P(∃j ∈ [z], |H ∩ h−1 (j)| > C lg(1/δ)) < δ/3.
h

(2)

We next invoke Bernstein’s inequality, which says there exists constant
c > 0 such that for indeP
pendent X1 , . . . , Xr each bounded by K in magnitude with σ 2 = i E(Xi − E Xi )2 ,
X
X
2
2
∀λ > 0, P(|
Xi − E
Xi | > λ) . e−cλ /σ + e−cλ/K .
i

i

We will consider the collection of random variables Xi indexed by i ∈ [n]\H defined as follows (so
r = n − |H|). Fix j ∈ [z]. Define Xi = 1h(i)=j · x2i . It then follows that K < 2 · kx[1/2 ] k22 and
σ2 =

X

x4i (1/z − 1/z 2 ) ≤

i∈H
/

X
2
2
· kx[1/2 ] k22 ·
x2i =
· kx[1/2 ] k42
z
z
i∈H
/

It then follows by Bernstein’s inequality and a union bound over all j ∈ [z] that
X
x2i > C2 lg(1/δ)kx[1/2 ] k22 ) < δ/3.
P(∃j ∈ [z],
h

(3)

i∈H
/
h(i)=j

Now, the hash function h divides the input stream into z separate substreams, with x(j) denoting the vector updated by the substream containing i with h(i) = j (i.e. (x(j))i = 1h(i)=j · xi ).
Conditioned on the events of (2), (3) occurring, we have that any i ∈ H satisfies x2i ≥ 2 kx[1/2 ] k22 ≥
1/(C lg(1/δ)) · kx(h(i))[C lg(1/δ)] k22 . Thus if we also condition on every Pj succeeding, which happens
with probability at least 1 − zδ 0 = 1 − δ/3 by a union bound, then our output L is correct. Thus
our overall failure probability is at most δ.

27

B

Partition heavy hitters and the b-tree

We first define a generalization of the heavy hitters problem that we call partition heavy hitters.
The standard heavy hitters problem is simply the special case when P = {{1}, . . . , {n}}, and the
oracle O is the identity map.
Definition 2. In the `2 partition heavy hitters problem there is some error parameter  ∈ (0, 1/2).
There is also some partition P = {S1 , . . . , SN } of [n], and it is presented in the form of an oracle
O : [n] → [N ] such that for any i ∈ [n], O(i) gives the index j ∈ [N ] such that i ∈ Sj . Define a
vector y ∈ RN such that for each j ∈ [N ],
sX
yj =
x2i .
i∈Sj

The goal then is to solve the `2 -heavy hitters problem on y subject to streaming updates to x. That
is, x is being updated in a stream, and we should at the end output a list L ⊂ [N ], |L| = O(1/2 ),
such that L contains all the -heavy hitters of y.
A related problem is the `2 partition point query problem, in which queries takes as input some
j ∈ [N ] and must output a value ỹj such that α1 yj − ky[1/2 ] k2 ≤ ỹj ≤ α2 yj + ky[1/2 ] k2 for some
approximation parameters α1 , α2 , . We call such a solution an (α1 , α2 , )-partition point query
algorithm.
We now describe the b-tree, introduced in [CH08] (and also called the Hierarchical CountSketch there and in other parts of the literature) and analyze its performance for solving the
partition heavy hitters problem. The b-tree was only suggested in [CH08] for the strict turnstile
model, and a detailed analysis was not given. Here we give a fully detailed analysis showing that,
in fact, that structure gives good guarantees even in the general turnstile model, and even for the
partition heavy hitters problem. Before delving into the b-tree, we will analyze the performance of
the PartitionCountSketch, a very slight modification of the CountSketch, for the partition
point query problem.

B.1

PartitionCountSketch

In the idealized PartitionCountSketch one chooses independent hash functions h1 , . . . , hL :
[N ] → [k] and σ1 , . . . , σL : [N ] → {−1, 1} from pairwise independent families, and β1 , . . . , βL :
[n] → R independently from a Cα -wise independent family for some small constant α > 0. The
marginal distribution of βt (i) for P
any i ∈ [n] and t ∈ [L] is the standard gaussian N (0, 1), and Cα
n
is chosen so that for any z ∈ R , i zi βt (i) has Kolmogorov distance at most α from N (0, 1) (see
Theorem 6). One also initializes counters Ca,b to 0 for all (a, b) ∈ [L] × [k], each consuming one
machine word. The space is then clearly O(kL) machine words.
The update algorithm for xi ← xi +∆ performs the change Ct,ht (O(i)) ← Ct,ht (O(i)) +∆·σt (O(i))·
βt (i) for each t ∈ [L]. To answer an `2 point query to index i ∈ [N ], one outputs ỹi being the median
value of |Ct,ht (i) | across t. In the actual, non-idealized version of PartitionCountSketch, the
marginal distribution of each βt (i) is a discretized gaussian with precision fitting in a single machine
word; see [KNW10, Section A.6] for details. We henceforth just discuss the idealized version. In
fact, for the types of instances of partition heavy hitters that our heavy hitters algorithm needs
to solve, the βt can be replaced with pairwise independent hash functions mapping to {−1, 1} (see
28

Remark 2), which would make an implementation less complicated. We instead have chosen to
analyze the version with gaussians since doing so then does not require us to limit the types of
partition heavy hitter instances we can handle, thus providing a more general guarantee that may
prove useful as a subroutine in future works.
Before analyzing PartitionCountSketch, we state a useful theorem from [KNW10].
Theorem 6. [KNW10] Let z ∈ Rn and 0 < α < 1 be arbitrary. There exists a constant Cα
depending on α such that if β1 , . . . , βn are Cα -wise independent standard gaussians and g is standard
gaussian, then
X
∀A < B ∈ R, | P(
βi zi ∈ [A, B]) − P(g ∈ [A, B])| < α.
i

In fact Cα can be taken as some value in O(1/α2 ) by combining the FT-mollification construction in [DKN10] with Lemma 2.2 and the argument in the proof of Theorem 2.1 in [KNW10].
Using the FT-mollification construction in [KNW10] would imply the weaker statement that Cα =
Ω(lg6 (1/α)/α2 ) suffices. In our current setting either is acceptable since α is some fixed constant.
The following lemma shows the correctness of PartitionCountSketch, following an argument similar to that of [CCFC04, Lemma 3].
Lemma 14. For L & lg(1/δ) and k & 1/2 ,
∀j ∈ [N ], P(ỹj ∈
/ [(1/20)yj − ky[1/2 ] k2 , 3yj + ky[1/2 ] k2 ]) < δ.

(4)

That is, the PartitionCountSketch with these parameters is an (α1 , α2 , )-partition point query
structure with failure probability δ, for α1 = 1/20, α2 = 3.
P
Proof. For t ∈ [L], define wt ∈ RN with (wt )j = i∈Sj βt (i)xi . Then by Theorem 6, P((wt )j ∈
p
[−α1 , α2 ]) ≤ P(yj g ∈ [−α1 , α1 ]) + α1 for g a standard gaussian. Since P(|g| ≤ ) ≤  2/π for any
 > 0,
p
P(|(wt )j | > α1 yj ) ≥ 1 − α1 (1 + 2/π) > 8/9.
(5)
Also by pairwise independence of βt , E(wt )2j = yj2 , so
P(|(wt )j | > α2 yj ) < 1/α22 = 1/9.

(6)

Next, let H ⊂ [N ] be the set of indices of top 1/(42 ) entries of y in magnitude. Note
E |

ht ,βt

X

1
βt (i)xi | ≤ √ · ky[1/2 ] k2
k
(j)

ht (O(i))=ht
O(i)∈H∪{j}
/

by pairwise independence of βt , ht . Thus
X
P (|
ht ,βt

βt (i)xi | > ky[1/2 ] k2 ) < 1/9

(7)

ht (O(i))=ht (j)
O(i)∈H∪{j}
/

by Markov’s inequality. Also Eht |h−1
t (ht (j)) ∩ (H\{j})| ≤ |H|/k < 1/9, so
P(∃j 0 ∈ (H\{j}) : ht (j 0 ) = ht (j)) < 1/9
29

(8)

by Markov’s inequality. Thus by a union bound, the conditions of (5), (6), (7), and (8) all happen
simultaneously with probability at least 5/9. Now note when all these events occur,
|Ct,ht (j) | ∈ [α1 yj − ky[1/2 ] k2 , α2 yj + ky[1/2 ] k2 ]

(9)

Thus by a chernoff bound, the probability that the median over t ∈ [L] of |Ct,ht (j) | does not satisfy
(9) is exp(−Ω(l)) < δ.

Remark 2. It is possible to obtain the main result of this paper, i.e. our bounds for (non-partition)
heavy hitters, without ever making use of Theorem 6. This might be useful for pedagogical reasons,
since the proof of Theorem 6 is somewhat complicated. We sketch how to do so here. We chose
to present the approach above since it divides our final algorithm into a more abstracted set of
subproblems, which we felt made it easier to describe. Furthermore, the “partition heavy hitters”
problem as formulated above seems quite clean and may find uses as a subroutine elsewhere.
The main idea to avoid Theorem 6 is as follows. First, in our application of partition heavy
hitters to solve the vanilla heavy hitters problem (see the proof of Theorem 2), we are only interested
in the case where each partition Sj in P contains at most one -heavy hitter i ∈ [n] with respect to
x. Furthermore, the other items in the same partition will, with good probability over the choice
of the hash function hj used in the ExpanderSketch, have much smaller total `2 mass than |xi |.
These observations can be used to show that, for applying partition heavy hitters to heavy hitters
as in Theorem 2, the βt above can be replaced with pairwise independent hash functions mapping
to {−1, 1}. This ensures that the “noise”, i.e. the non-heavy indices in the same partition as i,
with say 8/9 probability do not subtract much away from |xi | so that |(wt )j | will be Ω(|xi |). Note
that in the general partition heavy hitters problem the range of the βt cannot just be {−1, 1}. The
reason is that we want (5), (6), (7), and (8) to hold simultaneously with some probability strictly
larger than 1/2, to allow invoking Chernoff. However, (5) alone can fail with probability at least
1/2 even when using fully independent βt : [n] → {−1, 1}. For example, consider when a partition
j ∈ [N ] contains exactly two elements with equal weight. Then with probability 1/2 their signs are
opposite, in which case (wt )j equals zero. Note this is not an issue when Sj contains a single heavy
hitter that is much heavier than the total `2 mass in the rest of the partition.
The second issue is that PartitionCountSketch is again used in the b-tree (see Section B.2
below), which we use in our final heavy hitters algorithm. Unfortunately there, we do not have
the guarantee that each partition contains one item much heavier than the combined mass of the
rest. One way around this is to simply not use the b-tree at all, but to just use the PartitionCountSketch itself. Doing so, though, would make our final query time blow up to O(−2 lgC n)
for a large constant C. This can be fixed, and one can achieve our same current query time, by
instead implementing the data structures Pj in Section 5 as themselves recursive instantiations of
the ExpanderSketch data structure! Then after a constant number of levels of recursion (even
one level down), one then implements the Pj using the PartitionCountSketch (see Remark 1).
All in all, [KNW10] is thus avoided. We do not delve further into the details since the bounds do
not improve, and we feel that a fully detailed exposition is not worth the effort.
We also record a lemma here which will be useful later.
Lemma 15. Consider an instance of partition heavy hitters with partition P = {S1 , . . . , SN } and
oracle O. Suppose A ⊂ [N ], and D is an (α1 , α2 , 0 )-partition point query structure for some
0 < α1 ≤ 1 ≤ α2 which succeeds on point querying every j ∈ A, where 0 = (α1 /3). Then if L ⊆ A
30

is defined to be the 2/002 indices of A with the largest point query results from D for 00 = 0 /α2 ,
then L contains all partition -heavy hitters contained in A.
Proof. Let ỹj be the result of a point query of j ∈ A using D. If j ∈ A is a partition -heavy
hitter then
ỹj ≥ α1 ky[1/2 ] k2 − (α1 /3)ky[1/02 ] k2 ≥ (2/3)α1 ky[1/2 ] k2 .
by Eq. (4). Meanwhile, if some j 0 is not even an 00 -partition heavy hitter, then
ỹj 0 < α2 00 ky[1/02 ] k2 + 0 ky[1/02 ] k2 ≤ (2/3)α1 ky[1/02 ] k2 .
Thus every set which is not even a partition 00 -heavy hitter has a point query value strictly less
than every partition -heavy hitter in A. Since there are at most 2/002 sets which are partition
00 -heavy hitters, correctness follows, since L by definition contains the 2/002 sets with largest point
query values.


B.2

b-tree

Here we describe the b-tree for partition heavy hitters, which is a slight modification of the Hierarchical CountSketch from [CH08] for non-partition strict turnstile heavy hitters. We assume
2 ≤ b ≤ N is an integer power of 2.
For what follows, we assume vector entries in both x ∈ Rn and y ∈ RN are 0-based indexed, e.g.
x = (x0 , . . . , xn−1 )T and y = (y0 , . . . , yN −1 )T . Conceptually we create virtual streams J0 , . . . , Jlgb N .
For the stream Jr we solve an instance of partition point query with br sets in the partition defined
as follows. At the level r = lgb N , the partition is Plgb N = P = {S0 , . . . , SN −1 }, with oracle
Olgb N = O. For 0 ≤ r < lgb N , the partitions are defined inductively: we imagine a complete b-ary
tree on {0, . . . , N − 1} where the jth leaf node denotes Sj , and for r < lgb N each internal node
represents a set equal to the union of the sets at its children. Said succinctly, for r < lgb N , the
oracle evaluation Or (i) equals O(i)/blgb N −r . Note that since b = 2` is a power of 2, Or can be
implemented in constant time by bitshifting right `(lgb N − r) positions (lgb N is a fixed value that
can be computed once and stored during initialization).
When an update (i, v) is seen in the actual stream, it is fed into a PartitionCountSketch
Pr at level r for each 0 ≤ r ≤ lgb N , with partition Pr and oracle Or . Each Pr is chosen to
be a (1/20, 3, /60)-partition point query structure, i.e. the error parameter is 0 = /60. Set
Q = 2b(lgb N )/002 , which is an upper bound on the total number of point queries we make to all
Pr combined. We set the failure probability for each Pr to be η = δ/Q = Θ(2 δ/(b lgb N )).
To answer a heavy hitters query, we walk down the tree as follows (our goal is to have, at all
times 0 ≤ r ≤ lgb N , a list Lr of size O(1/2 ) which contains all the -heavy hitter partitions at
level r). First we set L0 = {0}. Then for r = 1 to lgb N , we point query every child of an element
of Lr−1 . We then set Lr to be the nodes at level r whose point query result were amongst the 2/002
highest for 00 = 0 /3 = /180. We finally return L = Llgb N as our set of partition heavy hitters.
Theorem 7. Suppose 1/N c ≤  < 1/2 and δ ∈ (0, 1/2). Then the b-tree as described above produces
a correct output L for partition -heavy hitters with probability at least 1 − δ for any 2 ≤ b ≤ N .
Furthermore, for any constant c0 ≥ 1 and any constant 0 < γ < γ0 where γ0 depends on c, c0 ,
0
for any failure probability 1/N c ≤ δ < 1/2, there is a choice of b so that the b-tree uses space
O(−2 lg N ), has update time O(lg N ), and query time O((−2 lg N )((lg N )/(δ))γ ). The constants
in the big-Oh depend on 1/γ.
31

Proof. We have |L| ≤ 2/002 = O(1/2 ) by definition of the algorithm. Note that we make at most
Q point queries since each Lr has size at most 2/002 , and each element of Lr has at most b children.
Also, there are lgb N values of r for which we query children (since the leaves have no children).
Thus the total number of queries is at most 2b(lgb N )/002 = Q. Now we show that, conditioned
on the event that all Q point queries succeed, correctness holds by induction on r. This would
complete the correctness analysis, since the probability that any point query fails at all is at most
Qη = δ, by a union bound. For the induction, our inductive hypothesis is that Lr contains every
-partition heavy hitter at level r. This is true for r = 0 since L0 = {0}, and the root of the
tree contains only a single partition. Now, assume Lr−1 satisfies the inductive hypothesis. Since
any ancestor of a partition -heavy hitter is itself an -partition heavy hitter, it follows that every
partition heavy hitter at level r is the child of some set in Lr−1 . Thus if we let A be the collection
of children of sets in Lr−1 , Lemma 15 implies that Lr also contains all the partition -heavy hitters
As for space and time bounds, we choose b to be ((lg N )/(δ))γ , rounded up to the nearest
integer power of 2. This is at most N for γ sufficiently small since , δ > 1/ poly(N ), and at least 2
for N larger than some constant depending on γ (which we can assume without loss of generality, by
padding the partition with empty sets). By Lemma 14 and choice of b, the space is asymptotically
1 lg N
1 lg N
·
lg(1/η) ' 2 ·
· (lg(1/δ) + lg b + lg lg N + lg(1/)) ' −2 lg N.
2 lg b

lg b
The update time is asymptotically
lg N
lg N
lg(1/η) '
· (lg(1/δ) + lg b + lg lg N + lg(1/)) ' lg N.
lg b
lg b
The query time is asymptotically
b lg N
lg N γ
b lg N
·
lg(1/η) ' 2 ·
· (lg(1/δ) + lg b + lg lg N + lg(1/)) ' −2 lg N · (
) .
2

lg b

lg b
δ

Corollary 1. For any constant 0 < γ < 1/2, (non-partition) heavy hitters with error parameter
 ∈ (0, 1/2) and failure probability 1/ poly(n) < δ < 1/2 can be solved with space O(−2 lg n), update
time O(lg n), query time O(−2 lg n((lg n)/(δ))γ ), and failure probability δ.
√
Proof. We can assume  > 1/ n without loss of generality, since otherwise the trivial solution of
keeping x in memory explicitly suffices. Otherwise, the claim follows from Theorem 7 by considering
the partition P = {{1}, . . . , {n}} with N = n and O(i) = i.


C

Connection between heavy hitters and list-recoverable codes

Our approach is somewhat related to list-recoverable codes, which were first used in group testing
in [Che09, INR10] and in compressed sensing in [NPR12] (and also in subsequent compressing
works, e.g. [GNP+ 13, GLPS14]). We say a code C ⊂ [q]m is (, `, L)-list recoverable if for any
sequence of lists L1 , . . . , Lm ⊂ [q] with |Lj | ≤ ` for all j ∈ [m], there are at most L codewords in
C whose jth symbol appears in at least a (1 − )-fraction of the lists Lj . A decoding algorithm is
then given these m lists and must find these at most L codewords. To see the connection to our
32

current heavy hitters problem, it is known (via the probabilistic method) that such codes exist with
|C| ≥ n, q = poly(lg n), m = O(lg n/ lg lg n), and `, L = O(lg n), where  can be made an arbitrarily
small constant (see for example the first row of [HW15, Figure 1]). Suppose we had such a code C
with encoding function enc : [n] → C. Then our heavy hitters algorithm could follow the scheme
of Figure 2. That is, we would instantiate m b-trees P1 , . . . , Pm for partition heavy hitters with
Oj (i) = enc(i)j . By picking constants appropriately in the parameter settings, one can ensure that
whp at most an -fraction of the Pj fail. Thus, whp every heavy hitter appears in a (1 − )-fraction
of the lists Lj , and we would then perform list-recovery decoding to find all the heavy hitters. The
trouble with this approach is that there currently are no explicit codes achieving these parameter
settings, let alone with linear time encoding and fast decoding. Indeed, this is the source of slight
suboptimality in the `1 /`1 “for all” compressed sensing scheme of [GLPS14].
The key to our progress is to sidestep the lack of explicit optimal list-recoverable codes with
linear-time encoding and fast decoding by realizing that list-recoverability is stronger than what
we actually need. First of all, list-recovery says that for all choices of lists L1 , . . . , Lm , some
condition holds. In our case the lists are random (symbols in it contain concatenations with random
hash evaluations hj ), since our heavy hitters algorithm is allowed to be a randomized algorithm.
Secondly, our decoding algorithm does not need to handle arbitrary lists, but rather lists in which
each symbol has a distinct name (recall from Section 4 that the “name” of z(i)j is hj (i)). This is
because, in our problem, with good probability any list Lj has the property that for each heavy
hitter i with z(i)j ∈ Lj , z(i)j will be reported by a partition point query data structure to have
much heavier weight than any other z ∈ Lj with the same name. Thus our post-processing step
using Qj allows us to only have to perform decoding from lists with a certain structure which does
not exist in the general list-recovery problem, namely that no two symbols in Lj agree on the first
few (namely O(lg lg n)) bits.

D

A simpler query algorithm for strict turnstile `1 heavy hitters

In this section, we describe our simpler algorithm for strict turnstile `1 heavy hitters. The high-level
idea is the following: Recall the general turnstile algorithm from Section 5. There we end up having
to find -spectral clusters. This subproblem arose because several data structures Pjk may err and
thereby insert spurious edges into the graph G. Now in the strict turnstile case, we can roughly
ensure that we can recognize when a Pjk errs. By simply deleting all edges returned by such a Pjk ,
the remaining graph G has each heavy hitter corresponding to a number of connected components
that are completely disjoint from the subgraphs corresponding to other heavy hitters and noise
from light elements. Furthermore, for each heavy hitter, one of these connected components has at
least 90% of the corresponding codeword enc(i). We can thus replace the cluster finding algorithm
by a simple connected components algorithm and thereby obtain a much simpler algorithm. This
section gives all the details of the above.
Our solution needs the more standard definition of heavy hitters: On a query, we must return
a set L containing all indices i where xi ≥ kxk1 and no indices j such that xj < (/2)kxk1 .
The first thing our solution in the strict turnstile case needs, is the fact that one can maintain
kxk1 exactly in O(1) space and with O(1) update time. This follows trivially by maintaining a
counter C that is initialized as 0, and upon every update (i, ∆), we update C ← C + ∆. Since we
are in the strict turnstile model, we will always have C = kxk1 .
The second thing is a variant of partition point queries that have been adapted to the `1 strict
33

turnstile case.
Definition 3. In the `1 strict turnstile partition point query problem there is some error parameter
 ∈ (0, 1/2). There is also some partition P = {S1 , . . . , SN } of [n], and it is presented in the form
of an oracle O : [n] → [N ] such that for any i ∈ [n], O(i) gives the index j ∈ [N ] such that i ∈ Sj .
Define a vector y ∈ RN such that for each j ∈ [N ],
X
yj =
xi .
i∈Sj

On a query for index j ∈ [N ], we must output a value ỹj such that yj ≤ ỹj ≤ yj + ky[1/] k1 .
Lemma 16. For any failure probability 1/ poly(n) < δ < 1/2, there is a solution to the strict
turnstile partition point query problem with space O(−1 lg(1/δ)) words, update time O(lg(1/δ)) and
query time O(lg(1/δ)). Furthermore, the solution guarantees that even when it errs, the returned
estimate ỹj is at least yj .
Proof. Simply implement the CountMin sketch of [CM05] on the vector y. Thus on an update
(i, ∆), feed the update (O(i), ∆) to the CountMin sketch and on a query for yj , return the estimate
for j in the CountMin sketch.

Using Lemma 16, we can also modify the b-tree from Section B.2 to obtain a no false negatives
guarantee. More specifically, define a new version of heavy hitters called threshold heavy hitters
with no false negatives. We say that an algorithm solves threshold `1 heavy hitters with no false
negatives and failure probability δ, if it supports taking a query value φ > 0. If the query value φ
is less than kx[1/] k1 , then the algorithm may return an arbitrary answer. If φ ≥ kx[1/] k1 , then
with probability at least 1 − δ, it must return a set L that has size O(φ−1 kxk1 ) and contains all
indices i with xi ≥ φ and no indices j with xj ≤ φ − (/2)kx[1/] k1 . With the remaining probability
at most δ, it returns the empty set.
Such algorithms can thus recognize when they err (indicated by an empty return set) on queries
for sufficiently large φ. The following lemma essentially follows from the b-tree solution in Theorem 7
combined with Lemma 16:
Lemma 17. Suppose 1/nc ≤ δ < 1/2 where c > 0. Let γ be any constant satisfying 0 < γ < γ0
for some fixed constant γ0 . Then there is a modification of the b-tree described in Section B.2
and a choice of b, which in the strict turnstile `1 setting solves threshold heavy hitters with no
false negatives and failure probability at most δ. Furthermore, the b-tree uses space O(−1 lg n),
has update time O(lg n), and query time O((−1 lg n)((lg n)/(δ))γ ). The constants in the big-Oh
depend on 1/γ.
Proof. Take the b-tree solution as described in Section B.2. Replace each PartitionCountSketch for Pr with the algorithm from Lemma 16 with approximation factor 0 = /2. This means
that at each level of the b-tree, we can do a point query for the total mass of a subtree. By
Lemma 16 these estimates are never underestimates, even when the algorithm errs. And when the
algorithm does not err, the returned estimate is at most 0 ky[1/] k1 ≤ 0 kx[1/] k1 = (/2)kx[1/] k1
too high. We set the failure probability for each data structure from Lemma 16 to O(δ/(b lgb n)).
On a query for all indices i with xi ≥ φ, we traverse the tree roughly as described in Section B.2.
The main difference is that when choosing the set Lr after having point queried every child of nodes
34

in Lr−1 , we choose Lr to be all nodes where the point query returned an estimate of at least φ. In
case |Lr | > 3−1 at any level, we abort and return L = ∅.
Now observe that if no query to the children of nodes in Lr−1 err, then for φ ≥ kx[1/] k1 , there
can be no more than 3−1 nodes for which the estimate is at least φ. This follows since if the
point queries did not err, then the true mass of those subtrees must be at least φ − (/2)kx[1/] k1 ≥
(/2)kx[1/] k1 . There can be at most 3−1 such subtrees. Thus conditioned on not making an error
in any point query on the first r − 1 levels of the b-tree, we will visit at most 3−1 nodes on level
r. It follows that we only abort and return an empty list in case some query errs. And if no query
errs, we will ask only O(−1 b lgb n) queries. Since we set the failure probability in each algorithm
from Lemma 16 to O(δ/(b lgb n)), the lemma follows.

We only need one more ingredient in our solution, namely a property of edge-expander graphs.
We have not been able to find a reference for this result, but suspect it is known.
Lemma 18. If G = (V, E) is a d-regular δ-edge-expander, then for any constant 0 < µ < 1, if we
remove any set of at most (δµ/2)|V | vertices in G and their incident edges, then there remains a
connected component of size at least (1 − µ)|V |.
Proof. Let S ⊆ V be any set of at most (δµ/2)|V | vertices in G. The number of edges with
an endpoint in S is at most d|S| since G is d-regular. Let C1 , . . . , Cm ⊆ V be the connected
components in GV \S , where GV \S is the graph obtained from G by removing the vertices S and
all edges incident to S. Assume for contradiction that |Ci | < (1 − µ)|V | for all Ci . For each Ci , let
Ci∗ denote the smaller of Ci and V \ Ci . It follows from |Ci | being less than (1 − µ)|V | that


µ
|V |
∗
· |Ci | < |Ci | ≤ min
, |Ci | .
1−µ
2
Since G is a δ-edge-expander and |Ci∗ | ≤ |V |/2, there are at least


µ
∗
δd|Ci | ≥ δ min 1,
· d|Ci | ≥ δ min{1, µ}d|Ci | = δµd|Ci |
1−µ
edges across the cut (Ci∗ , V \Ci∗ ) in G. This cut is just (Ci , V \Ci ). But Ci is a connected component
in GV \S and thus all edges leaving P
Ci in G must go to a node in S. Therefore, the number of edges
incident to a node in S is at least i δµd|Ci | = δµd(|V | − |S|). But |S| ≤ (δµ/2)|V | and hence
|V | − |S| ≥ (1 − δµ/2)|V | ≥

1 − δµ/2
· |S|.
δµ/2

We thus have at least

1 − δµ/2
· d|S| = 2(1 − δµ/2)d|S| > d|S|
δµ/2
edges incident to S. But this contradicts that there are only d|S| edges incident to S.
δµ



The following result due to Alon et al. [ASS08] shows that there exists efficient explicit edgeexpanders:
Theorem 8 (Alon et al. [ASS08]). There exists a constant δ > 0, such that for any positive integer
n, there exists a 12-regular δ-edge-expander G = (V, E) with n/2 ≤ |V | ≤ n. Furthermore, G is
constructable in time O(poly(n)).
We have set the stage for the description of our simpler `1 strict turnstile solution. Our new
algorithm is described in the following:
35

Strict Turnstile Algorithm. If  = o(1/ lg n), we re-execute the reduction in Section A, modified to the `1 setting. More specifically, we hash to z = Θ(1/( lg(1/n))) subproblems. Each
subproblem is solved with a threshold heavy hitters structure with  = O(1/ lg n) and failure probability 1/ poly(n). Thus on a query to report all heavy hitters, we use the fact that we know kxk1
exactly in order to query each threshold heavy hitters structure with φ = kxk1 . By an analysis
similar to Section A, with probability at least 1 − 1/ poly(n), this will ensure φ ≥ ky[1/] k1 where y
denotes the vector corresponding to any of these subproblem. If  is Ω(1/ lg n), we can also reduce
to threshold heavy hitters with the same  and failure probability 1/ poly(n) simply by maintaining
one structure and querying it with φ = kxk1 . Thus we have now reduced the problem to solving
threshold heavy hitters with  = Ω(1/ lg n) in the `1 strict turnstile case, where we are guaranteed
that the query value φ is at least kx[1/] k1 .
We now focus on solving threshold heavy hitters with  = Ω(1/ lg n) and failure probability
1/ poly(n) for a query value φ ≥ kx[1/] k1 . Following Section 5, we construct the 12-regular δedge-expander from Theorem 8 with m = Θ(lg n/ lg lg n) vertices. Call it F . This takes poly lg n
time. We store it in adjacency list representation, consuming O(lg n/ lg lg n) words of memory.
We then pick hash functions h1 , . . . , hm : [n] → [poly(lg n)] independently from a pairwise independent family and instantiate data structures D1 , . . . , Dm . Each Di is the threshold heavy hitters
with no false negatives from Lemma 17. The failure probability of each structure is 1/ poly(lg n)
and the approximation factor is .
On an update (i, ∆), we compute in O(lg n) time an encoding enc(i) of i into a string of length
T = O(lg n) bits by an error-correcting code with constant rate that can correct an Ω(1)-fraction
of errors (as in Section 5). We again partition enc(i) into m contiguous bitstrings each of length
t = T /m = Θ(lg lg n). We let enc(i)j denote the jth bitstring. For each j = 1, . . . , m, we feed the
update (hj (i) ◦ enc(i)j ◦ hΓ(j)1 ◦ · · · ◦ hΓ(j)12 , ∆) to Dj (similarly to Section 5).
On a query with threshold φ > 0, we query each Dj with φ. Let Lj be the output of Dj . If Lj is
non-empty, we go through all returned values and check if there are two with the same name (same
hj (i)). If so, we overwrite Lj ← ∅ and say that Dj failed. Now in all remaining Lj , all names are
unique. From these lists, we construct the same layered graph G as described in Section 4. Recall
that we only add edges if both endpoints suggest it. Now the crucial observation which makes the
`1 strict turnstile easier to solve, is that the Dj ’s guarantee no false negatives. Thus if some Dj did
not err and did not fail, then no node in G corresponding to a name hj (i) returned by Dj , can be
connected by an edge to a node hj 0 (i0 ) returned by a Dj 0 for any i0 6= i. To see this, notice that the
actual index hj 0 (i) ◦ enc(i)j 0 ◦ hΓ(j 0 )1 ◦ · · · ◦ hΓ(j 0 )12 corresponding to hj 0 (i) must not be in Lj 0 for
this to happen. But we are guaranteed no false negatives, so if Dj 0 returns anything, it must have
hj 0 (i) ◦ enc(i)j 0 ◦ hΓ(j 0 )1 ◦ · · · ◦ hΓ(j 0 )12 in its output. To summarize, for every index i with xi > φ, all
Dj that did not err and did not fail produce nodes corresponding to names hj (i), and these nodes
are not connected to nodes of name hj 0 (i0 ) for an i0 6= i. Furthermore, for two Dj and Dj 0 that both
did not err and fail, the edges between the returned nodes are in the graph G. But the hash function
hj have collisions with probability 1/ poly(lg n) and the data structures Dj have failure probability
1/ poly(lg n). Thus with probability 1 − 1/ poly(n), there are at most a γ-fraction of the Dj that
either fail or err. Here we can choose γ as an arbitrarily small constant by increasing the polylogs
in 1/ poly(lg n) failure probability. By Lemma 18, we get that with probability 1 − 1/ poly(n), each
index i with xi ≥ φ has a connected component in G of size at least 0.9m. We now finish off by
computing all connected components in G. For each component of size at least 0.9m, we stitch
together the pieces enc(i)j to obtain 90% of the codeword enc(i). We decode i in linear time in
36

its bit length, which is O(lg n) time. Finally, we verify all these returned indices by doing a point
query against a separate CountMin structure with failure probability 1/ poly(n) and the same .
This also costs O(lg n) time per index.
Since we are guaranteed that each returned list Lj has size at most φ−1 kxk1 , the query time
is O(φ−1 kxk1 lg n) for decoding codewords and for verifying the recovered indices (the norm of the
vector represented by each Dj is precisely the same as the norm of x). Now φ is kxk1 , so the
time spent is O(−1 lg n). For querying the structures Dj , Lemma 17 gives us a query time of
O((−1 lg lg n)((lg lg n poly(lg n))/))γ ) per Dj . Since  = Ω(1/ lg n), we can choose γ sufficiently
0
small to obtain a query time of −1 lgγ n for any constant γ 0 > 0. Since we have m = O(lg n/ lg lg n),
the total time for querying all Dj is O(−1 lg1+γ n) for any constant γ > 0.
For the update time, observe that each Dj has update time O(lg lg n) and there are O(lg n/ lg lg n)
such structures to be updated, for a total of O(lg n) time. Computing enc(i) also takes O(lg n)
time. The space is optimal O(−1 lg n) words.
Theorem 9. For any constant 0 < γ < 1/2, heavy hitters with error parameter  ∈ (0, 1/2) and
failure probability 1/ poly(n) < δ < 1/2 can be solved in the strict `1 turnstile setting with optimal
O(−1 lg n) space, update time O(lg n), query time O(−1 lg1+γ n), and failure probability δ.

E

Expected Time for Strict Turnstile `1

If we are satisfied with expected query time, then there is an even simpler and very practical
algorithm for the strict turnstile `1 case. The algorithm is based on the b-tree, but with b = 2, i.e.
a binary tree. As in Section D, we solve the more standard variant of heavy hitters in which we must
return a set L containing all indices i where xi ≥ kxk1 and no indices j such that xj < (/2)kxk1 .
For what follows, we assume vector entries in x ∈ Rn are 0-based indexed, e.g. x = (x0 , . . . , xn−1 )T .
Conceptually we create virtual streams J0 , . . . , Jlg2 n . For the stream Jr we solve an instance of
partition point query with 2r sets in the partition defined as follows. At the level r = lg2 n, the
partition is Plg2 n = P = {S0 , . . . , Sn−1 }, with oracle Olg2 n = O. For 0 ≤ r < lg2 n, the partitions
are defined inductively: we imagine a complete binary tree on {0, . . . , n − 1} where the jth leaf
node denotes Sj , and for r < lg2 n each internal node represents a set equal to the union of the
sets at its children. Said succinctly, for r < lg2 n, the oracle evaluation Or (i) equals O(i)/2lg2 n−r .
Note that Or can be implemented in constant time by bitshifting right `(lg2 n − r) positions (lg2 n
is a fixed value that can be computed once and stored during initialization).
When an update (i, v) is seen in the actual stream, it is fed into a PartitionCountSketch
Pr at level r for each 0 ≤ r ≤ lg2 n, with partition Pr and oracle Or . Each Pr is chosen to be
the partition point query structure from Lemma 16 with error parameter 0 = /2 and failure
probability δ = 1/4. This has each Pr using O(−1 ) words of space, supporting updates and queries
in O(1) time. We also maintain one CountMin sketch on x with error parameter 0 = /2 and
failure probability 1/ poly(n).
The space is O(−1 lg n) and the update time is O(lg n).
To answer a heavy hitters query, we walk down the tree as follows (our goal is to have, at all
times 0 ≤ r ≤ lg2 n, a list Lr of size O(1/−1 ) which contains all the -heavy hitter partitions at
level r). First we set L0 = {0}. Then for r = 1 to lg2 n, we point query every child of an element
of Lr−1 . We then set Lr to be the nodes at level r whose point query result was at least kxk1 .
Recall from Section D that in the strict turnstile `1 setting, we can maintain kxk1 exactly. Once

37

we have computed Llg2 n , we point query each element in the list against the CountMin sketch
and filter out those indices where the returned value is less than kxk1 .
The key insight is that the data structure from Lemma 16 never returns an underestimate.
Thus the list Llg2 n will always contain all indices i with xi ≥ kxk1 . The only issue is that we may
consider more candidate heavy hitters than really exist, which might increase the query time tq .
We show that in fact tq remains small in expectation.
Let the 2n − 1 nodes in the conceptual binary tree be called u1 , . . . , u2n−1 . During query, we
traverse this tree starting at the root. While visiting a node u at level r, we query it in Pr and only
recurse to its children if the subtree corresponding to u is declared to have mass at least kxk1 at
level r. For j ∈ [2n − 1] let Yj be an indicator randomPvariable for whether Pr declares uj as having
mass at least kxk1 . Note the runtime of a query is j Yj . Thus the expected runtime satisfies
tq = E

2n−1
X

Yj =

j=1

X

E Yj .

j

Now, what is E Yj ? Call a node uj which actually corresponds to a subtree of mass at least
(/2)kxk1 heavy. Then for heavy uj , we use the simple upper bound E[Yj ] ≤ 1; there are at
most 2−1 lg n such heavy j summed over the entire tree. Otherwise, if d is the distance to the
lowest ancestor v of uj which is heavy, then for Yj to be 1, it must be that every point query to an
ancestor of uj below v must fail. This happens with probability 1/4d−1 since the data structures are
independent across the levels of the tree. However, if we fix d and ask how many nodes in the entire
tree have shortest distance to a heavy ancestor equal to d, then that is at most (2−1 lg n) · 2d−1 .
Therefore the expected query time tq for traversing the tree is:
X
j

−1

E Yj ≤ (

lg n) ·

∞  r
X
2
r=0

4

= O(−1 lg n).

Finally, we also have |Llg2 n | queries to a CountMin sketch with failure probability 1/ poly(n).
These queries cost O(lg n) time each. Thus we need to bound O(lg n) · E |Llg2 n |. By an argument
similar to the above, consider a leaf uj corresponding to an index j with xj ≤ (/2)kxk1 . Let d
denote the distance from uj to its nearest heavy ancestor. For uj to be in Llg2 n , every point query
on this path must fail. This happens with probability 1/4d−1 . Now how many leaves can have
shortest distance to a heavy ancestor equal to d? Since we are only considering leaves, ancestors of
distance d are at the exact same level for all leaves. But a level has at most 2−1 heavy nodes, and
thus there are at most (2−1 ) · 2d−1 leaves with distance exactly d to their nearest heavy ancestor.
By an argument similar to the above, we get that E |Llg2 n | = O(−1 ). We conclude:
Theorem 10. For any constant 0 < γ < 1/2, heavy hitters with error parameter  ∈ (0, 1/2) and
failure probability 1/ poly(n) < δ < 1/2 can be solved in the strict `1 turnstile setting with optimal O(−1 lg n) space, update time O(lg n), expected query time O(−1 lg n), and failure probability
1/ poly(n).

38

