Optimal streaming algorithm for detecting ℓ2 heavy hitters in

random order streams

Santhoshini Velusamy∗ Huacheng Yu†

Abstract
arXiv:2509.07286v1 [[Link]] 8 Sep 2025

Given a stream x1 , x2 , . . . , xn of items from a Universe U of size poly(n), and a parameter

√ ϵ > 0,
qiP∈ U is said to be an ℓ2 heavy hitter if its frequency fi in the stream is at least ϵF2 , where
an item
2
F2 = i∈U fi . Efficiently detecting such heavy hitters is a fundamental problem in data streams
and has several applications in both theory and in practice. The classical CountSketch algorithm due
to Charikar,
 Chen, and Farach-Colton [2004], was the first algorithm to detect ℓ2 heavy hitters using
log2 n
O ϵ
bits of space, and their algorithm is optimal for streams with deletions. A follow-up paper
due to Braverman, Chestnut, Ivkin, and Woodruff [2016], gave the CountSieve algorithm
 for insertion-

log(1/ϵ)
only streams, with an improved space bound. Their algorithm requires only O ϵ
log n log log n
space. Note that any algorithm requires at least O 1ϵ log n space to output O(1/ϵ) heavy hitters in

the worst case. So for constant ϵ, the space usage of the CountSieve algorithm is asymptotically only a
log log n factor worse than the optimum bound. A later work due to Braverman, Chestnut, Ivkin, Nelson,
Wang, and Woodruff [2017] gave the BPTree algorithm which gets rid  of this additional
 log log n factor
log(1/ϵ)
and detects ℓ2 heavy hitters in insertion-only streams using only O ϵ
log n space. While their
algorithm achieves optimal space bound for constant ϵ, their bound could be sub-optimal for ϵ = o(1).
In this work, we show that for random order streams, where the stream elements can be adversarial but

their order of arrival is uniformly random, it is possible to achieve the optimal space bound of O 1ϵ log n
 
1
for every ϵ = Ω 2√log n
. We also show that for partially random order streams where only the heavy
hitters are required to be uniformly distributed in the stream, it is possible to achieve the same space
bound, but with an additional assumption that the algorithm is given a constant approximation to F2
in advance.
n
We mainly exploit the fact that if the stream is divided into windows of length roughly √ϵF , with
2
high probability, for every heavy hitter, every log n consecutive windows has an occurrence of that heavy
hitter, and develop a hierarchical sample-and-check framework that efficiently detects them. The window
size is crucial to the algorithm. For random order streams, we show that it is possible to approximately
estimate the window size after the algorithm sees a small constant fraction of the stream.

∗ Toyota Technological Institute, Chicago, Illinois, USA. Email: santhoshini@[Link].

† Princeton University, Princeton, New Jersey, USA. Email: yuhch123@[Link].

1
1 Introduction
“Heavy hitters” is a term often used to describe elements that occur most commonly in a data stream. The
problem of detecting heavy hitters has several applications, both in theory and practice. For instance, heavy
hitters algorithms have been used as subroutines to solve many important streaming problems including norm
estimation [1], entropy estimation [2, 3], and weighted sampling [4]. In addition, they have also influenced
recent efforts to speed up LLM algorithms. In particular, by detecting and removing heavy hitters, a recent
paper obtained a significant speed up in the matrix multiplication component of the “attention approximation
problem” in LLMs [5].
The earliest known work on heavy hitters began in the 1980’s when Boyer and Moore discovered an
algorithm to output the majority element in the stream using just two machine words [6]. Since then, vast
generalizations of this problem have been studied in the literature (see, for example, [7–14] and the references
therein). Formally, given a stream x1 , . . . , xn of items from a universe U of size poly n, the heavy hitters
problem asks to recover, with high probability, every element i ∈ U such that fi ≥ γ, where fi denotes the
frequency with which the element occurs in the stream. The algorithm is also often required to not output
any element whose frequency is less than τ , where the thresholds γ and τ are usually defined in terms of
different norms of the stream.
One popular notion is the ℓ1 guarantee where given a parameter ϵ ∈ (0, 1], the algorithm has to recover
every element of frequency at least ϵn and not output any element of frequency less than δn where δ is
typically assumed to be ϵ/c, for some constant c. The first algorithm for this problem was given by Misra
and Gries in 1982 [15]. Their algorithm is deterministic and uses only O(log n/ϵ) bits of space, which is
optimal since in the worst case, the algorithm has to output Θ(1/ϵ) elements and it requires Θ(log n) space
to represent each of them. Their algorithm also works only in the insertion-only model, also known as the
cash-register model, where elements can only be inserted into the stream. For general turnstile streams where
elements can be added to or deleted from the stream, Cormode and Muthukrishnan gave the CountMinSketch
algorithm which is a randomized sketching algorithm1 that uses O(log2 n/ϵ) bits of space to achieve a constant
success probability [16]. Notice the log n gap in the space required by the Misra-Gries algorithm and the
CountMinSketch algorithm. This gap is inherent as the latter algorithm is known to be optimal for turnstile
streams [17].
Another well-studied guarantee is the ℓ2 guarantee, where given a parameter ϵ ∈ (0, 1], the algorithm has
to recover every element i ∈ U such that fi2 ≥ ϵ∥f ∥22 and not output any element i ∈ U such that fi2 < δ∥f ∥22 ,
where ∥f ∥2 denotes the norm of the frequency vector of the elements in the stream. Note that this is a
stronger guarantee compared to the ℓ1 guarantee. For example, consider a stream where ∥f ∥22 = Θ(n). For
a constant ϵ, the ℓ1 guarantee asks only to output elements that occupy a constant √ fraction of positions in
the stream, while the ℓ2 guarantee asks for any element that has frequency Ω( n), which occupies only a
negligible portion of the stream. The CountSketch algorithm due to Charikar, Chen, and Farach-Colton can
recover heavy hitters under the l2 guarantee, with at least a constant probability, using O(log2 n/ϵ) bits of
space [18]. A follow-up work due to Jowhari, Sağlam, and Tardos shows that CountSketch can be extended
to output heavy hitters under the ℓp guarantee for every p ≤ 2 using space at most O(log2 n/ϵ) and that
the algorithm is optimal for every p in this range, in the turnstile setting [17]. An earlier work due to Do
ba, Indyk, Price, and Woodruff [19] proved this result for p = 2. While CountSketch is optimal for turnstile
streams, it is natural to ask if there is a more space-efficient algorithm in the insertion-only model, similar
to the ℓ1 case. This question was first answered positively by Braverman, Chestnut,

Ivkin, and Woodruff
who gave the CountSieve algorithm which requires only O 1ϵ log 1ϵ log n log log n space to output heavy

hitters under the ℓ2 guarantee, with at least a constant success probability [20]. The same authors,
along

with Nelson and Wang, later gave an improved algorithm called BPTree which uses only O 1ϵ log 1ϵ log n
space to achieve a constant success probability [21]. The primary goal of this paper is to further reduce
their space bound and obtain an optimal O(log n/ϵ) space algorithm and we achieve this for random order
streams. In addition, we also show that for partially random order streams when the heavy hitters are
uniformly distributed across the stream (while the non-heavy elements could be adversarially positioned), it
is possible to recover the l2 heavy hitters, assuming we know the l2 norm of the frequency vector in advance.
1 Sketching algorithms are a special class of streaming algorithms where the algorithm’s output is determined by a small

sketch it produces of the input stream, and the sketch itself has the property that the sketch of the concatenation of two streams
can be computed from the sketches of the two component streams.

2
1.1 Our results
We now formally state our main results. We first begin with some definitions.
Definition 1.1 (ℓ2 norm). The ℓ2 norm of a stream S, denoted by ∥S∥2 , is defined to be the ℓ2 norm of the
frequency vector f = (fi )i∈U where fi is the number of occurrences of element i in the stream.
Definition 1.2 (ℓ2 ϵ-heavy hitter). For 0 < ϵ ≤ 1, we say that x is an ϵ-heavy hitter if fx2 ≥ ϵ∥S∥2 .
Random order streams are well-studied in the streaming literature, and understanding the space com-
plexity in this model is an interesting problem of its own [22–25]. The difference between random order
streams and adversarial streams is that in random order streams, the elements in the stream are presented
in a uniformly random order to the streaming algorithm, and the algorithm has to do well on most orders.
Below, we state our result for detecting ℓ2 heavy hitters in random order streams.
 
1
Theorem 1.3 (Random order streams). ∃n0 , c0 ∈ N such that for every n ≥ n0 and ϵ ≥ c0 2√log n , there is
a single-pass streaming algorithm that with probability at least 9/10, finds every ℓ2 ϵ-heavy hitter and reports
no element that is not an ℓ2 ϵ/256-heavy hitter, in random order streams of length n, using O(log n/ϵ) bits
of space.
We also extend our results to partially random order streams, where the positions of the heavy hitters
are random, while the non-heavy elements can be adversarially positioned (see Definition 3.3 for a formal
definition). However, in this case, we need an additional assumption that the ℓ2 norm of the stream is known
in advance to the algorithm.
 
1
Theorem 1.4 (Partially random order streams). ∃n0 , c0 ∈ N such that for every n ≥ n0 and ϵ ≥ c0 2√log n ,
there is a single-pass streaming algorithm that with probability at least 9/10, finds every ℓ2 ϵ-heavy hitter and
reports no element that is not an ℓ2 ϵ/256-heavy hitter, in partially random order streams of length n, using
O(log n/ϵ) bits of space, assuming that the ℓ2 norm of the stream is known in advance to the algorithm.
The above result should be viewed as a first step towards generalizing our result beyond random order
streams. Assuming that the heavy hitters are uniformly distributed, while the non-heavy elements are placed
by an adversary, is a natural starting point. For example, the heavy hitters maybe generated by a stochastic
process, while the non-heavy elements could be adversarial noise. Such partially random ordered streams
have been explored in the literature (see, for example, [26]) and serve as an important bridge between the
random order and the adversarial streaming model. Our other assumption that the streaming algorithm
needs to know the ℓ2 norm of the stream in advance is not as natural as our first assumption, and we state
it this way purely for technical reasons. While one could imagine using an ℓ2 norm tracker algorithm like in
the BPTree algorithm to get rid of this assumption, unfortunately if the stream order is not fully random,
this could incur an additional factor of log(1/ϵ) in space, and hence we would not gain any advantage in
space compared to the BPTree algorithm. Therefore, we leave it as an interesting open problem whether
one could prove Theorem 1.4 without the assumption about the ℓ2 norm of the stream, or if there is a lower
bound in this case. We prove Theorems 1.3 and 1.4 at the end of Section 6.
In the following section, we present an overview of our techniques.

2 Technical overview
The previous ℓ2 heavy hitter algorithms for insertion-only streams (CountSieve, BPTree) first randomly hash
the elements into O(1/ϵ) buckets. For each ϵ-heavy hitter x∗ , there is a constant probability that all other
elements hashed to the same bucket as x∗ have second moment at least a constant smaller than fx2∗ . Such
an element x∗ is referred to as a super heavy hitter in the bucket. The algorithms then try to recover a super
heavy hitter from each bucket using small space, which will succeed with constant probability.
Since there can be as many as O(1/ϵ) heavy hitters, in order to recover all of them, the algorithms have
to repeat the process independently for O(log(1/ϵ)) times. More specifically, this is due to the following two
technical reasons:
• we must ensure that every ϵ-heavy hitter is super heavy in its bucket (at least once);

3
 • then we must ensure that it is recovered (at least once) with probability at least 1 − O(ϵ),
so that we can union bound over all O(1/ϵ) heavy hitters.
BPTree uses a subroutine with O(log n) bits of space to recover a super heavy hitter (with constant
probability). The subroutine is applied on all O(1/ϵ) buckets each time, and is repeated for O(log(1/ϵ))
times. Hence, it has space of O(ϵ−1 log(1/ϵ) log n) bits. Thus, in order to remove the extra O(log(1/ϵ))
factor, we must resolve the above two technical issues that forced us to repeat the process.
In this paper, we first focus on the second issue. That is, we first assume that an ϵ-heavy hitter x∗ is
already super heavy “in its bucket”, and we aim to recover it with high probability, under the assumption
√
that x∗ is roughly evenly distributed and with free randomness. It turns out that as long as ϵ > 2−Ω( log n) ,
our solution for high-probability super heavy hitter generalizes to ϵ-heavy hitter in a natural but different
way that does not need to do hashing on top of it. Hence, for our algorithm, the first issue no longer exists.
We note that there may be simpler solutions for random-order streams, the emphasis of this work is to design
the more general algorithm that works even only assuming the occurrences of heavy hitters are random.

2.1 Warmup
To motivate our new algorithm for super heavy hitter, let us first consider a special case of the stream√ as
a warmup. Consider a stream of length n consisting of a super heavy hitter x∗ with frequency C n for
some large
√ constant C, and other elements with frequency 1. Dividing the stream into windows of length
W := n/C, let us assume x∗ has one occurrence in every window. x∗ is super heavy in the stream, and
we want to find x∗ with high probability using O(log n) bits of space.
The main framework to find x∗ is sample-and-check. Since x∗ is the only element that appears at least
twice, as long as we find any duplicated element, the algorithm can declare√it to be the heavy hitter. The
algorithm processes the stream in windows. For each window i (of size W = n/C), it √ samples a set Si ⊆ [U ]
such that each x ∈ [U ] belongs to S independently with probability q := 1/W = C/ n. Hence, by linearity
of expectation, window i has expected one total occurrence of elements in Si . Also, with constant probability,
there exists a window i such that x∗ ∈ Si and it is the only occurrence of Si in window i. A natural idea is
to check if a sampled element in window i also appears in window i + 1, as x∗ should. However, this would
require O(log n) bits of space to remember the identity of the element, and would still only succeed with
constant probability.
Our (simplified) algorithm (for this case) uses only O(log log n) bits most of the time to check it. We
first sample a random hash function f that maps elements in [U ] to a range [K] for some K = poly log n. As
it processes the windows, if for window i, there is only one occurrence of elements in Si (say the element is
xi ), the algorithm remembers the log K-bit hash value v = f (xi ), rather than xi itself. Next, it proceeds to
the next window i + 1, and checks if it also has an element with the same hash value v and in Si (the sample
of window i). If that happens, only then we remember the identity of this element (via the occurrence in
window i + 1), and check if it also appears in window i + 2. When xi is not x∗ , the expected number of
occurrences of elements in Si in window i + 1 with the same hash value v is only 1/K. Hence, with only 1/K
probability, do we need to remember the identity of some element using O(log n) bits, while for the rest of
the time, the algorithm only remembers a hash value of O(log K) = O(log log n) bits.
Our next idea is then to time-share the O(log n)-space budget across multiple instances of the algo-
rithm, to boost the success probability while restricting the total space usage. We run O(log n/ log K) =
O(log n/ log log n) instances of the above algorithm in parallel. However, we only allow one instance to use
O(log n) bits at the same time. That is, if one instance already starts to use O(log n) bits for checking if the
exact element appears in two consecutive windows, then we will “pause” all other instances, and only resume
when the space is freed. That is, all other instances will simply do nothing in the meanwhile, and restart
at a later point in the stream. Each such instance may “block” all other instances at most O(1/K)-fraction
of the time. Hence, only a small fraction of the time, do we have any instance blocking others, the analysis
still goes through: Each instance of the algorithm still finds x∗ with constant probability. Thus, we are able
to increase the overall success probability to 1 − exp(−Ω(log n/ log log n)).

4
2.2 General stream with evenly distributed super heavy hitter
2
Next, let us consider a general stream of length
√ n and second moment O(n). Again let us assume that√there
∗
is a super heavy hitter x with frequency C n, and it appears once in every window of length W = n/C
as before. But, we do not make any assumption on the rest of the stream beyond its length and second
moment.
The main framework is the same as the warmup – sample-and-check. However, checking whether a
sampled element √ x is super heavy can be more challenging. For example, some element x with a lower
frequency of C n/t may locally appear like the heavy hitter x∗ , i.e., it appears like x∗ for 1/t-fraction of
the stream. Thus, the algorithm must spend at least this much time to distinguish such an element from the
true heavy hitter, if sampled. Moreover, in principle, there can be as many as O(t2 ) such elements (without
breaking the second moment bound). That is, it is even much more likely to sample such a “locally heavy”
element than x∗ itself.
Our algorithm samples a set Si ⊆ [U ] for each window i and a hash function f : [U ] → [K] as before.
Suppose xi is the only occurrence of elements in Si in window i. The algorithm remembers v = f (xi ), and
starts to check in parallel if the heavy hitter has hash value v, and is in Si . That is, the algorithm initiates
a check procedure, while at the same time continues to sample Si+1 , Si+2 , and so on, and may continue
to initiate more check procedures from future windows. As we will see below, each check terminates after
running for O(1) windows in expectation, and only O(1) check will be running at the same time in parallel
(enforced by the algorithm).
Now consider one check initiated from window i due to sampling xi ∈ Si . If xi ̸= x∗ , then for each
window that does not contain xi , there is only O(1/K) elements sampled in Si and with hash value v in
expectation. Thus, within O(fxi ) windows, we will be able to notice that there are many windows that do
not contain xi . That is, it takes O(fxi ) windows to figure out that xi is not the super heavy hitter, and this
check can return NO. To see that we will not have too many check procedures running at the same time, let
us consider the expected total running time of all check initiated throughout the stream. For each element
x, it may√appear in at most fx different windows; in each window where it appears, there is a probability
q = Θ(1/ n) of sampling it; for each time it gets sampled, it takes at most O(fx ) more windows for check to
figure out it is not the super heavy hitter (or x = x∗ ). Hence, by linearity of expectation, the total running
time of all check is X √
fx · q · O(fx ) = O( n)
x

windows. That is, an average window only has O(1) check running. We can also get a worst-case bound by
restricting the total number of check that can be executed at the same time in the algorithm, i.e., we do not
start new check procedures if it already hits the limit. It turns out that this restriction does not impact the
success probability by more than a constant.

2.3 K-super heavy hitter

To be more concrete on the check procedure, consider a check initiated due to sampling xi ∈ Si . Note that
we cannot afford to remember the identity of xi in order to check if it appears in every window. Moreover,
we cannot even remember the window index “i” (recall we have O(log n/ log log n) hash functions, and each
of them can occupy only O(log log n) bits). If we actually could remember the index i, then it suffices to
verify that every window contains an element with hash value v = f (xi ) (which we can remember) and is
contained in Si by the argument in the last subsection, since
• this holds for the heavy hitter x∗ ;

• if xi ̸= x∗ , we will be able to notice it with high probability within O(fx ) windows.

The main challenge here is that we cannot remember in which window we sampled the element. Our
solution first breaks the check into O(log n) iterations with geometrically increasing numbers of windows. In
2 This assumes that we know both the length of the stream and the second moment of the frequency vector. It turns out

that if the second moment is Θ(nt), then sampling each element in the stream with probability 1/t reduces to the case with
second moment linear in the stream length, and the super heavy hitter remains super heavy.

5
iteration l, we aim to verify 2l consecutive windows. We always start the iteration from the next window j
such that j is a multiple of 2l .3 In this case, from the fact that we are current executing iteration l, and the
index of the current window, we will be able to derive a range which i may be in. One can verify that this
is a range I of 2l windows.
Thus, Let S ′ be the union of Sk for all k ∈ I. Instead of verifying elements with hash value v and is
contained in Si , we verify elements with hash value v and is contained in S ′ . By doing a standard expectation
calculation, we can show that if xi is the heavy hitter x∗ , then within the 2l windows we execute iteration l,
xi is a K-super heavy hitter among all elements with hash value v and is contained in S ′ , i.e., within the 2l
windows, the frequency of xi squared is at least K times more than the sum of that over all other elements.
Finally, for K-super heavy hitter, we apply another sample-and-check algorithm, which uses O(log log n)
bits most of the time, and uses O(log n) bits only 1/poly log n-fraction of the time (see Algorithm 1). By
strictly enforcing only O(1) parallel instances of the algorithm may use O(log n) bits at the same time, we
obtain the space bound.
At last, we note that the algorithm generalizes to ϵ-heavy hitters in a natural way by changing the
window size and sampling probability to reflect the frequency of ϵ-heavy hitters. We will also have more
hash functions (as we allow more space) so that each heavy hitter is sampled by sufficiently many hash
functions.

3 Preliminaries
In this section, we formally define random order streams and partially random order streams, and state some
useful concentration bounds.

3.1 Problem definitions

Definition 3.1 (Adversarial streams). An adversarial stream is defined by a multiset S of n elements from
the universe U , and a bijective map Π : S → [n] that maps every element in S to a unique position in the
stream.
For example, the multiset S = {a, a, b} and the bijective map Π{a → 1, a → 3, b → 2}, correspond to the
stream a, b, a.
Definition 3.2 (Random order streams). A random order stream is defined by a multiset S of n elements
from the universe U , and a uniformly random bijective map Π : S → [n].
In the following, we define partially random order streams for every fixed ϵ > 0.
Definition 3.3 (Partially random order streams). A partially random order stream is defined by a multiset
S of n elements from the universe U , and a bijective map Π : S → [n] such that the restricted map Π|S ϵ :
S ϵ → [n] is uniformly random, where S ϵ is the subset of ℓ2 ϵ-heavy hitters in S.

3.2 Concentration bounds

We now recall some standard concentration bounds like Chebyshev’s inequality, Chernoff bound, and Hoeffd-
ing’s inequality. We also state and prove a (somewhat standard) Azuma-Hoeffding style inequality. Similar
inequalities have been proved in other works in the literature (for example, see Lemma 2.5 in [27]).

Theorem 3.4 (Chebyshev’s inequality). Let X be a random variable with variance σ 2 . For any a > 0, we
have
σ2
Pr[|X − E[X]| > a] ≤ 2 .
a

3 This allows us to not remember when we started the iteration by only remembering the current window number. We can

afford to remember l (taking O(log l) = O(log log n) bits), but not an index within a 2l range. The current window number
takes O(log n) bits, but can be shared across all hash functions.

6
Theorem 3.5 (Chernoff bound). Let X1 , . . . , Xn be independent random variables taking values in {0, 1}.
Let X = X1 + · · · + Xn and µ = E[X]. For every δ > 0, we have
µ
eδ

Pr[X ≥ (1 + δ)µ] ≤ .
(1 + δ)1+δ

Theorem 3.6 (Hoeffding’s inequality). Let X1 , . . . , Xn be independent bounded random variables such that
ai ≤ Xi ≤ bi . Consider the sum of these random variables, Sn = X1 + · · · + Xn . Then Hoeffding’s theorem
states that for all t > 0,
2t2
 
Pr[|Sn − E[Sn ]| ≥ t] ≤ 2 exp − Pn 2
.
i=1 (bi − ai )
P
Theorem 3.7 (Azuma-Hoeffding style concentration inequality). Let X = i∈N Xi where Xi are Bernoulli
random variables such that for every k ∈ [N ], E[Xk | X1 , . . . , Xk−1 ] ≥ p for some p ∈ (0, 1). Let µ = N p.
Then
• for 0 < ∆ ≤ µ/2, we have
∆2
 
Pr[X ≤ µ − ∆] ≤ exp − ,
4(µ − ∆)

• for ∆ > µ/2, we have  

−3∆ + µ
Pr[X ≤ µ − ∆] ≤ exp .
4

Proof. First, observe that for random variables Z, Y if E[Z|Y ] ≤ a, then E[ZY ] ≤ aE[Y ]. For u > 0, consider
the random variables e−uX1 , . . . , e−uXN . We have for every k ∈ [N ], E[e−uXk | e−uX1 , . . . , e−uXk−1 ] ≤
(1 − p) + pe−u . Now applying our previous observation, we have
"N −1 #
Y
−uX −u −uXi
E[e ] ≤ (1 − p + pe )E e ≤ · · · ≤ (1 − p + pe−u )N .
i=1

(1−p+pe−u )N
Applying Markov’s inequality, we have Pr[e−uX ≥ e−u(µ−∆) ] ≤ e−u(µ−∆)
. Therefore,

(1 − p + pe−u )N
Pr[X ≤ µ − ∆] ≤ min .
u>0 e−u(µ−∆)
Substituting v = 1 − e−u gives us

(1 − pv)N
Pr[X ≤ µ − ∆] ≤ min .
0<v<1 (1 − v)µ−∆

2
Using the fact that e−x−x ≤ 1 − x ≤ e−x for 0 ≤ x ≤ 1/2, we can bound Pr[X ≤ µ − ∆] as

Pr[X ≤ µ − ∆] ≤ min exp −µv + (v + v 2 )(µ − ∆) = min exp v 2 (µ − ∆) − ∆v .

0<v≤1/2 0<v≤1/2

∆
g(v) = v 2 (µ − ∆) − ∆v is an upward-facing parabola that attains minima at v = 2(µ−∆) . When ∆ ≤ µ/2,
∆
2(µ−∆) ≤ 1/2, and hence, we can bound

∆2
 
Pr[X ≤ µ − ∆] ≤ exp − .
4(µ − ∆)

For ∆ > µ/2, the minimum value for v ∈ (0, 1/2] is achieved at v = 1/2. Substituting v = 1/2 in g(v), we
get  
−3∆ + µ
Pr[X ≤ µ − ∆] ≤ exp .
4

7
 We also prove the following concentration bound for sampling without replacement.
Theorem 3.8 (Sampling without replacement). Consider a bag containing n balls numbered 1, . . . , n. Let
k < n balls be sampled at random without replacement from this bag. Let ℓ ∈ [n] and i ∈ [0, n − ℓ]. Let Xℓ,i
denote the number of balls that are sampled whose numbers lie in the range i + 1 to i + ℓ. Then,

Pr [Xℓ,i < 2ℓk/3n] ≤ 2 exp(−ℓk/18n) .

Before we prove Theorem 3.8, we state a few facts from probability theory that are useful to prove this
result. A collection of random variables are said to be negatively associated if they satisfy the following
conditions.
Definition 3.9 (Negatively associated random variables). The random variables X = (X1 , . . . , Xn ) are
negatively associated if for every disjoint index sets I, J ⊆ [n],

E[f (Xi , i ∈ I)g(Xj , j ∈ J] ≤ E[f (Xi , i ∈ I)]E[g(Xj , j ∈ J] ,

for all functions f : R|I| → R and g : R|J| → R that are either both non-increasing or both non-decreasing.
A theorem due to Dubhashi and Ranjan [28, Proposition 5] states that Chernoff-Hoeffding bounds can
be applied on negatively associated random variables. In particular, we have the following.
Theorem 3.10 (Chernoff bound for negatively associated random variables). Let X = (X1 , . . . , Xn ) be
negatively associated identically distributed Bernoulli random variables. Consider the sum of these random
variables, Sn = X1 + · · · + Xn . Let µ = E[Sn ]. Then for all 0 ≤ δ ≤ 1,

Pr[Sn ≤ (1 − δ)µ] ≤ 2 exp −δ 2 µ/2 .

Theorem 3.11 (Hoeffding’s inequality for negatively associated random variables). Let X1 , . . . , Xn be neg-
atively associated bounded random variables such that ai ≤ Xi ≤ bi . Consider the sum of these random
variables, Sn = X1 + · · · + Xn . Then Hoeffding’s theorem states that for all t > 0,

2t2
 
Pr[|Sn − E[Sn ]| ≥ t] ≤ 2 exp − Pn 2
.
i=1 (bi − ai )

The following proposition from [28, Proposition 7] states some useful properties of negatively associated
random variables.
Proposition 3.12. Let X = (X1 , . . . , Xn ) be negatively associated random variables.
1. For any index set I ⊆ [n], the random variables (Xi , i ∈ I) are also negatively associated.

2. If the random variables Y = (Y1 , . . . , Ym ) are negatively associated and are mutually independent from
X, then the augmented vector (X, Y) of random variables are also negatively associated.
3. Let I1 , . . . , Ik ⊆ [n] be disjoint index sets, for some positive integer r. For j ∈ [k], let hj : R|Ij | → R
be functions that are all non-decreasing or all non-increasing, and define Yj := hj (Xi , i ∈ Ij ). Then
the vector of random variables Y = (Y1 , . . . , Yk ) are also negatively associated. In other words, non-
decreasing (or non-increasing) functions of disjoint subsets of negatively associated variables are also
negatively associated.
We are now ready to prove Theorem 3.8.
Proof. For j ∈ [n], let Bj be the indicator random variable for the event that ball numbered j is sampled.
Dubhashi, Priebe, and Ranjan proved in [29, Corollary 11] that the random variables (Bj : j ∈ [n]) are
negatively associated. It follows from Item 1 in Proposition 3.12 that (Bj : i+1 ≤ j ≤ i+ℓ) are also negatively
Pi+ℓ
associated. Since Xℓ,i = j=i+1 Bj , E[Xℓ,j ] = ℓk/n, and the variables Bj are identically distributed, the
desired bound follows from applying Theorem 3.10.

8
4 Streaming algorithm for detecting ℓ2 super heavy hitter
In this section, we describe our subroutine for detecting super-heavy hitters and prove some lemmas that
will be useful in the analysis of our main heavy-hitter algorithms in Section 5 and Section 6.
Let S be an input stream divided into L windows, each of length W . Let m = LW denote the total length
of the stream. Let U be a universe of size at most poly n4 . K = (log n)100 is a fixed parameter.
 We say that
2 2 1
P
an element x is a K-super heavy hitter if fx ≥ K · y̸=x fy , or equivalently it is a 1 − K+1 -heavy hitter
by Definition 1.2. We are given a subset of the universe V ⊂ U , and we focus on the substream consisting
of elements in V . The positive case is that there exists a K-super heavy hitter x∗ ∈ V (with respect to
the substream restricted to V ) of frequency L and evenly distributed in the original stream. In this section,
we develop algorithms that return YES if we are in the positive case, with high probability, return NO if
we are far from it (i.e., every element in V has frequency at most K −1/8 L), and with further guarantees
for the intermediate cases. In the following section, we first give a streaming algorithm for the case when
L ≥ K 3/16 , and in the end, we handle the case when L < K 3/16 separately.

4.1 L ≥ K 3/16

Algorithm 1 Streaming algorithm for evenly distributed ℓ2 super-heavy hitters (K-SHH)

Input: a stream S divided into L windows, each of length W (m = LW denotes the total length of the
stream), parameter K = (log n)100 such that L ≥ K 3/16 , and a subset V of the universe U of size poly n
1: set T = 100 log m and p = (2/5)T /L.
2: initialize counter = 0.
3: subdivide the stream into T consecutive segments, each containing L/T windows.
4: for each segment do
5: process the segment by sampling each element of the stream that is in V independently with proba-
bility p until an element is sampled or there are no more elements left in the current segment
6: proceed to the following step if the current window is not blocked. Else, continue the sampling process
7: if an element is sampled then
8: set y to be this sampled element and t = 1.
9: else
10: go to the next segment.
11: end if
12: if the total number of remaining windows within the segment is less than L/K 1/8 then
13: go to the next segment.
14: else if y occurs in each of the next L/K 1/8 windows then
15: increment counter by 1, and go to the next segment.
16: else
17: return to Line 5.
18: end if
19: end for
Output: return YES if counter > T /4 and NO otherwise.

Consider the following (hypothetical) algorithm A5 which is a “space-unconstrained” modification of Algo-

rithm 1: The execution of A is same as that of Algorithm 1 except that in Line 5, A continuously samples
elements in the segment. In particular, even when an element is already sampled in Line 5, A does not
pause sampling elements in the current segment. For all the sampled elements, the Lines 7-18 are executed
concurrently with the sampling process in Line 5. In addition, A and Algorithm 1 share the same random
coin tosses6 . The hypothetical algorithm has no space constraints and hence Line 6 is never executed. Fi-
4 Every element in the universe can be represented using O(log n) bits.
5 We define A purely for the sake of the analysis.
6 For the analysis sake, we can imagine that Algorithm 1 also tosses a random coin whenever it sees an element of the stream

that is in V , but unlike A discards the outcomes of these random coins when there is already a sampled element that is being

9
nally, since Lines 7-18 are executed independently for all the sampled elements, we find that compared to
Algorithm 1, it is easier to analyze A directly. In the following lemmas, we first analyze A and then use it
to analyze Algorithm 1.
In the following, we analyze the space used by A in terms of the number of windows in which it uses
log n bits.

Lemma 4.1. The expected total number of windows in which A uses log n bits is at most
   
X X
 fx2  · O(T /L) +  fx  · O(T /K 1/8 ) .
x:fx ≤L/K 1/8 x:fx >L/K 1/8

Proof. Note that A uses log n bits only when executing Lines 7-18 and checking for the occurrences of
the sampled element. For any element x in the universe, the expected number of times it is sampled is
fx · O(T /L). Each time x is sampled, the Lines 7-18 are executed in at most max{L/K 1/8 , fx } windows.
P
Lemma 4.2 (Concentration lemma for the high-frequency elements). Suppose that x:fx >L/K 1/8 fx ≤ Lγ.
With probability at least 1 − 1/poly m, the total number of windows in which A uses log n bits after sampling
a high-frequency (frequency larger than L/K 1/8 ) element is at most Lγ(log m)2 /K 1/8 .
2
Phigh-frequency elements sampled by A is at most γ(log m)
Proof. It suffices to show that the total number of
with probability at least 1 − 1/poly m. Let R = x:fx >L/K 1/8 fx . For i ∈ [R], let Xi be an indicator random
P is sampled by A. We know that
variable for the event that the i-th high-frequency element in the stream
each element is sampled independently with probability p. Let X = i∈[R] Xi . By assumption, we have
R ≤ Lγ. Therefore, E[X] ≤ γ log m. Applying Chernoff bound (see Theorem 3.5), we conclude that
Pr[X > γ(log m)2 ] ≤ 1/poly m.
2
P
Lemma 4.3 (Concentration lemma for the low-frequency elements). Suppose that x:fx ≤L/K 1/8 fx ≤
L2 /(log m)c . With probability at least 1 − 1/poly m, the total number of windows in which A uses log n
bits after sampling a low-frequency (frequency at most L/K 1/8 ) element is at most L/(log m)c/2−1 .
Proof. For an element a, let fa denote its frequency and let Xa be a random variable that denotes the
number of windows in algorithm A in which either a is sampled or the window is used to check for the
occurrence of a. Observe that Xa is a bounded random variable, i.e., Xa ≤ 2fa . We have E[Xa ] ≤ p · fa2
since in every window that a occurs, it is sampled with probability at most p and then at most the following
fa windows are used to check for the occurrence of a. Observe also that by definition of A, the Xa ’s are
independent random variables. Let NA denote the random variable for the total
P number of windows in which
either a low-frequency element is sampled or checked by A. We have NA ≤ a:fa ≤L/k1/8 Xa and by linearity
of expectation, E[NA ] ≤ p · a:fa ≤L/K 1/8 fa2 ≤ O(L/(log m)c−1 ). By applying Hoeffding’s inequality (see
P

Theorem 3.6), we have

!
h
c/2−1
i L2 /(log m)c−2
= 2 exp −Θ(log m)2 .


Pr NA ≥ L/(log m) ≤ 2 exp −2 P 2
4 a:fa ≤L/K 1/8 fa

In the following, we analyze the YES and the NO cases, and prove guarantees for the correctness of the
algorithm.
Lemma 4.4 (YES case). Let x∗ ∈ V occur at least once in every window and let y̸=x∗ ∈V fy2 ≤ L2 log5 n/K.
P
In addition, suppose there is a set of at most L/c blocked windows (c >= 168) where Algorithm 1 is not
allowed to sample any new elements. Then Algorithm 1 returns YES with probability at least 1−exp(−Θ(T )).
checked.

10
Proof. We say that a window is bad if an element y ̸= x∗ is sampled in it or if it is used in Lines 7-18
to check for the occurrence of y ̸= x∗ . We first obtain a bound on the total number of bad windows in
Algorithm 1. Observe that for any fixed outcomes of the random coin tosses, the number of bad windows
in Algorithm 1 is upper bounded by the number of bad windows in A. For an element a ̸= x∗ ∈ V , let fa
denote its frequency and let Xa be a random variable that denotes the number of windows in algorithm A
in which either a is sampled or the window is used to check for the occurrence of a. Observe that Xa is a
bounded random variable, i.e., Xa ≤ 2fa . We have E[Xa ] ≤ p · (fa )2 since in every window that a occurs, it
is sampled with probability at most p and then at most the following fa windows are used to check for the
occurrence of a. Observe also that by definition of A, the Xa ’s are independent random variables.
P Let NA
denote the random variable for the total number of bad windows in A. We have NA ≤ a̸=x∗ ∈V Xa and
by linearity of expectation, E[NA ] ≤ p · F ≤ L/(log m)2 , where the last inequality follows from the fact that
F ≤ L2 /K 0.99 . By applying Hoeffding’s inequality (see Theorem 3.6), we have
!
(L/(log m))2
Pr [NA ≥ L/(log m)] ≤ 2 exp − P = exp (−Θ(log m)) .
4 a̸=x∗ ∈V fa2

Let N denote the random variable for the total number of bad windows and blocked windows in Algo-
rithm 1. Since the number of bad windows in Algorithm 1 is always less than NA and the number of blocked
windows is at most L/c, we get that

Pr [N ≥ 2L/c] ≤ exp (−Θ(log m)) .

Conditioned on N < 2L/c, we will now upper bound the probability that at the end of Algorithm 1, the
counter value is less than T /4. Let Z = L/T −L/K 1/8 ≥ 6L/7T . For segment j, let Ij be the indicator random
variable for the event that x∗ is sampled within the first Z windows in the segment. Observe that the
P counter
is incremented in Line 15 whenever Ij = 1 since x∗ appears in every window. Hence, counter ≥ j∈[T ] Ij .
Let Nj denote the total number of bad and blocked windows within the first U windows in segment j. We
have
 
E Ij N1 , . . . , NT , N < 2L/c ≥ 1 − (1 − p)Z−Nj ≥ 1 − (1 − p(Z − Nj ) + (p(Z − Nj ))2 /2) ≥ 3p(Z − Nj )/4 ,

since pZ ≤ 1/[Link],
 
3pZT 3pZT 3pL T 71
E counter N1 , . . . , NT , N < 2L/c ≥ − (3p/4)N ≥ − ≥ · .
4 4 2c 4 70

Observe that conditioned on N1 , . . . , NT , the Ij ’s are independent. Hence, by applying Hoeffding’s inequality,
we have  
Pr counter < T /4 N1 , . . . , NT , N < 2L/c ≤ exp (−Θ(T )) .

Lemma 4.5 (NO case(s)). If there is no element with frequency L/K 1/8 or if there is only one element
with frequency at least L/K 1/8 but at most L/2, then Algorithm 1 returns NO with probability at least
1 − exp(−Θ(T )).

Proof. The counter is incremented only if the sampled element has frequency at least L/K 1/8 . Hence, if
there is no element with frequency at least L/K 1/8 , the algorithm always returns NO.
In the second case where there is only one element x with frequency at least L/k 1/8 , the element must
be sampled at least T /4 times for Algorithm 1 to return YES. We will show that with probability at least
1 − exp(−Θ(T )), x is sampled less than T /4 times in Algorithm 1. Consider algorithm A. Since whenever
an element is sampled in Algorithm 1, it is also sampled in A, it suffices to show that with probability at
least 1 − exp(−Θ(T )), x is sampled less than T /4 times in A. Let Xi be the indicator random variable
for the event that x is sampled by A at its i-th occurrence in the stream. We are interested in the sum

11
 Pfx
X = i=1 Xi , where fx is the frequency of x. Each Xi is an independent Bernoulli random variable with
E[Xi ] = p. By linearity of expectation, we have

E[X] = f · p ≤ T /6 .

By applying the Chernoff bound, we have

Pr[X ≥ T /4] ≤ exp(−Θ(T )) .

We now address the case when the total number of windows is too small, i.e., L < K 3/16 . In this case,
we simply hash every element in V using a uniform O(log K)-bit hash function and return YES if there
are at least L elements in the substream restricted to V and all their hash values are equal, else return
NO. We will now argue that Lemmas 4.1 to 4.5 hold in this case as well. Observe that Lemmas 4.1 to 4.3
hold trivially because the algorithm
P never uses more than O(log K) bits. In the YES case corresponding to
Lemma 4.4, the condition that y̸=x∗ ∈V fy2 ≤ L2 log5 n/K implies that there is no element other than x∗
in the substream restricted to V . Therefore, the algorithm always outputs YES in this case. On the other
hand, consider the NO case. If the substream restricted to V has fewer than L elements, then the algorithm
always outputs NO. If the substream has at least L elements, then the conditions in the NO case imply that
there are at least K 1/8 /2 distinct elements in the substream. The probability that they all have the same
hash value is at most 1/poly n.

5 Streaming algorithm for detecting ℓ2 heavy hitter

In this section, we present the algorithm for finding an ℓ2 heavy hitter with high probability using O(log n)-
bits of space, assuming the heavy hitter is evenly distributed in the stream. Here, we assume that the length
of the stream is n, the second moment of the frequency vector is ≈ C 2 n, and we assume access to free
randomness.
The algorithm is as follows (Algorithm 2, Algorithm 3). At a high level, we sample O(log n/ log log n)
independent hash functions with O(log log n)-bit hash values. The goal is to compute for (most of) the hash
functions, what is the hash value√ of the heavy hitter, if exists. To this end, we partition the stream into
windows of size approximately n so that each window has on average on occurrence of the heavy hitter.
Then√we sample a random set Si ⊆ U for each window, each element is contained in Si with probability
≈ 1/ n independently. Note that, with constant probability, some window will sample the heavy hitter, and
no other element appearing in the window is sampled. We hope this happens, and for the sampled elements,
we remember its hash value, and run a check procedure to check if this is the hash value of the heavy hitter.
For the check procedure, the high level idea is to gradually increase the length of the interval. In the l-th
iteration, we will examine 2l consecutive windows, whether there is a heavy hitter with the given hash value.
As argued in the overview, this is done by invoking the K-super-heavy-hitter subroutine from the previous
section.

12
Algorithm 2 Algorithm for ℓ2 heavy hitters
Input: a stream
√ of length n of elements from set U of size poly n such that some element x∗ appears at
least C n times √
1: assumptions: dividing the stream into windows of length W := n/C, there is at least one occurrence of
x∗ in each window; ℓ22 of the frequency vector is at most (1 + 2−8 )C 2 n
Output: x∗
1
2: fix parameters q = C √ n
, K = log1000 n and J = 128 log U/ log K
3: let h(1) , . . . , h(J) be independent random hash functions h(j) : U → [K]
(j) (j)
4: for each window i and each j ∈ [J], sample a random set Si ⊆ U such that each x ∈ U is in Si with
probability q independently using free random bits
5: for each window i do
(j)
6: for j ∈ [J], if there is some x ∈ Si that appears in the window, record (j, h(j) (x)) (if there is more
than one such x for some j, record the first one)
7: for each hash (j, v) recorded at the end of the window do
8: if at most 100 instances of check are still running for this j then
9: start check(j, v) in parallel
10: end if
11: end for
12: end for
13: For each j, record the first (j, v) such that check(j, v) returned YES
14: If there is an x such that h(j) (x) = v for at least 4 log U/ log K of them, return x (if there is more than
one such x, return any)

√
For every l = 0, . . . , maxL = log(C n/8), we divide the stream into intervals of 2l windows, i.e., for
l = 0, each segment is a single window; for l = 1, the first segment consists of the first two windows, then the
second consists of the next two windows. Each length-2l interval is subdivided into two length-2l−1 intervals.
We now build a binary forest on this multi-level division: For each length-2l−1 interval, its parent is the
chronologically next interval of length-2l .7 The check function runs K-SHH on these intervals in increasing
levels, the l-th round will be on the parent interval of the l − 1-th round. We call this binary forest the
execution forest of check (see Figure 1 below).
<latexit sha1_base64="4fI0Y1GqStpNuYPG/UZzOkvDd4o=">AAALQHicnVZNb9tGEGXSqE3Vj8TtsZdNjQB2LdIkZcsGEhlBe+kxBeokgKgay+VSWmj5gd1lJYXgn+upf6H/oLei1546u6JsUVIEOQQE7L6ZebPzODtUmHMmlev+9eDhJ49an372+PP2F19+9fWTpwffvJFZIQi9JhnPxLsQS8pZSq8VU5y+ywXFScjp23Dyk7a//Z0KybL0VzXP6TDBo5TFjGAF0M3Boz+DkI5YWio2eZ8zogpBq4EkmNO+65wP2+0gzoCQjFEwQyxFpdvxOn6FyjZCAYvTItGGPvJRGcSM80jg6SDkBX127j6bjpmiQ3R0+UMwO3Edv+OdHyNBicLpiNMav7SNpXf8otKclEu6yjUSeP6xXDFrnPIKuebcgBlqm2NFZx01ZmSyzmzb6OTkyO7B1r44fnG/KP8uanmOaruSjuN0zjfV7O5S82yZ8aIhgIHPjACXe2q5P9P9lFzlrSXpakm6u4TcEuTdBe2ho+dtCnm2S0h/mbHbKN/Avin/bE8h92e6n5CrvLeaXHRsb5eQW4Lcu6A9hPS7m0L2dgm5vAGN4gH0TOn+niLux1IfnaZRY2a1b54euo5rHrS58OrFoVU/r28OWjdBlJEioakiHEs58NxcDUssFCMcGINC0hyTCR7RASxTnFA5LM3MrdBzQCIEAsIvVcigqxElTqScJyF4JliN5bpNg9tsg0LFl8OSpXmhaEoWieKCI5UhPcBRxLQ6fA4LTASDsyIyxgITBWO+kUXL06iiDAVmkWxiBOfKzuImmI/inGdKKhyuKXFrqlADlqxImZrVvrUPZ5BRzEtt0mmXuKQKTkcmyHxoUMjSLO8HioHAa17wZYNqQd5MRBKFVE0pTaFZIzo7daSaQ7SPsBjJ/uIWzRC0Fyhx6pAsojVoborp5cAQmfCXh14Q0Vhn0y9BUFlwVVaLC/qBmKtDf1dM1a62159nHItq4+XYMZ2nCU7Borf1TpdNsiTHqg9d67jNOAmdOqZRExylhc4HQ2CBa7a73JLpbz1LR5tGLEQ2lZt4REkmzF8E6cBBxkkm8rFheB5gzrNpxGTO8TyE+TFpdp25CSrkQCpoSqdQChQVlYEaw6srElaVQJGPy8Xmg27GT+CQkbLeb7hyHEJ7LDiPbgOPd/hp0tsETlPEqcB5zEb1y9Bvwb6y6ybrrygCTZVgMQE1ZAfpVR8rtFQZJk4PTZkaI316ELc0s7mqqg64KLilhqFmo1W1mu7lR6U735JvIKj+10ej4c7M6/1Ioi1gN9K9tdkj72c23F5S8GJtoszN1MBFBSPZWx/Am4s3vuP1nN4v/uGrH+vh/Nj6zvreOrI868J6Zf1svbauLdI6bV23fmvdtP9o/93+p/3vwvXhgzrmW6vxtP/7H7u6sBY=</latexit>

Figure 1: Execution forest of check. An example execution path of a check function initiated at one of the
leaf nodes is highlighted in blue.
7 Note that there is more than one node with no parent, hence, it is a forest.

13
Algorithm 3 check(j, v) checks if h(j) (x∗ ) = v (when x∗ exists)
√
1: let maxL = log(C n/8)
2: for l = 0, . . . , maxL do
3: currently at the beginning of a level-l node I in the execution forest, let it be the beginning of
the i-th window such that 2l | i; the current check must be initiated from a window in the range
[max{0, i − 2l+1 + 1}, i − 2l ]
4: if there is another instance of check with the same j and v is about to start the same round l (hence
on the same I), then keep only one instance and terminate the others
S (j) (j)
5: let UI,j ← k∈[max{0,i−2l+1 +1},i−2l ] Sk be the union of all Sk of windows that may have initiated
this check
6: run K-SHH (Algorithm 1) on I, restricted to elements in UI,j with hash value v (i.e., set the parameter
V to UI,j,v , n is the length of the original stream, and we assume that the universe size is at most poly n,
W and K are fixed parameters that do not vary across the different executions of K-SHH)

UI,j,v := {x : h(j) (x) = v} ∩ UI,j ,

denote this instance of K-SHH by AI,j,v ; only K-SHH instances AI,j,v with the same j can use
O(log n) bits at the same time (any AI,j,v that is using O(log n) blocks all other AI ′ ,j ′ ,v′ for
j ′ ̸= j, i.e., they do not proceed after Algorithm 1 in Algorithm 1)
7: if K-SHH returns NO then
8: return NO
9: end if
10: wait until the start of the next window i such that 2l+1 | i
11: end for
12: return YES

Like in the previous section, in order to analyze the algorithm, we need to analyze a hypothetical version
of it.
Definition 5.1. The hypothetical version of Algorithm 2 may have any number of instances of check running
at the same time for each j (no restriction in Algorithm 2). Also it uses the hypothetical versions of K-
SHH, and the K-SHH subroutines may use O(log n) bits at the same time (no restriction in Algorithm 5 in
Algorithm 3).
It is easy to verify that when using the same randomness, if the real algorithm has some K-SHH subroutine
use O(log n) bits in a window, then the the same subroutine must also be using O(log n) bits in the same
window in the hypothetical version. Hence, the hypothetical version generally uses more space, but it has
less dependence between different subroutines, making it easier to analyze. In the following, most of the
lemmas will be proving bounds on the hypothetical version directly, while they should also carry over to the
actual algorithm.
Lemma 5.2. In the hypothetical version of the algorithm, for each hash function j ∈ [J], the expected
number of windows with at most 100 instances of check running is at least (3/4 − o(1)) · n/W .
Proof. Consider any node I in the execution forest of check in level l < maxL, fix a hash function index
j ∈ [J] and one possible hash value v ∈ [K]. Now let us analyze the probability that a check procedure on
(j, v) passes the round-l test on I, i.e., the probability that it advances to round l + 1 on the parent node of
I. Note that there can be at most one check on any particular (j, v) that runs the round-l test on I due to
Algorithm 5.
To this end, we will apply Lemma 4.5 and bound the probability of the necessary conditions for check(j, v)
to pass round l on I. Recall that K-SHH is run on the substream restricted to the set of elements UI,j,v .
Lemma 4.5 ensures that if neither of the following happens, then K-SHH must return NO except with
1/poly n probability:
1. there exists an element in UI,j,v with frequency at least 2l−1 in I;
2. there exist at least two elements in UI,j,v with frequency at least 2l · K −1/8 in I.

14
Hence, it suffices to consider check(j, v) of these two types, i.e., we say check(j, v) has Type 1 with respect
to I if it passes round l on I and it satisfies the first condition above; similarly, check(j, v) has Type 2 with
respect to I if it passes round l on I and satisfies the second condition.
Let us first consider Type 1 check procedures. For a fixed I, let αI be the number of elements with
frequency at least 2l−1 in I. For any given element, with probability K −1 , it has hash value v, and with
(j)
probability at most 2l ·q, it belongs to one of Sk that could have initiated check to run on I in round l. Each
fixed element belongs to UI,j,v with probability at most K −1 · 2l · q, hence, the probability that check(j, v)
has Type 1 with respect to I is at most
αI · K −1 · 2l · q.
If check(j, v) has Type 1 with respect to I, then it may wait for at most 2l windows and will continue to
execute on the parent node of I for 2l+1 windows, a total of at most 3 × 2l windows. Now for a fixed pair
(j, v), we will upper bound the total running time (including the waiting time to get to the parent node) of
K-SHH on all the parent nodes of nodes where check(j, v) is executed and has Type 1 with respect to that
node. By linearity of expectation, the expected number of windows is at most
X X X X
(αI · K −1 · 2l · q) · 3 · 2l = 3K −1 q αI · 4l . (5.3)
l≥0 I in level l l≥0 I in level l

The following claim lets us upper bound the RHS.

Claim 5.4. We have X X
αI · 4l ≤ (8 + 2−5 )C 2 n.
l≥0 I in level l

Proof of Claim 5.4. Recall that αI is the number of elements with frequency at least 2l−1 in I. Consider
any element x with frequency fx , its contribution to LHS in the claim is equal to
X X
4l ,
l≥0 I in level l:fx,I ≥2l−1

′
where fx,I is the frequency of x in I. Observe that for any I in level l, I ′ ⊆I,I ′ in level l′ <l 4l ≤ 4l , where a
P
node I ′ is said to be contained in a node I if the windows of I ′ are a subset of the windows of I. We say
that a node I at level l is maximal with respect to x if fx,I ≥ 2l−1 and there exists no node I ′ ⊃ I at level
′
l′ > l such that fx,I ′ ≥ 2l −1 . Hence, the above sum is bounded by twice the sum over all maximal nodes,
and these nodes must be disjoint, i.e., not share any windows. Therefore, we have
X X XX X
αI · 4l = 4l
l≥0 I:I in level l x l≥0 I in level l:fx,I ≥2l−1
XX X
≤2 4l
x l≥0 maximal I in level l w.r.t. x
XX X
2
≤8 fx,I (fx,I ≥ 2l−1 )
x l≥0 maximal I in level l w.r.t. x
X
≤8 fx2 (We are summing over maximal I and a2 + b2 ≤ (a + b)2 for a, b ≥ 0)
x
≤ (8 + 2−5 )C 2 n.

The claim holds.

Now, it follows from Claim 5.4 that (5.3) is at most

25C 2 n · K −1 q.

Taking the sum over all v, the expected total running time for a fixed hash function index j ∈ [J] is at most

25C 2 nq.

15
Since there are n/W = C 2 nq windows, by Markov’s inequality, at most 1/4 fraction of the windows have
more than 100 checks running due to passing the previous round with Type 1.

To analyze Type-2 check procedures, let βI be the number of elements with frequency at least 2l · K −1/8
in I. The probability that check(j, v) has Type 2 with respect to I is at most
 
βI
· (K −1 · 2l · q)2 ≤ (βI · K −1 · 2l · q)2 .
2

We have the following claim, since all intervals I in the same level are disjoint.
Claim 5.5. For each fixed l, we have
X
βI · 4l · K −1/4 ≤ (1 + 2−8 )C 2 n.
I in level l

Since there are n/(2l W ) nodes in level l, for an average node I, we have

(1 + 2−8 )C 2 n
βI · 4l · K −1/4 ≤ = (1 + 2−8 )C 2 2l W.
n/(2l W )

That is, for an average node I,

βI · K −1 · 2l · q ≤ (1 + 2−8 )C 2 2l W · K −3/4 · 2−l · q = O(K −3/4 ).

By Markov’s inequality, except for at most O(K −1/4 log n) fraction of the nodes, we have

βI · K −1 · 2l · q ≤ K −1/2 log−1 n. (5.6)

That is, there are at most O(K −1/4 log n)-fraction of level l + 1 nodes such that check(j, v) can execute on
them due to passing level l on a node violating (5.6). Summing over all levels l, at most K −1/4 log2 n = o(1)-
fraction of the windows can have such a check running.
For a node I satisfying (5.6), the probability that check(j, v) has Type 2 with respect to I is at most
K −1 log−2 n. Taking a union bound over all v, the probability that a check corresponding to a fixed hash
function j ∈ [J] is of Type 2 with respect to I is at most log−2 n. If check(j, v) has Type 2 with respect to
I, then it will continue to execute on the parent node of I for a total of at most 3 × 2l windows. By linearity
of expectation, the expected total number of windows executing such a check is at most
X X X X
log−2 n · 3 · 2ℓ ≤ 3 log−2 n 2ℓ ≤ 3 log−1 n · (n/W ) . (5.7)
l≥0 I in level l satisfying (5.6) l≥0 I in level l

By Markov’s inequality, at most o(1) fraction of all the windows have even a single instance of such a check
running.
Combining the analysis for the two types, we prove the lemma.

Lemma 5.8. Let I be a node in the execution forest of check, and I1 , I2 be its children. Suppose I is in level
l such that 2l W ≤ n/ log10 n, and FI1 , FI2 , FI ≤ O(2l W log4 n). For a fixed j ∈ [J] and hash function h(j) ,
the expected total number of windows AI,j,v blocks for all v, conditioned on h(j) , is at most O(2l / log4 n).
Proof. Recall that check(j, v) passes round l − 1 on I1 if either

• Type 1: ∃x∗ ∈ UI,j,v such that fx∗ ,I1 ≥ 2l−2 , or

• Type 2: ∃x∗1 , x∗2 ∈ UI,j,v such that fx∗1 ,I1 , fx∗2 ,I1 ≥ 2l−1 · K −1/8 .
We will analyze the expected number of blocked windows conditioned on each singleton event, then apply
the law of total probability.

16
 To this end, we apply Lemma 4.1, which asserts that the expected number of blocked windows, conditioned
on UI,j,v , is at most8
X n o
2
min fx,I · O(2−l · log n), fx,I · O(K −1/8 · log n) .
x∈UI,j,v

Let HI1 be the set of heavy elements in I1 , {x : fx,I1 ≥ 2l−2 }. Let HI1 ,v ⊆ HI1 be the set of heavy
elements in I1 with hash value v, {x : h(j) (x) = v, fx,I1 ≥ 2l−2 }. Similarly, let MI1 be the set of medium
heavy elements in I1 , {x : fx,I1 ≥ 2l−1 · K −1/8 }. Let MI1 ,v ⊆ MI1 be the set of medium heavy elements in I1
with hash value v, {x : h(j) = v, fx,I1 ≥ 2l−1 ·K −1/8 }. Note that these sets are fixed given the stream and h(j) .
By Chernoff bound (Theorem 3.5), we have |HI1 ,v | ≤ O(|HI1 |/K + log n) and |MI1 ,v | ≤ O(|MI1 |/K + log n)
with probability 1 − 1/poly n. We assume below that this happens, since it only adds at most o(1) to the
expectation otherwise.
For Type 1, fix x∗ ∈ HI1 ,v . Since UI,j,v ⊃ UI1 ,j,v and Pr x ∈ UI,j,v | h(j) ≤ 2l · q for any element x ∈ U
 

such that hj (x) = v, taking expectation over UI,j,v , we have

 
X n o
EUI,j,v  min fx,I2
· 2−l · log n, fx,I · K −1/8 · log n | x∗ ∈ UI1 ,j,v , h(j) 
x∈UI,j,v
 
X
≤ EUI,j,v  2
fx,I h(j)  · 2−l · log n + fx∗ ,I · K −1/8 · log n
x∈UI,j,v ,x̸=x∗
X
≤2 ·q· l 2
fx,I · 2−l · log n + fx∗ ,I · K −1/8 · log n
x:h(j) (x)=v
X
= 2
fx,I · q log n + fx∗ ,I · K −1/8 · log n.
x:h(j) (x)=v

The calculation is similar for Type 2. Fix x∗1 , x∗2 ∈ MI1 ,v , we have that
 
X n o
EUI,j,v  2
min fx,I · 2−l · log n, fx,I · K −1/8 · log n | x∗1 , x∗2 ∈ UI1 ,j,v , h(j) 
x∈UI,j,v
X
≤ 2
fx,I · q log n + (fx∗1 ,I + fx∗2 ,I ) · K −1/8 · log n.
x:h(j) (x)=v

Summing up over the two types and over v, we have that

X
E[# blocked windows by AI,j,v · 1(check(j, v) passes on I1 )]
v
X X
≤ E[# blocked windows by AI,j,v · 1(x∗ ∈ UI1 ,j,v )]
v x∗ ∈HI1 ,v
X X
+ E[# blocked windows by AI,j,v · 1(x∗1 , x∗2 ∈ UI1 ,j,v )]
v x∗ ∗
1 ,x2 ∈MI1 ,v
 
X X
≤ |HI1 ,v | · 2l−1 q · O  2
fx,I · q log n (5.9)
v x:h(j) (x)=v
 
X X
+ (|MI1 ,v | · 2l−1 q)2 · O  2
fx,I · q log n (5.10)
v x:h(j) (x)=v
X X
+ 2l−1 q · O(fx∗ ,I · K −1/8 · log n) (5.11)
v x∗ ∈HI1 ,v

8 Note that Lemma 4.1 is stated in a slightly different form, which is equivalent to the expression here.

17
 X X
+ |MI1 ,v |(2l−1 q)2 · O(fx∗ ,I · K −1/8 · log n). (5.12)
v x∗ ∈MI1 ,v

Note that X
|HI1 | ≤ 2−2(l−2) · 2
fx,I 1
≤ O(2−2l · FI1 ) ≤ O(2−l W log4 n),
x

and X
|MI1 | ≤ K 1/4 · 2−2(l−1) · 2
fx,I 1
≤ O(K 1/4 · 2−2l · FI1 ) ≤ O(K 1/4 2−l W log4 n).
x

Thus, we have
|HI1 ,v | ≤ O |HI1 | · K −1 + log n ≤ O K −1 2−l W log4 n + log n ,

and  
|MI1 ,v | ≤ O |MI1 | · K −1 + log n ≤ O K −3/4 2−l W log4 n + log n .

By Cauchy-Schwarz, we have
X X s X
fx∗ ,I ≤ |HI1 | · fx2∗ ,I
v x∗ ∈H I1 ,v x∗ ∈HI1
q 
≤O 2−l W log4 n · 2l W log4 n

≤ O(W log4 n),

and
X X s X
fx∗ ,I ≤ |MI1 | · fx2∗ ,I
v x∗ ∈MI1 ,v x∗ ∈MI1
q 
1/4 −l 4 l 4
≤O K 2 W log n · 2 W log n
 
≤ O K 1/8 W log4 n .

Thus, we have
X
O |HI1 ,v |2l q 2 log n · FI,v


(5.9) ≤
v
X
O (K −1 2−l W log4 n + log n)2l q 2 log n · FI,v


≤
v
= O (K −1 q log5 n + 2l q 2 log2 n)FI

≤ O (K −1 q log5 n + 2l q 2 log2 n)2l W log2 n

≤ O(K −1 2l log7 n + 22l q log4 n)

≤ O(2l / log4 n),
X  2 
−3/4 −l 4 l
(5.10) ≤ O (K 2 W log n + log n)2 q · q log n · FI,v
v
 
≤ O (K −3/2 q log9 n + 22l q 3 log3 n) · FI
 
≤ O (K −3/2 q log9 n + 22l q 3 log3 n) · 2l W log4 n
 
≤ O K −3/2 2l log13 n + 23l q 2 log7 n
≤ O(2l / log4 n),
 
(5.11) ≤ O K −1/8 2l qW log5 n

18
 ≤ O 2l / log4 n ,


X X  
(5.12) ≤ O (K −3/4 2−l W log4 n + log n)22l q 2 · fx∗ ,I · K −1/8 log n
v x∗ ∈MI1 ,v
 
≤ O (K −3/4 2−l W log4 n + log n)22l q 2 · K 1/8 W log4 n · K −1/8 log n
 
≤ O K −3/4 2l log9 n + 22l q log6 n
≤ O(2l / log4 n).

The four bounds combined imply that

X
E[# blocked windows by AI,j,v · 1(check(j, v) passes on I1 )] ≤ O(2l / log4 n).
v

A similar bound can be obtained for I2 . Since running AI,j,v requires check(j, v) to pass either on I1 or I2 ,
we prove the lemma.
Lemma 5.13. In the hypothetical version, for each j ∈ [J], all K-super heavy hitter algorithms initiated by
hash function j block at most O(1/ log4 n)-fraction of the windows in total, with probability 1 − 1/poly n.
Proof. We first consider l such that 2l W < n/ log10 n, and bound the total number of blocked windows by
all AI,j,v for I of size 2l . Fix such a node I with children nodes I1 , I2 . If FI1 , FI2 , FI ≤ O(2l W log4 n), then
by Lemma 5.8, the expected total number of blocked windows by AI,j,v for all v is O(2l / log4 n) conditioned
on h(j) . Denote this random variable by XI,j . Note that conditioned on h(j) , XI,j only depends on the
(j)
random sets Si (as well as the randomness used by AI,j,v ), and for different I of size 2l , they depend on
(j)
different sets Si . Hence, XI,j are independent for all I of the same size 2l conditioned on h(j) .
Since there can be at most O(n/2l W log4 n) I’s with at least one of FI1 , FI2 , FI more than Ω(2l W log4 n),
and XI,j ≤ |I|, we have
 
X
E XI,j | h(j)  ≤ O(n/2l W log4 n) · 2l + n/2l W · O(2l / log4 n) = O(n/(W log4 n)).
I:|I|=2l

4
By Theorem 3.6, and the fact that XI,j ≤ 2l , we have
P
I:|I|=2l XI,j ≤ O(n/(W log n)) except with
probability 1/poly n.
Now for l such that 2l W ≥ n/ log10 n, we will apply Lemma 4.3 and Lemma 4.2 to bound the number of
blocked windows. Fix such a node I of length 2l . Let I1 and I2 be its children. We claim the following.
Claim 5.14. For each (j, v), the number of windows blocked by AI,j,v is at most 2l /K 1/17 with probability
at least 1 − 1/poly n.
Before we prove this claim, let us see why this claim suffices to prove the desired bound. Consider the
definitions of HI1 , HI1 ,v , MI1 , MI1 ,v from the proof of Lemma 5.8. We execute AI,j,v only if check(j, v) passes
round l − 1 on I1 or on I2 . Recall that check(j, v) passes round l − 1 on I1 only if either
• Type 1: ∃x∗ : h(j) (x∗ ) = v and fx∗ ,I1 ≥ 2l−2 , or
• Type 2: ∃x∗1 , x∗2 : h(j) (x∗1 ) = h(j) (x∗2 ) = v and fx∗1 ,I1 , fx∗2 ,I1 ≥ 2l−1 · K −1/8 .
We now bound the total number of check functions that are running on I for check(j, v) that passes
round l − 1 on I1 . Recall that for fixed j and v, we run only a single instance of check(j, v) on I. Therefore,
the total number of check functions (for each j) is at most

1[∃x∗ : h(j) (x∗ ) = v and fx∗ ,I1 ≥ 2l−2 ]+1[∃x∗1 , x∗2 : h(j) (x∗1 ) = h(j) (x∗2 ) = v and fx∗1 ,I1 , fx∗2 ,I1 ≥ 2l−1 ·K −1/8 ]
X

Observe that v 1[∃x∗ : h(j) (x∗ ) = v and fx∗ ,I1 ≥ 2l−2 ] = |HI1 | ≤ O(log20 n). As for the second term,
P
we want to bound the number of hash values v such that at |MI1 ,v | ≥ 2. Since 2l W < n/ log10 n, we have

19
|MI1 | ≤ O(K 1/4 log20 n). For any t ≥ 1, the probability that there are t hash values with |MI1 ,v | ≥ 2 is at
most  
|MI1 | 1 t
· 2t · t! · K ≤ K −t/3 .


2t
Since this probability is exponentially small in t, the number of hash values v such that at |MI1 ,v | ≥ 2 is at
most O(log n) with probability at least 1 − 1/poly n. The analysis is similar for I2 .
Combining this with Claim 5.14 and summing and taking a union bound over all the nodes with 2l W ≥
n/ log10 n, we conclude that at most O(1/ log n)-fraction of the windows are blocked in total, with probability
at least 1 − 1/poly n. We will now prove the claim by applying Lemma 4.2 and Lemma 4.3. Consider
an instance of check(j, v) that is initiated on I. In order to apply Lemma 4.2, we need to bound the
total number of occurrences of elements with hash value v and frequency at least 2l /K 1/8 in I. The total
number of such elements is at most O(K 1/4 log20 n). The hash function h(j) assigns each of these elements
to hash value v independently at random with probability 1/K. Applying the additive form of Chernoff
bound, we conclude that the total number of elements assigned to hash value v√ is at most O(log n) with
probability at least 1 − 1/poly n. Since each element has frequency at most O( n), we conclude that the
total number of occurrences
   of elements with hash value v and frequency at least 2l /K 1/8 in I, is at most
√ l √ W 11

O( n log n) ≤ O 2 n
log n , with probability at least 1 − 1/poly n. By applying Lemma 4.2, we
conclude that the number of windows blocked due to elements of frequency at least 2l /K 1/8 is at most
2l /K 1/17 with probability at least 1 − 1/poly n.
To apply Lemma 4.3, we need to bound the second moment of the frequencies of elements which occur
less than 2l /K 1/8 times in I. For an element a of frequency at most 2l /K 1/8 , let Xa be thePindicator random
variable for the event that h(j) (a) = v and let Ya = fa,I2
Xa . We want to bound Y = a:fa,I <2l /K 1/8 Ya .
Note that X
2
E[Y ] = (1/K) fa,I ≤ n/K .
a:fa,I <2l /K 1/8

Since 0 ≤ Ya ≤ fa2 , we can apply Hoeffding’s inequality (Theorem 3.6) to conclude that with probability
at least 1 − 1/poly(n), Y ≤ n/K 1/8 . Now, by applying Lemma 4.3, we conclude that the number of
windows blocked due to elements of frequency less than 2l /K 1/8 is at most 2l /K 1/17 with probability at
least 1 − 1/poly n. Thus, we have proved our claim.
The main lemma that leads to the final claim on the success probability of the algorithm is the following.
′ (j ′ )
We focus on one j, and fix the random bits used by all j ′ ̸= j, i.e., hash function h(j ) , the sets Si , and the
random bits used by K-SHH instances that are initiated by some instance of ˇ(j ′ , v). Then we will analyze
regardless of fixing of these random bits, we can always find the correct hash value vj = hj (x∗ ) with some
constant probability (only over the randomness used by j).
Lemma 5.15. For each j, conditioned on all the random bits used by j ′ ̸= j, the probability that we find the
correct vj = hj (x∗ ) is at least 1/25, and we find an incorrect hash value with probability O(K −1/2 ).
Proof. Fix the random bits used by all j ′ ̸= j. This fixes the set of windows blocked by j ′ ̸= j in the
hypothetical algorithm. By Lemma 5.13, at most 1/ log4 n-fraction of the windows are blocked in total.
Recall that the windows blocked by the real algorithm are a subset, the remaining at least (1 − 1/ log4 n)-
fraction of the windows are guaranteed to not be blocked by j ′ ̸= j, regardless of the randomness used by
hash function j.
For j fixed, the algorithm records the first (j, v) such that check(j, v) returns YES. We will prove
• for all v ̸= h(j) (x∗ ), where x∗ is the heavy hitter, check(j, v) will return YES with probability O(K −1/2 );
• for v = h(j) (x∗ ), check(j, v) will be initiated and will return YES with probability Ω(1).
For the first bullet point, consider the last √
round of check, i.e., l = maxL. Consider a node I in level l of
the execution forest, the length of I is 2l = C n/8. Fix v ̸= h(j) (x∗ ), we now upper bound the probability
that check(j, v) passes the last round on I. √ First observe that no element other than the heavy-hitter in
UI,j,v can have frequency at least 2l−1 = C n/16. √ Hence, by Lemma 4.5, this requires at least two elements
in UI,j,v with frequency at least 2l · K −1/8 = C nK −1/8 /8. But there can be at most O(K 1/4 ) elements

20
with this frequency,
 even in the whole stream. The probability there exists two of them with hash value v
2 
K 1/4
= O K −3/2 . In particular, check(j, v) passes the last round on I with probability


is at most O K

at most K −3/2 . There are O(1) nodes in the last level, taking a union bound over v and the nodes in this
level, we conclude that the algorithm records a wrong hash value for j with probability at most O(K −1/2 ).
In the remainder of the proof, we will show that we will sample and start check(j, v) from a “good”
window with constant probability, and a check(j, v) that is started from a “good” window will return YES
with constant probability.
Consider a window i, suppose we start check in parallel at the end of this window. Let I0 , I1 , . . . , ImaxL
be the nodes in the execution forest that this check will run K-SHH on, where Il is in level l (in particular,
I0 consists of window i + 1). We say window i is “good” if
1. I0 , . . . , ImaxL exist, i.e., i is not close to the end of the stream,
2. for each l = 0, . . . , maxL, Il has at most 2l log−1 n blocked windows, and

3. for each l = 0, . . . , maxL, the second moment of Il is at most 2l W log3 n, i.e., 2

≤ 2l W log3 n.
P
x fx,I l

Note that the definition of a good window depends on the randomness used when checking other hash
functions j ′ ̸= j (for the second condition), but not the randomness used by j.
For each good window, v = h(j) (x∗ ), and l = 0, . . . , maxL, we have
 
X
E 2 
fx,I l
≤ Pr[x ∈ UIl ,j,v ] · 2l W log3 n ≤ (2l q) · 1/K · 2l W log3 n = 4l log3 n/K.
x∈UIl ,j,v ,x̸=x∗

Therefore, by Markov’s inequality and taking the union bound over all l, we have that with probability at
least 1 − o(1), for every l = 0, . . . , maxL,
X
2
fx,I l
≤ 4l log5 n/K .
x∈UIl ,j,v ,x̸=x∗

Assuming the bound holds, if we start check(j, v) for v = h(j) (x∗ ) from a good window, then for each
round l, K-SHH returns YES with probability 1 − 1/poly n by Lemma 4.4. Taking a union bound over all
levels, check returns YES except with o(1) probability. It remains to show that we will start such a check
with constant probability.
We show that at least a constant fraction of the windows are good.
Claim 5.16. With probability 1 − 1/poly n, at least 1/2 − o(1) fraction of the windows are good.
To see this, we analyze the fraction of windows that is not good due to the violation of each of the
conditions above.
√
1. Note that 2maxL = C n/8 = n/8W . As long as i + 4 · 2maxL ≤ n/W , i.e., i ≤ n/2W , I0 , . . . , ImaxL exist.
At most half of the windows violate this condition.
′
2. By applying Lemma 5.13
−3

and taking the sum over all hash functions j ̸= j, we observe that at
most O (n/W ) · log n windows are blocked with probability 1 − 1/poly n. For a fixed l, at most
O((n/W )·log−3 n)
= O (n/2l W ) log−2 n nodes in level l can violate the condition. For each such node,


2l log−1 n
there are exactly 2l windows i that could lead to this node in level l. At most O((n/W ) log−2 n) windows
violate this condition for each l, thus, a total of O((n/W ) log−1 n) windows violate this condition. This
is o(1)-fraction.

3. Similarly, since the second moment of the stream is O(n), fix l, at most O(n)
2l W log3 n
= O((n/2l W ) log−3 n)
nodes in level l can violate this condition. At most O((n/W ) log−3 n) windows violate this condition
for each l. Thus, a total of o(1)-fraction windows violate this condition.

21
 Given the claim, we now prove that with Ω(1) probability, the (actual) algorithm will start check(j, v)
for the correct v from some “good” window. Concretely, we prove the following claim.
Claim 5.17. With 1/20 probability, there exists a good window i such that
(j) (j)
• x∗ is in Si , and it is the only element in Si that appears in window i;
• at the end of window i, at most 100 check(j, ·) are still running.

It is easy to verify that when the event in the claim happens, we start check(j, v) for the correct v from
that window, and hence, the lemma holds.
First observe that for each window i, the probability that the first condition holds is at least

q · (1 − q)W ≈ q(1 − 1/C 2 ).

To prove the claim, we need to prove that this happens in a good window and when there are at most
100 other check running. We apply Lemma 5.2, which asserts that at most 1/4 + o(1) of the windows in
expectation can have more than 100 check(j, ·) running. Combined with Claim 6.2, in expectation, at least
1/4 − o(1)-fraction of the windows are simultaneously good and have at most 100 check running. Ideally, we
(j)
would like to argue that in at least one of these (1/4−o(1))n/W windows, we sample x∗ in Si but not other
(1/4−o(1))n/W
elements with constant probability by bounding it by 1 − (1 − q/3) = Ω(1). However, we cannot
bound it in this way, since the set of this 1/4 − o(1)-fraction of windows can depend on the randomness used
(j)
by hash function j (in particular, the sets Si ). To this end, we will prove the following claim by induction,
which implies the bound we aim for.
Let Gi be the random variable indicating the number of windows that are simultaneously good and have
at most 100 check running from window i + 1 to the end. We have E[G0 ] ≥ (1/4 − o(1))n/W . Let Ri be the
(j) (j)
randomness used by the algorithm in window i, i.e., the random sets S1 , . . . , Si , and all the random bits
used by K-SHH in window i.
Claim 5.18. Fix all randomness used by hash functions j ′ ̸= j. Let E be the (bad) event that we don’t have
(j)
a window i that is simultaneously good and have at most 100 check running such that x∗ is in Si , and it is
(j)
the only element in Si that appears in the window. Then we have
q 
Pr[E | h(j) , R≤i ] ≤ γ · E[Gi | h(j) , R≤i ] ,
2
where γ(y) := exp(−y/3 − 5y 2 /9).
As we will use it later, observe that the function γ on the RHS is concave. This is because 21 q · E[Gi |
2
h(j) , R≤i ] ≤ 12 q · n/W ≤ 1/2, and for y ∈ [0, 1/2], the second derivative of γ(y) = e−y/3−5y /9 is ((1/3 +
2
10y/9)2 − 10/9)e−y/3−5y /9 < 0.
Now to see this claim is sufficient for proving Claim 6.3, we set i = 0. We have that
q 
Pr[E | h(j) ] ≤ γ · E[G0 | h(j) ] .
2
Taking expectation over h(j) and using the concavity and monotonicity of γ, we have
h q i
Pr[E] ≤ Eh(j) γ · E[G0 | h(j) ]
q 2 
≤γ · E[G0 ]
 2q 
≤γ · (1/4 − o(1))n/W
2
≤ γ (1/8 − o(1))
≤ exp(−1/24 − 5/576 + o(1))
≤ 19/20.

22
That is, the bad event E happens with probability at most 19/20, we must start check on the correct hash
value v = h(j) (x∗ ) with probability at least 1/20. This implies Claim 6.3.
It remains to prove the claim. We prove by induction on i from i = n/W to 0. The base case is when
i = n/W . The bound trivially holds, since Gi = 0, the RHS is equal to 1. Now suppose the bound holds for
i + 1, and let us consider i. There are two cases: whether window i + 1 is simultaneously good and has at
most 100 check running. Note that this is completely determined by h(j) and R≤i .
• Suppose h(j) and R≤i are such that window i + 1 is either not good or has more than 100 check
running. Then we have Gi+1 = Gi conditioned on h(j) and R≤i . In this case, we have
h i
Pr[E | h(j) , R≤i ] ≤ ERi+1 |h(j) ,R≤i Pr[E | h(j) , R≤i+1 ]
h q i
≤ ERi+1 |h(j) ,R≤i γ · E[Gi+1 | h(j) , R≤i+1 ]
h  2q i
= ERi+1 |h(j) ,R≤i γ · E[Gi | h(j) , R≤i+1 ]
2
which by the concavity, is
q h i
≤γ · ERi+1 |h(j) ,R≤i E[Gi | h(j) , R≤i+1 ]
 2q 
=γ · E[Gi | h(j) , R≤i ] ,
2
proving the bound for i.
• Suppose h(j) and R≤i are such that window i + 1 is good and has at most 100 check running. Then
(j)
Gi+1 = Gi − 1 conditioned on h(j) and R≤i . Note that Ri+1 is such that x∗ ∈ Si+1 and it is the
(j) (j)
only element in window i + 1 that is sampled in Si+1 , then event E does not happen. The set Si+1 is
(j)
independent of hi and R≤i , and hence, it happens with probability at least q(1 − 1/C 2 ) as we argued
(j)
above. Denote by Fi+1 the event that x∗ ∈ Si+1 and it is the only element in window i + 1 that is
(j)
sampled in Si+1 . Thus, we have
h i
Pr[E | h(j) , R≤i ] ≤ ERi+1 |h(j) ,R≤i Pr[E | h(j) , R≤i+1 ]
h q i
≤ ERi+1 |h(j) ,R≤i 1¬Fi+1 · γ · E[Gi+1 | h(j) , R≤i+1 ]
2 h q i
(j)
= Pr[¬Fi+1 | h , R≤i ] · ERi+1 |h(j) ,R≤i ,¬Fi+1 γ · E[Gi+1 | h(j) , R≤i+1 ]
q h2 i
2
≤ (1 − q(1 − 1/C )) · γ · ERi+1 |h(j) ,R≤i ,¬Fi+1 E[Gi+1 | h(j) , R≤i+1 ]
 2q 
2
= (1 − q(1 − 1/C )) · γ · E[Gi+1 | h(j) , R≤i , ¬Fi+1 ]
2
q  2 
≤ e−q(1−1/C ) · γ · E[Gi | h(j) , R≤i , ¬Fi+1 ] − 1 .
2
Again by the fact that Pr[Fi+1 | h(j) , R≤i ] ≈ q(1 − 1/C 2 ) and Gi ∈ [0, n/W ], we have that

E[Gi | h(j) , R≤i , ¬Fi+1 ] ≥ E[Gi | h(j) , R≤i ] − (q(1 − 1/C 2 )) · n/W = E[Gi | h(j) , R≤i ] − (1 − 1/C 2 ).

Hence, by the monotonicity of γ,

2
q  
Pr[E | h(j) , R≤i ] ≤ e−q(1−1/C )
· E[Gi | h(j) , R≤i ] − (1 − 1/C 2 ) − 1
·γ
 2q 
−q(1−1/C 2 )
≤e ·γ · E[Gi | h(j) , R≤i ] − q(1 − 1/2C 2 ) .
2
On the other hand,
q   
γ · E[Gi | h(j) , R≤i ] − q(1 − 1/2C 2 )
2

23
  2 
q q 5 q
= exp − · E[Gi | h(j) , R≤i ] + (1 − 1/2C 2 ) − · E[Gi | h(j) , R≤i ] − q(1 − 1/2C 2 )
6 3 9 2
q   
 q 5
≤γ · E[Gi | h(j) , R≤i ] · exp (1 − 1/2C 2 ) + q · E[Gi | h(j) , R≤i ] · q(1 − 1/2C 2 )
2 3 9
q   
 q 5q
≤γ · E[Gi | h(j) , R≤i ] · exp (1 − 1/2C 2 ) + (1 − 1/2C 2 ) · (qn/W )
2 3 9
q  
(j) 2


≤γ · E[Gi | h , R≤i ] · exp q(1 − 1/C ) .
2
This completes the induction step for the second case, finishing the proof.

Theorem 5.19. The space usage of Algorithm 2 is O(log n) bits. It finds x∗ with probability 1 −
2−Ω(log n/ log log n) .
Proof. It is straightforward to verify that the space usage is O(log n) bits: at most O(J) = O(log n/ log K)
check and K-SHH may be running in parallel, each uses O(log K) bits regularly; at most O(1) instances of
K-SHH may use O(log n) bits at the same time.
Now we lower bound the probability that it finds x∗ . Let Xj indicate if we find vj = h(j) (x∗ ). Lemma 5.15
Xj is at least J/25 = 128
P
implies that E[Xj | X1 , . . . , Xj−1 ] ≥ 1/25. The expectation of 25 log U/ log K.
−Ω(log U/ log K) −Ω(log n/ log log n)
P
Thus, by Theorem 3.7, Pr[ j Xj ≥ 4 log U/ log K] ≥ 1 − 2 =1−2 .
When this happens, x∗ satisfies the last line of Algorithm 2. On the other hand, it is the only such
element with high probability. Consider any x ̸= x∗ that matches 4 log U/ log K hash values recorded. For
each vj it matches, either h(j) (x) = h(j) (x∗ ) or vj ̸= h(j) (x∗ ). The former happens with probability K −1 ,
and in the latter case, it is the hash value found by j with probability O(K −1/2 ) by Lemma 5.15. By union
bounding over the choice of 4 log U/ log K indices j, the probability that this happens is at most
 
J
· O(K −1/2 )4 log U/ log K ≤ O(K −1/2 )4 log U/ log K ≤ 1/U 2−o(1) .
4 log U/ log K

Thus, the probability that there exists a different x ̸= x∗ that also satisfies the last line of the algorithm is
at most 1/U 1−o(1) . This proves the theorem.

6 Streaming algorithm for detecting ℓ2 ϵ-heavy hitters

 
In this section, we present the algorithm for finding ℓ2 ϵ-heavy hitters with high probability using O logϵ n -
bits of space, assuming each ϵ-heavy hitter is evenly distributed in the stream.
 Note that the space is tight
because there could be θ 1ϵ ϵ-heavy hitters and we would need at least O logϵ n -bits of space to output

them. Here again, we assume that the length of the stream is n, the second moment of the frequency vector
is O(C 2 n), and we assume access to free randomness.
The main changes to Algorithm 2 from the previous section are highlighted in red below.

24
Algorithm 4 Algorithm for ℓ2 ϵ-heavy hitters
Input: a stream of length n of elements from set U of size poly n, and a parameter 0 < ϵ ≤ 1 with
ϵ = ω (1/n). p
1: assumptions: for every ϵ-heavy hitter, if we divide the stream into windows of length W := n/ϵ/C,
there is at least one occurrence of it in every window; ℓ22 of the frequency vector is at most C 2 n.
Output: the set of all ϵ-heavy
√
hitters in the stream
ϵ 1000
2: fix parameters q = C √n , K = (log n/ϵ) , and J = 128 log U/ϵ log K
3: let h(1) , . . . , h(J) be independent random hash functions h(j) : U → [K]
(j) (j)
4: for each window i and each j ∈ [J], sample a random set Si ⊆ U such that each x ∈ U is in Si with
probability q independently using free random bits
5: for each window i do
(j)
6: for j ∈ [J], if there is some x ∈ Si that appears in the window, record (j, h(j) (x)) (if there is more
than one such x for some j, record the first one)
7: for each hash (j, v) recorded at the end of the window do
8: if at most 100 instances of check are still running for this j then
9: start check(j, v) in parallel
10: end if
11: end for
12: end for
13: For each j, record the first (j, v) such that check(j, v) returned YES
14: If x such that h(j) (x) = v for at least 4 log U/ log K of them, return x (If there are multiple such x,
return all of them)

The execution forest of Algorithm 4 would be similar to√ the execution forest that we defined in the
previous section for Algorithm 2 with the new maxL = log(C ϵn/8).
Below we describe the algorithm for the check function and highlight the changes from Algorithm 3 in
red. Note the the only changes are in the value of maxL and the maximum number of K-SHH algorithms
that can use log n bits simultaneously.

25
Algorithm 5 check(j, v) checks if h(j) (x∗ ) = v (when x∗ exists)
√
1: let maxL = log(C ϵn/8)
2: for l = 0, . . . , maxL do
3: currently at the beginning of a level-l node I in the execution forest, let it be the beginning of
the i-th window such that 2l | i; the current check must be initiated from a window in the range
[max{0, i − 2l+1 + 1}, i − 2l ]
4: if there is another instance of check with the same j and v is about to start the same round l (hence
on the same I), then keep only one instance and terminate the others
S (j) (j)
5: let UI,j ← k∈[max{0,i−2l+1 +1},i−2l ] Sk be the union of all Sk of windows that may have initiated
this check
6: run K-SHH (Algorithm 1) on I, restricted to elements in UI,j with hash value v (i.e., set the parameter
V to UI,j,v , n is the length of the original stream, and we assume that the universe size is at most poly n,
W and K are fixed parameters that do not vary across the different executions of K-SHH)

UI,j,v := {x : h(j) (x) = v} ∩ UI,j ,

denote this instance of K-SHH by AI,j,v ; at every time-step, we ensure that there are at most
1/ϵ different j’s such that their K-SHH instances use O(log n) bits (and they block AI ′ ,j ′ ,v′
for every other j ′ , i.e., those instances do not proceed after Algorithm 1 in Algorithm 1)
7: if K-SHH returns NO then
8: return NO
9: end if
10: wait until the start of the next window i such that 2l+1 | i
11: end for
12: return YES

Like in the Section 5, in order to analyze the above algorithm, we would need to work with hypothetical
versions of it. Observe that the main changes to the algorithms in the previous section are the setting of
the parameters q, W, K, J, and maxL. In addition, 1/ϵ many K-SHH algorithms are now allowed to use log n
bits in parallel, and Algorithm 4 outputs any element whose hash value passes check in at least 0.5ϵ fraction
of the hash functions. Given this, it can be verified that Lemmas 5.2, 5.8 and 5.13, and the claims within
the lemmas still hold with the new setting of the parameters for the ϵ-heavy hitters.
We now prove a lemma similar to Lemma 5.15 in the previous section.
Lemma 6.1. For each j, for every ϵ-heavy hitter x∗ , conditioned on all the random bits used by j ′ ̸= j, the
probability that we find vj = hj (x∗ ) is at least ϵ/25. On the other hand, we find a hash value v such that
v ̸= hj (x) for any ϵ/256-heavy hitter with probability O(K −1/3 ).

Fix the random bits used by all j ′ ̸= j. This fixes the set of windows blocked by j ′ ̸= j in the hypothetical
algorithm. By Lemma 5.13, at most 1/ log4 n-fraction of the windows are blocked in total. Recall that the
windows blocked by the real algorithm are a subset, the remaining at least (1 − 1/ log4 n)-fraction of the
windows are guaranteed to not be blocked by j ′ ̸= j, regardless of the randomness used by hash function j.
For j fixed, the algorithm records the first (j, v) such that check(j, v) returns YES. We will prove

• for all v such that v ̸= h(j) (y) for any ϵ/256-heavy hitter y, check(j, v) will return YES with probability
O(K −1/3 );
• for every ϵ-heavy hitter x∗ , check(j, v) will be initiated for v = h(j) (x∗ ) and will return YES with
probability Ω(ϵ).

For the first bullet point, consider the √

last round of check, i.e., l = maxL. Consider a node I in level l of the
execution forest, the length of I is 2l = C ϵn/8. Fix v such that v ̸= h(j) (y) for any ϵ/256-heavy hitter y, we
now upper bound the probability that check(j, v) passes the last round on I. First observe √ that any element
in UI,j,v that is not an ϵ/256-heavy hitter has overall frequency that is less than 2l−1 = C ϵn/16. √ Hence, by
Lemma 4.5, this requires at least two elements in UI,j,v with frequency at least 2l · K −1/8 = C ϵnK −1/8 /8.

26
But there can be at most O(K 1/4 /ϵ) elements with this frequency,
 even in the whole stream. The probability
2 
K 1/4
≤ O K −4/3 . In particular, check(j, v)


there exists two of them with hash value v is at most O ϵK

passes the last round on I with probability at most K −4/3 . There are O(1) nodes in the last level, taking a
union bound over v and the nodes in this level, we conclude that the algorithm records a wrong hash value
for j with probability at most O(K −1/3 ). In the remainder of the proof, we will show that we will sample
and start check(j, v) from a “good” window with constant probability, and a check(j, v) that is started from
a “good” window will return YES with constant probability.
Consider a window i, suppose we start check in parallel at the end of this window. Let I0 , I1 , . . . , ImaxL
be the nodes in the execution forest that this check will run K-SHH on, where Il is in level l (in particular,
I0 consists of window i + 1). We say window i is “good” if

1. I0 , . . . , ImaxL exist, i.e., i is not close to the end of the stream,

2. for each l = 0, . . . , maxL, Il has at most 2l log−1 n blocked windows, and
3. for each l = 0, . . . , maxL, the second moment of Il is at most 2l W log3 n, i.e., 2
≤ 2l W log3 n.
P
x fx,Il

Note that the definition of a good window depends on the randomness used when checking other hash
functions j ′ ̸= j (for the second condition), but not the randomness used by j.
For each good window, v = h(j) (x∗ ), and l = 0, . . . , maxL, we have
 
X
E 2 
fx,I l
≤ Pr[x ∈ UIl ,j,v ] · 2l W log3 n ≤ (2l q) · 1/K · 2l W log3 n = 4l log3 n/K.
x∈UIl ,j,v ,x̸=x∗

Therefore, by Markov’s inequality and taking the union bound over all l, we have that with probability at
least 1 − o(1), for every l = 0, . . . , maxL,
X
2
fx,I l
≤ 4l log5 n/K .
x∈UIl ,j,v ,x̸=x∗

Assuming the bound holds, if we start check(j, v) for v = h(j) (x∗ ) from a good window, then for each
round l, K-SHH returns YES with probability 1 − 1/poly n by Lemma 4.4. Taking a union bound over all
levels, check returns YES except with o(1) probability. It remains to show that we will start such a check
with constant probability.
We show that at least a constant fraction of the windows are good.
Claim 6.2. With probability 1 − 1/poly n, at least 1/2 − o(1) fraction of the windows are good.

To see this, we analyze the fraction of windows that is not good due to the violation of each of the
conditions above.
√
1. Note that 2maxL = C ϵn/8 = n/8W . As long as i + 4 · 2maxL ≤ n/W , i.e., i ≤ n/2W , I0 , . . . , ImaxL
exist. At most half of the windows violate this condition.
′
2. By applying Lemma 5.13
−3

and taking the sum over all hash functions j ̸= j, we observe that at
most O (n/W ) · log n windows are blocked with probability 1 − 1/poly n. For a fixed l, at most
O((n/W )·log−3 n)
= O (n/2l W ) log−2 n nodes in level l can violate the condition. For each such node,


2l log−1 n
there are exactly 2l windows i that could lead to this node in level l. At most O((n/W ) log−2 n) windows
violate this condition for each l, thus, a total of O((n/W ) log−1 n) windows violate this condition. This
is o(1)-fraction.

3. Similarly, since the second moment of the stream is O(n), fix l, at most O(n)
2l W log3 n
= O((n/2l W ) log−3 n)
−3
nodes in level l can violate this condition. At most O((n/W ) log n) windows violate this condition
for each l. Thus, a total of o(1)-fraction windows violate this condition.

27
Given the claim, we now prove that with Ω(1) probability, the (actual) algorithm will start check(j, v) for
the correct v from some “good” window. Concretely, we prove the following claim.
Claim 6.3. With ϵ/25 probability, there exists a good window i such that
(j) (j)
• x∗ is in Si , and it is the only element in Si that appears in window i;
• at the end of window i, at most 100 check(j, ·) are still running.
It is easy to verify that when the event in the claim happens, we start check(j, v) for the correct v from
that window, and hence, the lemma holds.
To prove the claim, we need to prove that this happens in a good window and when there are at most
100 other check running. We apply Lemma 5.2, which asserts that at most 1/4 + o(1) of the windows in
expectation can have more than 100 check(j, ·) running. Combined with Claim 6.2, in expectation, at least
1/4 − o(1)-fraction of the windows are simultaneously good and have at most 100 check running. Like in
Section 5, we will prove the following claim by induction, which implies the bound we aim for.
Let Gi be the random variable indicating the number of windows that are simultaneously good and have
at most 100 check running from window i + 1 to the end. We have E[G0 ] ≥ (1/4 − o(1))n/W . Let Ri be the
(j) (j)
randomness used by the algorithm in window i, i.e., the random sets S1 , . . . , Si , and all the random bits
used by K-SHH in window i.
Claim 6.4. Fix all randomness used by hash functions j ′ ̸= j. Let E be the (bad) event that we don’t have
(j)
a window i that is simultaneously good and have at most 100 check running such that x∗ is in Si , and it is
(j)
the only element in Si that appears in the window. Then we have
q 
Pr[E | h(j) , R≤i ] ≤ γ · E[Gi | h(j) , R≤i ] ,
2
where γ(y) := exp(−y/3 − 5y 2 /9).
The claim above is the exact same claim that we proved in Section 5. And as we observed earlier, the
function γ on the RHS is concave.
By setting i = 0. We have that
q 
Pr[E | h(j) ] ≤ γ · E[G0 | h(j) ] .
2
Taking expectation over h(j) and using the concavity and monotonicity of γ, we have
h q i
Pr[E] ≤ Eh(j) γ · E[G0 | h(j) ]
q 2 
≤γ · E[G0 ]
 2q 
≤γ · (1/4 − o(1))n/W
2
≤ γ (ϵ(1/8 − o(1)))
≤ exp(−ϵ/25 − ϵ2 /64)
≤ 1 − ϵ/25 .

That is, the bad event E happens with probability at most 1 − ϵ/25, we must start check on the correct hash
value v = h(j) (x∗ ) with probability at least ϵ/25. This implies Claim 6.3.
We finally analyze the space usage and correctness of Algorithm 4.

Theorem 6.5. The space usage of Algorithm 4 is O(log n/ϵ) bits. It finds all the ϵ-heavy hitters with
probability 1 − 2−Ω(log n/(log log n−log ϵ)) /ϵ9 and it outputs an element that is not an ϵ/256-heavy hitter with

probability at most 1/U 1−o(1) .

 
9 This probability is at least a constant for ϵ = Ω √1 .
2 log n

28
Proof. It is straightforward to verify that the space usage is O(log n/ϵ) bits: at most O(J) = O(log n/ϵ log K)
check and K-SHH may be running in parallel, each uses O(log K) bits regularly; at most O(1/ϵ) instances
of K-SHH may use O(log n) bits at the same time.
Now we lower bound the probability that it finds the correct set of ϵ-heavy hitters. Consider an ϵ-heavy
hitter x∗ . Let Xj indicate (j) ∗
Pif we find vj = h (x ).128Lemma 5.15 implies that E[Xj | X1 , . . . ,P Xj−1 ] ≥
ϵ/25. The expectation of Xj is at least ϵJ/25 = 25 log U/ log K. Thus, by Theorem 3.7, Pr[ j Xj ≥
4 log U/ log K] ≥ 1 − 2−Ω(log U/ log K) = 1 − 2−Ω(log n/(log log n−log ϵ)) . When this happens, x∗ satisfies the last
line of Algorithm 2. Taking the union bound over at most 1/ϵ many ϵ-heavy hitters, we get the desired
bound.
On the other hand, consider any x that is not an ϵ/256-heavy hitter that matches 4 log U/ log K hash
values recorded. For each vj it matches, either h(j) (x) = h(j) (x∗ ) for some ϵ/256-heavy hitter x∗ or vj ̸=
h(j) (x∗ ) for any ϵ/256-heavy hitter x∗ . The former happens with probability O((ϵK)−1 ), and in the latter
case, it is the hash value found by j with probability O(K −1/3 ) by Lemma 5.15. By union bounding over
the choice of 4 log U/ log K indices j, the probability that this happens is at most
 
J
· O(K −1/3 )4 log U/ log K ≤ O(K −1/3 )4 log U/ log K ≤ 1/U 2−o(1) .
4 log U/ log K

Thus, the probability that there exists an element that is not an ϵ-heavy hitter that also satisfies the last
line of the algorithm is at most 1/U 1−o(1) . This proves the theorem.

6.1 Proof of Theorem 1.4

Algorithm 4 assumed that both the length of the stream and the second moment are known in advance. It
also assumed that the heavy hitters are evenly distributed in the stream. We first show how to remove the
assumption that the heavy hitters are evenly distributed in the stream. We claim the following regarding
the distribution of heavy hitters in partially random order streams.
Claim 6.6. For each ϵ-heavy hitter, every L consecutive windows have at least 2L/3 occurrences of this
heavy hitter with probability 1 − 2 exp(−L/18).
Before we prove the claim, let us see how we can modify our algorithm based on this claim. We first
modify Algorithm 1 so that it searches for an element that occurs in many windows instead of all windows.
For L ≥ K 3/16 , we modify Algorithm 1 in the K-SHH algorithm (Algorithm 1) to look for an occurrence of
the sampled element y in every 90 log n windows, rather than every window, and do this check in the next
90 log nL/K 1/8 windows. Note that this increases the total number of windows using log n bits in Lemmas 4.1
to 4.3 only by an O(log n) factor, which does not affect how these lemmas are applied in Sections 5 and 6,
since K is a large polynomial in log n. It is also easy to see that we get the same success probability in
the YES case (Lemma 4.4) because of Claim 6.6 (and the fact that L ≫ log n). There is no change in the
analysis of the NO case (Lemma 4.5).
For L < K 3/16 , we use a similar algorithm as before, where we hash every element in V using a uniform
O(log K) bit hash function and return YES if there are at least 2L/3 elements in the substream restricted to
V and all their hash values are equal, else return NO. We will now argue that Lemmas 4.1 to 4.3 and 4.5 hold
in this case, and Lemma 4.4 holds after changing the premise to an x∗ occurring in 2L/3 of the windows.
Observer that Lemmas 4.1 to 4.3 hold trivially because the algorithmP never uses more than O(log K) bits.
In the YES case corresponding to Lemma 4.4, the condition that y̸=x∗ ∈V fy2 ≤ L2 log5 n/K implies that
there is no element other than x∗ in the substream restricted to V . Therefore, the algorithm outputs YES
in this case. On the other hand, consider the NO case. If the substream restricted to V has fewer than
2L/3 elements, then the algorithm always outputs NO. If the substream has at least 2L/3 elements, then
the conditions in the NO case imply that there are at least K 1/8 /6 distinct elements in the substream. The
probability that they all have the same hash value is at most 1/poly n.
To accommodate for the new premise of Lemma 4.4, we will need to update the proof of Lemmas 5.15
and 6.1, which are the only places we used Lemma 4.4. We change the definition of a “good” window to
further require for each l ≥ 10, the node Il has at least 2l+1 /3 occurrences of the heavy hitter x∗ . By
Claim 6.6, all but an 2 exp(−50)-fraction of the windows satisfy this extra condition. Next, we modify the

29
algorithm so that it starts from iteration l = 10. We also increase the number of check allowed at the
same time by a factor of 210 . The proofs still go through with a slightly smaller constant fraction of good
windows. The correctness of Algorithms 2 and 4 still hold and the space usage is also unaffected. We now
prove Claim 6.6.
√
Proof of Claim 6.6. Fix an ϵ-heavy hitter x∗ . By definition, the frequency of x∗ is at least C ϵn and the
positions of its occurrences are marginally uniform in the stream. Equivalently, we can view the distributions
of its occurrences in the stream as sampling at least k = n/W balls from n bins without replacement, where
n is the length of the stream and W is the length of the window we chose in Algorithm 4. Let L ≤ n/W
and j ∈ [0, n/W − L]. Let XL,j denote the number of occurrences of x∗ in windows ranging from j + 1 to
j + L. Applying Theorem 3.8 with ℓ = LW and i = jW , we get that

Pr[XL,j < 2L/3] ≤ 2 exp(−ℓk/18n) ≤ 2 exp(−L/18) .

This proves the claim.

We now show how to remove the assumption about the length of the stream. It is not hard to show
that if we replace n with ñ ∈ [0.9n, 1.1n] and if Algorithm 4 executes only on a 0.9 fraction of the stream,
the analysis still works. So, we guess the value of n in increasing powers of (1.1), i.e., (1.1), (1.1)2 , . . . , and
ensure that whenever we guess the correct value of n, at least a 0.9 fraction of the stream is still left. At
each time step, the algorithm maintains 25 possible guesses for n in increasing order (1.1)i , . . . , (1.1)i+24 and
maintains a counter len to measure the current length of the stream. At the beginning of the stream, i is
set to be 0, and we start executing Algorithm 4 in parallel for each of these guesses. Whenever len reaches
(1.1)i + 1, we discard the first guess, along with its corresponding execution of Algorithm 4, and we add a
new guess (1.1)i+25 and begin executing an instance of Algorithm 4 for this guess, starting from this point in
the stream. At the end of the stream we choose the guess (1.1)i such that (1.1)i−1 < n ≤ (1.1)i and output
whatever the Algorithm 4 corresponding to this guess outputs and discard the rest. Note that the length
ñ of the stream guessed for this instance of Algorithm 4 lies in the range [0.9n, 1.1n], where n is the true
length of the stream. In addition, at the point where the guess (1.1)i is added, at most (1.1)i−25 elements
in the stream have been seen. Hence, for the correct guess, Algorithm 4 would have executed on at least
a 1 − (1.1)−25 > 0.9 fraction of the remaining portion of the stream, and hence, we would get the same
guarantees as in Theorem 6.5. Finally, we note that this meta algorithm has the same space complexity as
Algorithm 4.

6.2 Proof of Theorem 1.3

Finally, we prove our result for random order streams. In this case, we can get rid of the assumption that
the ℓ2 norm of the stream is known in advance to the algorithm. To do this, we use an ℓ2 norm tracking
algorithm due to Braverman, Chestnut, Ivkin, Wang, and Woodruff [21].
Theorem 6.7 (ℓ2 norm tracking [21]). Let 0 < ϵ < 1. There is a streaming algorithm that outputs at each
(t) (t) (t)
time t, a value F̂2 such that Pr[|F̂2 − F2 | ≤ ϵF2 , for all 0 ≤ t ≤ n] ≥ 1 − δ, where F2 denotes the squared
(t)
norm of the stream and F2
denotes the squared norm at time t. The algorithm uses O ϵ12 log 1δ log n bits

of space and has O ϵ12 log 1δ update time.

Setting ϵ = δ = 0.01, we get that with probability at least 99/100, for all 0 ≤ t ≤ n, it is possible to
(t) (t) (t)
output F̂2 such that |F̂2 − F2 | ≤ 0.01F2 , using O(log n) space. We now modify Algorithm 4 as follows.
It is again not hard to show that if we set the window size W based on F˜2 ∈ [0.9F2 , 1.12F2 ], a constant
factor approximation to F2 , and execute Algorithm 4 on a constant fraction of the stream, the analysis still
works. So, we maintain a constant number of guesses for the value of F2 in increasing powers of (1.1), i.e.,
(1.1), (1.1)2 , . . . , and ensure that whenever we guess the correct value of F2 , at least a constant fraction of the
stream is still left. At each time step, the algorithm maintains 25 possible guesses for F2 in increasing order
(1.1)i , . . . , (1.1)i+24 and simultaneously runs the F2 tracking algorithm from Theorem 6.7. At the beginning
of the stream, i is set to be 0, and we start executing Algorithm 4 in parallel for each of these guesses. At each
(t)
time step t, successively remove every guess (1.1)i that is smaller than F̂2 , and add a corresponding new

30
guess (1.1)i+25 , and begin executing an instance of Algorithm 4 for this guess, starting from this point in the
(n)
stream. At the end of the stream, we choose the guess (1.1)i such that (1.1)i−1 < F̂2 ≤ (1.1)i and output
whatever the Algorithm 4 corresponding to this guess outputs and discard the rest. It is not hard to see that
this meta algorithm still has the same space complexity as Algorithm 4. We will now argue its correctness.
(n)
By the setting of ϵ, we have 0.99F2 ≤ F̂2 ≤ 1.01F2 . It follows that F̃2 = (1.1)i ∈ [0.9F2 , 1.12F2 ]. Let t∗ be
(t∗ −1)
the timestep where the guess (1.1)i was added. Observe that F̂2 ≤ (1.1)i−25 since the guess (1.1)i−25
∗
(t −1) (t∗ −1)
was discarded only at time t∗ . Therefore, F̂2 ≤ 0.12F2 and hence, F2 ≤ 0.13F2 . It follows from
√ (t) (t)
Claim 6.8 that with probability at least 1−O(1/ n), for t = 0.4n, F √2 ≥ 0.15F 2 . Since F2 is monotonically
∗
increasing in t, we conclude that with probability at least 1 − O(1/ n), t ≤ 0.4n. This completes the proof.
Claim 6.8. For every t ≤ n, we have

(t) F2 t(t − 1) t(n − t)

E[F2 ] = + ,
n(n − 1) n−1
√ (t) (t)
and with probability at least 1 − O(1/ n), |F2 − E[F2 ]| ≤ 0.01F2 .
Proof. Consider a random order stream defined by a multiset S of n elements and a uniform bijective function
Π : S → [n] that maps every element in S to a unique position in the stream. Assume an arbitrary ordering
on the elements of S. For i ∈ [n], let S(i) denote the i-th element in S. Define J(i) := Π(S(i)). Dubhashi,
Priebe, and Ranjan proved in [29, Theorem 10] that the permutation random variables (Ji : i ∈ [n]) are
negatively associated (see Definition 3.9). For every x ∈ S, define the index set Ix := {i ∈ [n] : S(i) = x}.
Observe that the index sets are mutually disjoint for distinct elements, and for every x ∈ S and t ≤ n,
Yx := ( i∈Ix 1[Ji ≤ t])2 is a non-increasing function. Therefore, we can apply Item 3 of Proposition 3.12 to
(t) P

= 1[Ji ≤ t]).
(t) (t)
conclude that the random variables (Yx : x ∈ S) are negatively associated for every t. Let Zi
We have
(t) (t) (t)
X X
E[Yx(t) ] = E[Zi ] + E[Zi1 Zi2 ]
i∈Ix i1 ̸=i2 ∈Ix
tfx t(t − 1)
= + fx (fx − 1)
n n(n − 1)
(fx )2 t(t − 1) fx t(n − t)
= + .
n(n − 1) n(n − 1)

Therefore,
(t)
X F2 t(t − 1) t(n − t)
E[F2 ] = E[Yx(t) ] = + .
x
n(n − 1) n−1
(t) (t) (t) P (t)
It follows from Definition 3.9 that for x ̸= y, cov(Yx , Yy ) ≤ 0. Therefore, var(F2 ) ≤ x var(Yx ). We
have
X (t)
E[(Yx(t) )2 ] = E[( Zi )2 ]
i∈Ix
(t) (t) (t) (t) (t) (t) (t) (t) (t) (t)
X X X X
= E[Zi ] + 14 E[Zi1 Zi2 ] + 36 E[Zi1 Zi2 Zi3 ] + 24 E[Zi1 Zi2 Zi3 Zi4 ]
i∈Ix i1 <i2 ∈Ix i1 <i2 <i3 ∈Ix i1 <i2 <i3 <i4 ∈Ix
tfx t(t − 1)
= + 7fx (fx − 1)
n n(n − 1)
t(t − 1)(t − 2) t(t − 1)(t − 2)(t − 3)
+ 6fx (fx − 1)(fx − 2) + fx (fx − 1)(fx − 2)(fx − 3) .
n(n − 1)(n − 2) n(n − 1)(n − 2)(n − 3)

Therefore,

t(t − 1)(n − t)(4tn − 6) 2t(t − 1)(n − t)(2tn2 + 2tn − 6n2 + 6n − 6t)

var(Yx(t) ) = −fx4 2 2
+ fx3
n (n − 1) (n − 2)(n − 3) n2 (n − 1)2 (n − 2)(n − 3)

31
 t2 (n − t)2
 
7t(t − 1) 18t(t − 1)(t − 2) 11t(t − 1)(t − 2)(t − 3)
+ fx2 − + − 2
n(n − 1) n(n − 1)(n − 2) n(n − 1)(n − 2)(n − 3) n (n − 1)2
 
t 7t(t − 1) 12t(t − 1)(t − 2) 6t(t − 1)(t − 2)(t − 3)
+ fx − + −
n (n − 1)(n − 2) n(n − 1)(n − 2) n(n − 1)(n − 2)(n − 3)
≤ 3fx3 .
(t)
fx3 . By applying Chebyshev’s inequality (Theorem 3.4), we
P
It follows that var(F2 ) ≤ 3F3 , where F3 = x
conclude that
√
 
(t) (t) F3
Pr[|F2 − E[F2 ]| > 0.01F2 ] ≤ O 2 ≤ O(1/ n) .
F2
2
√
The last inequality is true because F3 ≤ 2F2 / n. We have
X X
F3 = fx3 + fx3
√ √
x:fx < n x:fx ≥ n
√ X √ X
≤ n fx2 + (1/ n) fx4 .
√ √
x:fx < n x:fx ≥ n

We consider two cases.

√
• Say x:fx <√n fx2 ≥ n/2, then x:fx <√n fx2 ≤ 2( x:fx <√n fx2 )2 /n. It follows that F3 ≤ 2F22 / n.
P P P

• Else if x:fx <√n fx2 < n/2, then x:fx <√n fx2 < x:fx ≥√n fx2 , since x fx2 ≥ n. Therefore,
P P P P

X √ X √ X X
fx3 ≤ n fx2 ≤ n fx2 ≤ fx3 .
√ √ √ √
x:fx < n x:fx < n x:fx ≥ n x:fx ≥ n
√
It follows that F3 ≤ 2F22 / n.

Acknowledgment
We thank Uma Girish for her contributions in the early stages of this project. S.V. is supported in part
by NSF award CCF 2348475. Part of the work was conducted when S.V. was visiting the Simons Institute
for the Theory of Computing as a research fellow in the Sublinear Algorithms program. Part of the work
was conducted when S.V. was a graduate student at Harvard University, and supported in part by a Google
Ph.D. Fellowship, a Simons Investigator Award to Madhu Sudan, and NSF Award CCF 2152413. Part of the
work was conducted when S.V. was visiting Princeton Univeristy as an exchange student under the IvyPlus
Exchange Scholar program. Huacheng Yu is supported in part by NSF CAREER award CCF-2339942.

References
[1] 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, Baltimore, MD, USA, May 22-24,
2005. Ed. by Harold N. Gabow and Ronald Fagin. ACM, 2005, pp. 202–208. doi: 10.1145/1060590.1060621.
url: [Link]
[2] Amit Chakrabarti, Graham Cormode, and Andrew McGregor. “A near-optimal algorithm for estimating the
entropy of a stream”. In: ACM Trans. Algorithms 6.3 (2010), 51:1–51:21. doi: 10.1145/1798596.1798604. url:
[Link]
[3] Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. “Sketching and Streaming Entropy via Approxima-
tion Theory”. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadel-
phia, PA, USA, October 25-28, 2008. IEEE Computer Society, 2008, pp. 489–498. doi: 10.1109/FOCS.2008.76.
url: [Link]

32
 [4] 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 2010, Austin,
Texas, USA, January 17-19, 2010. Ed. by Moses Charikar. SIAM, 2010, pp. 1143–1160. doi: 10 . 1137 / 1 .
9781611973075.92. url: [Link]
[5] Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, and Amir Zandieh. “Hy-
perAttention: Long-context Attention in Near-Linear Time”. In: The Twelfth International Conference on
Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. [Link], 2024. url: https:
//[Link]/forum?id=Eh0Od2BJIM.
[6] Robert S. Boyer and J. Strother Moore. “MJRTY—A Fast Majority Vote Algorithm”. In: Automated Reasoning:
Essays in Honor of Woody Bledsoe. Appeared as Technical Report ICSCA-CMP-32, Institute for Computer
Science, University of Texas in 1981. Dordrecht: Springer Netherlands, 1991, pp. 105–117. isbn: 978-94-011-
3488-0. doi: 10.1007/978-94-011-3488-0_5. url: [Link]
[7] Shiyuan Feng, William Swartworth, and David P. Woodruff. “Tight Bounds for Heavy-Hitters and Moment
Estimation in the Sliding Window Model”. In: 52nd International Colloquium on Automata, Languages, and
Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark. Ed. by Keren Censor-Hillel, Fabrizio Grandoni,
Joël Ouaknine, and Gabriele Puppis. Vol. 334. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025,
75:1–75:19. doi: 10.4230/[Link].2025.75. url: [Link]
[8] Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, and Zhewei Wei. “Simple and Optimal Algorithms for Heavy
Hitters and Frequency Moments in Distributed Models”. In: Proceedings of the 57th Annual ACM Symposium
on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025. Ed. by Michal Koucký and Nikhil
Bansal. ACM, 2025, pp. 371–382. doi: 10.1145/3717823.3718199. url: [Link]
3718199.
[9] Liang Zheng, Qingjun Xiao, and Xuyuan Cai. “A Universal Sketch for Estimating Heavy Hitters and Per-
Element Frequency Moments in Data Streams with Bounded Deletions”. In: Proc. ACM Manag. Data 2.6
(2024), 224:1–224:28. doi: 10.1145/3698799. url: [Link]
[10] Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, and Zhengyi Zhou. “Differentially Private
Hierarchical Heavy Hitters”. In: Proc. ACM Manag. Data 2.5 (2024), 208:1–208:25. doi: 10.1145/3695826.
url: [Link]
[11] Rana Shahout and Michael Mitzenmacher. “Learning-Based Heavy Hitters and Flow Frequency Estimation
in Streams”. In: 32nd IEEE International Conference on Network Protocols, ICNP 2024, Charleroi, Belgium,
October 28-31, 2024. IEEE, 2024, pp. 1–13. doi: 10.1109/ICNP61940.2024.10858542. url: [Link]
10.1109/ICNP61940.2024.10858542.
[12] Qingjun Xiao, Xuyuan Cai, Yifei Qin, Zhiying Tang, Shigang Chen, and Yu Liu. “Universal and Accurate
Sketch for Estimating Heavy Hitters and Moments in Data Streams”. In: IEEE/ACM Trans. Netw. 31.5 (2023),
pp. 1919–1934. doi: 10.1109/TNET.2022.3216025. url: [Link]
[13] Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. “Differentially Private $L 2$-Heavy
Hitters in the Sliding Window Model”. In: The Eleventh International Conference on Learning Representations,
ICLR 2023, Kigali, Rwanda, May 1-5, 2023. [Link], 2023. url: [Link]
id=3UHoYrglYkG.
[14] Christian Janos Lebeda and Jakub Tetek. “Better Differentially Private Approximate Histograms and Heavy
Hitters using the Misra-Gries Sketch”. In: SIGMOD Rec. 53.1 (2024), pp. 7–14. doi: 10.1145/3665252.3665255.
url: [Link]
[15] Jayadev Misra and David Gries. “Finding Repeated Elements”. In: Sci. Comput. Program. 2.2 (1982), pp. 143–
152. doi: 10.1016/0167-6423(82)90012-0. url: [Link]
[16] Graham Cormode and S. Muthukrishnan. “An improved data stream summary: the count-min sketch and
its applications”. In: J. Algorithms 55.1 (2005), pp. 58–75. doi: 10 . 1016 / J . JALGOR . 2003 . 12 . 001. url:
[Link]
[17] Hossein Jowhari, Mert Saglam, and Gá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 2011, June 12-16, 2011, Athens, Greece. Ed. by Maurizio Lenzerini and Thomas
Schwentick. ACM, 2011, pp. 49–58. doi: 10 . 1145 / 1989284 . 1989289. url: https : / / doi . org / 10 . 1145 /
1989284.1989289.
[18] Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. “Finding frequent items in data streams”. In:
Theor. Comput. Sci. 312.1 (2004), pp. 3–15. doi: 10.1016/S0304-3975(03)00400-6. url: [Link]
10.1016/S0304-3975(03)00400-6.

33
[19] Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. “Lower Bounds for Sparse Recovery”. In:
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin,
Texas, USA, January 17-19, 2010. Ed. by Moses Charikar. SIAM, 2010, pp. 1190–1197. doi: 10 . 1137 / 1 .
9781611973075.95. url: [Link]
[20] 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 SIGACT Symposium on Theory of
Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. Ed. by Daniel Wichs and Yishay Mansour.
ACM, 2016, pp. 740–753. doi: 10.1145/2897518.2897558. url: [Link]
[21] Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff.
“BPTree: An 2 Heavy Hitters Algorithm Using Constant Memory”. In: Proceedings of the 36th ACM SIGMOD-
SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19,
2017. Ed. by Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts. ACM, 2017, pp. 361–376. doi:
10.1145/3034786.3034798. url: [Link]
[22] Mark Braverman and Or Zamir. “Optimality of Frequency Moment Estimation”. In: Proceedings of the 57th
Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025. Ed. by
Michal Koucký and Nikhil Bansal. ACM, 2025, pp. 360–370. doi: 10.1145/3717823.3718171. url: https:
//[Link]/10.1145/3717823.3718171.
[23] Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. “Revisiting Frequency Moment
Estimation in Random Order Streams”. In: 45th International Colloquium on Automata, Languages, and Pro-
gramming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. Ed. by Ioannis Chatzigiannakis, Christos
Kaklamanis, Dániel Marx, and Donald Sannella. Vol. 107. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für In-
formatik, 2018, 25:1–25:14. doi: 10.4230/[Link].2018.25. url: [Link]
ICALP.2018.25.
[24] Sudipto Guha and Andrew McGregor. “Stream Order and Order Statistics: Quantile Estimation in Random-
Order Streams”. In: SIAM J. Comput. 38.5 (2009), pp. 2044–2059. doi: 10 . 1137 / 07069328X. url: https :
//[Link]/10.1137/07069328X.
[25] Alexandr Andoni, Andrew McGregor, Krzysztof Onak, and Rina Panigrahy. “Better Bounds for Frequency
Moments in Random-Order Streams”. In: CoRR abs/0808.2222 (2008). arXiv: 0808 . 2222. url: http : / /
[Link]/abs/0808.2222.
[26] Ashish Chiplunkar, John Kallaugher, Michael Kapralov, and Eric Price. “Factorial Lower Bounds for (Almost)
Random Order Streams”. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022,
Denver, CO, USA, October 31 - November 3, 2022. IEEE, 2022, pp. 486–497. doi: 10.1109/FOCS54457.2022.
00053. url: [Link]
[27] Michael Kapralov and Dmitry Krachun. “An optimal space lower bound for approximating MAX-CUT”. In:
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ,
USA, June 23-26, 2019. Ed. by Moses Charikar and Edith Cohen. ACM, 2019, pp. 277–288. doi: 10.1145/
3313276.3316364. url: [Link]
[28] Devdatt Dubhashi and Desh Ranjan. “Balls and bins: a study in negative dependence”. In: Random Struct.
Algorithms 13.2 (Sept. 1998), 99–124. issn: 1042-9832.
[29] Devdatt P. Dubhashi, Volker Priebe, and Desh Ranjan. “Negative Dependence Through the FKG Inequality”.
In: BRICS Report Series 3.27 (1996). doi: 10 . 7146 / brics . v3i27 . 20008. url: https : / / tidsskrift . dk /
brics/article/view/20008.

34