Revisiting Frequency Moment Estimation in Random
Order Streams

arXiv:1803.02270v1 [] 6 Mar 2018

Vladimir Braverman∗,
Johns Hopkins University

Emanuele Viola†,
Northeastern University

David Woodruff‡,
Carnegie Mellon University

Lin F. Yang§
Princeton University

March 6, 2018

Abstract
We revisit one of the classic problems in the data stream literature, namely, that
of estimating the frequency moments Fp for 0 < p < 2 of an underlying n-dimensional
vector presented as a sequence of additive updates in a stream. It is well-known
that using p-stable distributions one can approximate any of these moments up to
a multiplicative (1 + )-factor using O(−2 log n) bits of space, and this space bound
is optimal up to a constant factor in the turnstile streaming model. We show that
surprisingly, if one instead considers the popular random-order model of insertion-only
streams, in which the updates to the underlying vector arrive in a random order, then
e −2 + log n) bits of space, where the
one can beat this space bound and achieve O(
e hides poly(log(1/) + log log n) factors. If −2 ≈ log n, this represents a roughly
O
quadratic improvement in the space achievable in turnstile streams. Our algorithm is
in fact deterministic, and we show our space bound is optimal up to poly(log(1/) +
log log n) factors for deterministic algorithms in the random order model. We also
obtain a similar improvement in space for p = 2 whenever F2 & log n · F1 .

1

Introduction

Analyzing massive datasets has become an increasingly challenging problem. Data sets, such
as sensor networks, stock data, web/network traffic, and database transactions, are collected
at a tremendous pace. Traditional algorithms that store an entire dataset in memory are
∗

vova@cs.jhu.edu
viola@ccs.neu.edu
‡
dwoodruf@cs.cmu.edu
§
lin.yang@princeton.edu. Work done while the author was at Johns Hopkins University
†

1

impractical. The streaming model has emerged as an important model for coping with
massive datasets. Streaming algorithms are typically randomized and approximate, making
a single pass over the data and using only a small amount of memory.
A well-studied problem in the streaming model is that of estimating the frequency moments of an underlying vector. Formally, in an insertion-only stream, the algorithm is presented with a sequence of integers ha1 , a2 , . . . , am i from a universe [n]. A turnstile stream is
defined similarly except integers may also be P
removed from the stream. The p-th frequency
moment of the stream is defined to be Fp = i∈[n] fip , where fi is number of times integer
i occurs in the stream, i.e., its frequency. The quantity Fp is a basic, yet very important
statistic of a dataset (e.g. [AGMS99]). For example, interpreting 00 as 0, F0 is equal to
the number of distinct items in the stream. F2 measures the variance and can be used to
estimate the size of a self-join in database applications. It also coincides with the (squared)
Euclidean norm of a vector and has application in geometric and linear algebraic problems on
streams. For other non-integer p > 0, Fp can serve as a measure of the entropy or skewness
of a dataset, which can be useful for query optimization.
In their seminal paper, Alon, Matias & Szegedy [AMS96] introduced the study of frequency moments in the streaming model. Nearly two decades of research have been devoted
to the space and time complexity of this problem. An incomplete list of papers on frequency
moments includes [Ind00, CKS03, Woo04, IW05, BO10, KNPW11, And12], and [BKSV14];
please also see the references therein. In the turnstile model, Θ(−2 log(mn)) bits of space is
necessary and sufficient for a randomized one-pass streaming algorithm to obtain a (1 ± )approximation to Fp for 0 < p ≤ 2 [KNW10]. Here, by (1 ± )-approximation, we mean that
the algorithm outputs a number Fep for which (1 − )Fp ≤ Fep ≤ (1 + )Fp . For larger values
of p, i.e., p > 2, the memory required becomes polynomial in n rather than logarithmic
[CKS03, IW05].
In this paper, we study the frequency moment estimation problem in the random-order
model, which is a special case of insertion streams in which the elements in the stream occur
in a uniformly random order and the algorithm sees the items in one pass over this random
order. This model was initially studied by Munro and Paterson [MP80], which was one of
the initial papers on data streams in the theory community. Random-order streams occur
in many real-world applications and are studied in, e.g., [DLOM02, CJP08, GH09] and the
references therein. It has been shown that there is a considerable difference between random
order streams and general arbitrary order insertion streams for problems such as quantile
estimation [CJP08, GM09]. For other problems, such as frequency moments for p > 2, the
dependence on n in the space complexity is roughly the same in random and general arbitrary
order streams [GH09]. Notice that [CMVW16] studies the frequency moments problem of
stochastic streams, in which data points are generated from some distribution. That model
is different from ours, but when conditioning on the realizations of the values of each point,
the stream is exactly in random order. Therefore, our analysis is applicable to that model
as well.
However, there is a gap in our understanding for the important problem of Fp -estimation,
0 < p ≤ 2, in the random order model. On the one hand there is an Ω(−2 ) bits of space lower
2

bound [CCM08]. On the other hand, the best upper bound we have is the same as the best
upper bound in the turnstile model, namely O(−2 log n) bits [AMS96, KNW10, KNPW11].
In practice it would be desirable to obtain O(−2 + log n) bits rather than O(−2 log n) bits,
since if  is very small this can lead to considerable savings. For example, if −2 ≈ log n, it
would represent a roughly quadratic improvement. The goal of this work is to close this gap
in our understanding of the memory required for Fp -estimation, 0 < p ≤ 2, in the random
order model.

1.1

Our Contribution

In this paper, we make considerable progress on understanding the space complexity of Fp
with 0 < p ≤ 2, in random order streams. Specifically,
• for F2 , we show that there exists a simple, and in fact deterministic, one-pass algorithm
using space O(−2 +log n) bits to output a (1±) approximation, provided F2 ≥ m·log n,
• for Fp with p ∈ (0, 2)\{1}, we obtain a one-pass deterministic algorithm to obtain a
e −2 + log n) bits of space. We also show that this space
(1 ± ) approximation using O(
complexity is optimal for deterministic algorithms in the random order model, up to
log(1/) + log log n factors. Note that for the case p = 1, Fp is the length of the stream,
which can be computed in O(log n) bits of memory.

1.2

Our Techniques

For F2 , we partition the stream updates into a sequence of small blocks for which each block
can be stored using O(−2 ) bits. We then construct an unbiased estimator by counting the
number of “pairs” of updates that belong to the same universe item. The counting can be
done exactly and with only O(log n) bits of space in each small block. We further show
that if F2 ≥ log n · F1 , we can obtain the desired concentration by averaging the counts over
all blocks. The analysis of the concentration is by constructing a Doob martingale over the
pairs and applying Bernstein’s inequality.
For Fp with 0 < p < 2 our algorithm is considerably more involved. We first develop a
new reduction from estimating Fp to finding `p heavy hitters (a heavy hitter is an item with
1/p
frequency comparable to Fp ). In the rest of this section, we illustrate the high level ideas for
obtaining a constant factor approximation to Fp . Let v = (f1 , f2 , . . . , fn ) be the frequency
vector of the items. Our reduction is to apply a scaling Xi to each fi , where each Xi is
pairwise independently drawn from some distribution. We argue that finding the leading `p
heavy hitter of the scaled frequency vector (denoted as Xi∗ fi∗ ) gives a good estimation to
the Fp of the original stream. The distribution of Xi is a so-called p-inverse distribution (see
Definition 2 for details). This distribution has similar tails as the max-stable distributions
used in [And12] or the precision sampling distribution [AKO11]. However, it has different
properties better suited to our setting, e.g., we can use pairwise independent variables to
do the scaling. In contrast, for max-stable distributions, we have to use fully random hash
3

functions and apply pseudo-random generators, which is problematic in our very low space
regime (a related technique called tabulation-based hashing has similar problems). Note that
[AKO11] does not require pseudo-random generators, but their precision sampling technique
aims to solve a more general family of problems and their distribution has a slightly different
form, e.g., the random variable is drawn from a continuous distribution. The p-inverse
distribution is particularly suited for p-norm estimation, and allows for a concise algorithm
and improved space complexity in our setting.
Next, we group the coordinates of v into Θ(log n) levels by their scalings, i.e., if 2−w Fp <
p
Xi ≤ 2−w+1 Fp , then i is in level w for some integer w. Let Zw ⊂ [n] be the set of universe
p p
items in level w. We observe that if i∗ ∈ Zw and Xi∗
fi∗ ≈ Fp , then
fip∗ = Ω(2w ).
Fortunately, we can also show that in expectation, i∗ is an `p -heavy hitter of the substream
induced by Zw . Our algorithm simply looks for i∗ from Zw for every w ∈ [log n]. One may
notice that if we run the search instance in parallel, then there will be a (log n)-factor blowup
in space. However, we can show that for random order streams, one can choose a
w0 = Θ (log log n)
such that
1. for all w > w0 : the search for i∗ can be done in one pass and in sequence for each w. This
is because fi∗ is large (i.e., Ω(2w )) and a small portion of the random order stream contains
sufficient information about i∗ .
2. for all w ≤ w0 : with high probability, |Zw | = poly log n. We thus do a brute force search
for each level w below w0 in parallel. Each search instance uses a small amount of memory
because of the small universe size.
The final space overhead becomes a poly(w0 ) factor rather than a Θ(log n) factor. This
observation is critical to reduce space usage for approximating frequency moments in random
order streams and is, to the best of our knowledge, new. For p ≥ 2, the above claim is no
longer true. We leave the exact space complexity for p ≥ 2 as an open problem.

1.3

Roadmap

In Section 2, we introduce some definitions and the p-inverse distribution. In Section 3, we
present our algorithm for F2 . In Section 4, we present our generic framework for approximating Fp as well as our main result. In Section 6, we present the detailed construction of
each subroutine used in Section 4, and the details of the main algorithm. In Section 7, we
introduce our deterministic algorithm, which uses our randomized algorithm as a subroutine.
We also show its optimality in the same section.

4

2

Preliminaries

Definition 1 (Aggregate Streaming)
An insertion-only stream (or simply stream) S = ha1 , a2 , . . . , am i is a sequence of integers,
where each ai ∈ [n]. A weighted stream S 0 = h(a1 , w1 ), (a2 , w2 ), . . . , (am , wm )i is a sequence
of pairs, where each ai ∈ [n] and each wm ∈ R. The insertion-only stream S is a special case
of a weighted stream with all the weights being 1. The frequency fi (S 0 ) of a weighted stream
is defined as the sum of all weights of the item i. Formally,
P
fi (S 0 ) := m
j=1 I (aj = i) wj .
The frequency vector V (S 0 ) ∈ Rn is the vector with the i-th coordinate being fi (S 0 ), for each
i ∈ [n]. The p-th frequency moment, for p ≥ 0, is defined as
P
Fp (S 0 ) := kV (S 0 )kpp := ni=1 fip (S 0 ).
For time 0 < t1 ≤ t2 ≤ m, we denote

S 0:t1 := h(a1 , w1 ), (a2 , w2 ), . . . , (at1 , wt1 )i and
S 0t1 :t2 := h(at1 , wt1 ), (at1 +1 , wt1 +1 ), . . . , (at2 , wt2 )i
as sub-streams of S 0 from 1 to t1 or from t1 to t2 .
We introduce a discretized version of the α-Fréchet distribution: the α-Inverse distribution.
Definition 2 Fixing an α > 0, we say a random variable X on N is drawn from an αInverse distribution if
P[X < x] = 1 − x1α for x ∈ N+ .
Definition 3 (α-Scaling Transformation)
Given an α > 0, an α-scaling transformation (ST) Tk,α : [n]m → ([k]×[n]×R)m is a function
acting on a stream of length m on universe [n]. On input stream S, it outputs a weighted
stream S 0 of length km on universe [k] × [n] via the following operation: let Xi,j be identical
independent (or with limited independence) α-Inverse random variables, where i = 1, 2, . . . , k
and j = 1, 2, . . . , n. For each a ∈ S, the transformation outputs
Tk,α (a) → ((a, 1), X1,a ), ((a, 2), X2,a ), . . . , ((a, k), Xk,a ).
The next lemma shows that the k2 -th largest element of the transformed frequency vector
gives a good approximation to the α-norm of the vector.
Lemma 4 Let S be a stream of universe [n]. Let Tk,α be a pairwise independent α-ST with
1
0
k ≥ α160
2 2 being an even integer and α ≥ 0, where  ∈ (0, 2α ). Let S = Tk,α (S). Define the
two sets,

U+ := (a, r) ∈ [n] × [k] : f(a,r) (S 0 ) ≥ 21/α (1 − ) kV (S)kα
5

and

U− := (a, r) ∈ [n] × [k] : f(a,r) (S 0 ) < 21/α (1 + ) kV (S)kα .

Then with probability at least 0.9,
|U+ | ≥ k2 ,

U− <

k
2

and

|U+ ∩ U− | > 0,

where U is the complement of the set U .
The proof of this lemma is provided in Section A.

3

A Simple F2 Algorithm For Long Streams

We start with a very simple algorithm for approximating F2 in a random order stream. We
denote the algorithm as RANDF2. The algorithm has a parameter b > 0. It treats the stream
updates as a series of length b blocks, i.e.,
S = (B1 , B2 , . . . , Bm/b ).
Initialize a register K = 0. At any time, suppose the current block is Bi . The algorithm
simply stores everything it sees until the end of Bi . After storing Bi entirely, the algorithm
computes
X fj (Bi )
Ki =
.
2
j=1
This can be done using space b log n bits. Then, the counter K is updated as
K ← K + Ki .
At the end of the stream, the algorithm computes
Y =

2K(m2 − m)
+ m,
(b2 − b)T

where T is the ID of the last complete block, and m is the length of the stream. The
algorithm uses O(b log n) bits. By setting
h


i
1
1
b = Θ max 2 log
,
2
·
log
.
n
δ
we obtain the following theorem.

Theorem 5 Let S be a random order stream satisfying F2 (S) ≥ m · log n. After one pass
over the stream S, Y is a (1 ± ) approximation to F2 (S) with probability at least 1 − δ.
Moreover, to compute Y , RANDF2 uses O (−2 log δ −1 + log n) bits of memory.
6

(j)

(j)

(j)

Proof For each j ∈ [n], we distinguish its stream updates as u1 , u2 , . . . , ufj (S) . Then Ki
(j)

(j)

is the number of pairs of the form (u`1 , u`2 ) appearing in Bi . We denote F2 = F2 (S) and
F1 = F1 (S) for simplicity. Thus,
∀i ∈ [T ] : E(Ki ) =

Pn

) b

fj (S)
j=1
2
F1
2

(

( )

Thus, by linearity of expectation,

2

=

F2 −m (b2 −b)
.
m2 −m
2

E[Y ] = F2 .
We now prove that Y is concentrated around its mean. Notice that the algorithm can be
viewed as sampling a number of “pairs”. A pair is formed by two updates to the same
universe element. There are q = (F2 − F1 )/2 many pairs. Let P = [q] denote the set of pairs.
For each P
pair z ∈ P , we let Xz denote the indicator that Xz is sampled by some bucket.
Let K = z∈P Xz . Note that this K is the same as the one denoted in the algorithm. Let
Qz = E[K|X1 , X2 , . . . , Xz ]. Then Qz for z = 1, 2, . . . form a Doob martingale. Also notice
that |Qz − Qz−1 | ≤ 1. Next, we proceed to bound the variance of
Qz − Qz−1 = Xz |X1 , X2 , . . . Xz−1 .
For a pair z ∈ P , let a, b be the two nodes. Consider a fixed assignment of X1 , X2 , . . . Xz−1 .
Also note that, knowing Xi , the two nodes of the i-th pair are assigned to some block.
Now, if from the information of X1 , X2 , . . . , Xz−1 , a, b are both assigned and to the same
block, then Xz = 1 and otherwise Xz = 0. For both cases V(Qz − Qz−1 ) = 0. If a, b are
assigned, but it cannot be determined if they are in the same block, then P[Xz = 1] ≤ b/m
and thus V(Xz ) ≤ b/m. If only one of a, b is assigned, then P[Xz = 1] ≤ b/m, and thus
V(Xz ) ≤ b/m. Lastly, if both a, b are not assigned, then P[Xz = 1] ≤ b/m. Thus V(Xz ) ≤
b/m. Overall, we have that vz2 := V(Qz − Qz−1 ) ≤ b/m for all possible X1 , X2 , . . . , Xz−1 . Let
P
2 −m)
.
V = z vz2 ≤ b(F2m
Next by Bernstein’s inequality [DP09], we have that,


t2
P[|K − E(K)| ≥ t] ≤ 2 exp − 2V (1+t/3V
.
)

Since we need to have a (1 ± ) approximation to F2 , we can set
2t(m2 − m)b
≤ F2
(b2 − b)m

and t = 

F2 b
.
2m

Since F2 ≥ m · log n · log 1δ , and  is sufficiently small, we can bound the error probability by:


t2
P[|K − E(K)| ≥ t] ≤ 2 exp −
2V (1 + t/3V )


2 2
 F2 b
≤ 2 exp −
≤ δ,
(1)
8m(F2 − m)
7

for b = Ω



log 1δ
2
 ·log n



. Finally, since K ∈ E(K) ± F2 b/(2m), we have
2b
·
Y ∈ F2 ±  F2m

2(m2 −m)b
(b2 −b)m

⊂ (1 ± )F2

as desired.

4

A Generic Framework for Fp Estimation

In this section, we first construct a generic framework for Fp estimation, and then we construct all the components in subsequent sections. For a random order stream S, we will need
the following three components to construct an Fp estimation algorithm.
• A counter that stores the time for the current update;
• An algorithm that gives a constant approximation to the current Fp (S :t );
• An algorithm that computes an accurate (1±) approximation to Fp (S) given poly(log n, −1 )
approximations to m and Fp (S).
To begin, we denote by C2Fp a data structure that, once initialized with a poly(log n, −1 )approximation of both the length and p-th frequency moments, Fp (S), supports two operations: update and query. At the end of the stream, C2Fp.query() returns either Fail or a
(1 ± )-approximation to Fp of the input stream S. Component (1) will be used to guess the
length of the stream, and component (2) will be used to guess an approximation to Fp (S).
We denote component (2) by ConstFp, which is a data structure that supports both update
and query operations. ConstFp.query() returns a 2-approximation to Fp (S :t ) at some fixed
t. The full framework is described in Algorithm 1.
Our full algorithm is denoted by RndFp , which uses C2Fp as a subroutine. From a high
level, the algorithm constantly guesses the length of the stream. If at some point in time the
algorithm finds that the current guess of the length is at least a factor C = poly(−1 , log n)
smaller than the true value of the stream, then the algorithm initializes a new instance of
C2Fp to estimate the Fp value of the stream. At the end, it is guaranteed that a stored
instance of C2Fp uses at least a (1 − poly(, 1/ log n)) portion of the stream to approximate
the frequency moments. It can be verified that an accurate estimation of Fp of this portion
of the stream will serve as a good estimator for the overall stream. Therefore, if C2Fp is able
to output the correct answer with high probability, then the algorithm RndF is guaranteed
to be correct with high probability.
1
, 12 ), and n ∈ N+ ,
Theorem 6 (Main Theorem) For fixed p ∈ [0, 2),  ∈ (0, 1),δ ∈ ( poly(n)
algorithm RndFp , making a single pass over a random order stream S on universe [n], outputs
a number Fb such that, with probability at least 1 − δ,

(1 − )Fp (S) ≤ Fb ≤ (1 + )Fp (S) ,
8

Algorithm 1: Full algorithm for Fp in random order: RndFp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Data:
S = ha1 , a2 , . . . , am i is random order stream of length m from universe [n] (known in
advance);
p ∈ [1, 2], a real constant;
Initialize (p, n, , δ):
m0 ← 1, m1 ← 1 G0 ← 1. Here m0 is the approximated length, G0 is a guess of Fp , 
is the target precision, and δ is the failure probability;
A1 ←new C2Fp(p, /3, n, m0 , G0 , δ/3), A2 ←new C2Fp(p, /3, n, m0 , G0 , δ/3);
A3 ←new ConstFp(p, n, δ/3);
C ← poly( 1 , log nδ );
Update a:
A1 .update(a), A2 .update(a), A3 .update(a);
m1 ← m1 + 1;
if m1 ≥ Cm0 then
A1 ← A2 ;
G0 ← A3 .query();
m0 ← m1 ;
A2 ←new C2Fp(p, /3, n, m0 , G0 , δ/3);
Query():
return A1 .query();

where the probability is over both the randomness of the algorithm and the randomness of
the data stream. The algorithm uses
"
!
#
4

1
1
1
O
+ log n log
log log n + log
2

δ
bits of memory in the worst case.

Proof Without loss of generality, we assume Fp (S) = Ω poly 1 poly log nδ , since otherwise
we can use a turnstile Fp algorithm with memory O 12 log log nδ + 12 log 1 bits to solve the
Fp estimation problem. Initialize m0 = 1. Let S 0 = S m0 :m . By definition of the algorithm,
A1 is an instance of C2Fp that runs on S 0 . Let S 00 = S 0:m0 and C = poly −1 polylog nδ . By
definition of the algorithm, we always update m0 such that
m
m
≤ m0 ≤ ,
2
C
C

9

at the end of the stream. By Lemma 25, and Lemma 26 with probability at least 1 − δ/3,
Fp (S)
≤ Fp (S 00 )
5p C 2p
p 


20n
20n
−1
C Fp (S) + 4 log
≤ 17 log
δ
δ

20n p
18 log δ
Fp (S),
≤
C
where the last inequality holds for sufficiently large Fp (S). Conditioned on this event, we
obtain that

20n
18
log

δ
kV (S 00 )kp ≤
kV (S))kp ,
kV (S))kp ≤
1/p
C
3p
for sufficiently large C. By the triangle inequality, we obtain
(1 − /(3p)) kV (S)kp ≤ kV (S)kp − kV (S 00 )kp

≤ kV (S 0 )kp ≤ kV (S)kp .

Thus Fp (S 0 ) is a (1 ± /3) approximation to Fp (S).
In the algorithm, A3 is an instance of ConstFp, i.e., by Theorem 7. Let G0 be the output
of A3 .query(). Since with probability at least 1 − δ/3, A3 outputs a c0 approximation to
Fp (S 00 ) for some constant c0 , we obtain that G0 is a

p−1
20n
p
2p
5 c0 C
log
δ
approximation to Fp (S 0 ).
In the algorithm, A1 is an instance of C2Fp, which runs on the stream S 0 at any time
t with the required parameters, i.e., G0 . By Theorem 8, with probability at least 1 − δ/3,
A1 .query() outputs a (1 ± /3) approximation to Fp (S 0 ), and thus a (1 ± ) approximation
to Fp (S). By a union bound, the overall algorithm is correct with probability at least 1 − δ.
By Theorem 16 and Theorem 17, the space needed for A1 and A2 is
"
!
#

4
1
1
1
log log n + log
+ log n log
.
O
2


δ
The space needed for A3 is O(log n log 1δ ) (Theorem 7). Thus the total space is dominated
by the total space used by A1 and A2 as desired.
The following is a theorem required in the above proof.
Theorem 7 (Const. Fp approx., [KNW10])
For a fixed n, there exists a turnstile streaming algorithm, which on input a stream S of
length m, outputs a number F ∈ (1 ± )Fp (S) with probability at least 1 − δ. The algorithm
uses O(−2 log m + log log(n)) log δ −1 ) bits of space in the worst case.
In subsequent sections, we will construct the C2Fp Algorithm.
10

A (1 ± ) Approximation to Fp With a Prior

5

In this section, we construct the algorithm C2Fp. We assume that the input is a random order
stream and that the algorithm is given two parameters, m
b and G, which are poly(−1 , log n)
approximations to the length and the p-th frequency moments of the stream S, respectively.

5.1

High Level Idea

Although the high level idea is introduced in the introduction, we repeat it here with more
details for better understanding of the algorithm. To illustrate the intuition of the algorithm,
we first consider a constant factor approximation algorithm. Estimating the frequency moments can be reduced to finding the heavy hitters of a scaled vector, as shown in Lemma 4.
Suppose the frequency vector in a stream is v = (f1 (S), f2 (S), . . . , fn (S)), and the scaling
applied to it is X = (X1 , X2 , . . . , Xn ), where the Xi are pairwise independent p-Inverse (see
Definition 2) random variables. Let i∗ be the maximum of the scaled vector. By Lemma 4,
we expect
Xip∗ fip∗ (S) ≈ Fp .
We group the coordinates of v into Θ(log n) levels by their scalings, i.e., if 2−w Fp < Xip ≤
2−w+1 Fp , then i is in level w. Let Zw ⊂ [n] be the universe items of level w. We observe that
if i∗ ∈ Zw , then
fip∗ (S) = Ω(2w ).

Luckily, we can also show that, in expectation, i∗ is an Fp -heavy hitter of the substream
induced by Zw . Our algorithm is simply looking for i∗ from Zw for every w ∈ [log n]. One
may notice that if we run the search instance in parallel, then there will be a log n factor
blowup in the space. However, we can show that in a random order stream, one can choose
an w0 = Θ (log log n) such that
1. for all w > w0 : the search for i∗ can be done in one pass and in sequence for each w.
2. for all w ≤ w0 : with high probability, |Zw | = poly log n. We thus do a brute force
search for each level w below w0 in parallel.
The final space overhead is a poly(w0 ) factor rather than Θ(log n).

To reduce the error from constant to (1 ± ), we repeat the above process Θ 12 times

conceptually. Namely, we apply a p-ST Tk,p transformation to the stream, where k = Θ 12 .
(r)
For r = 1, 2, . . . , [k], i = 1, 2, . . . , n, we denote the scaling p-Inverse random variable as Xi .
We wish to find the heavy hitter for each r using the same procedure described above. By
Lemma 4, the k/2-th largest of all the outputs serves as a good approximation to Fp (S).

5.2

The Algorithm

The algorithm needs three components, SmallApprox, SmallCont and LargeCont. All
these algorithms support “update” and “query” operations. SmallApprox returns fail if
11

Fp (S) is much larger than poly(−1 , log n), otherwise returns an approximation to Fp (S).
SmallApprox is a turnstile streaming Fp algorithm [KNW10] but with restricted memory. Once the memory exceeds the memory quota, the algorithm simply returns Fail.
SmallCont estimates the contribution from the small-valued frequencies and LargeCont estimates the contribution from the large-valued frequencies. The correctness of these algorithms is presented in Theorem 17, and 16. The full algorithm is presented in Algorithm 2.
The following theorem guarantees its correctness.
Theorem 8 Fix p ∈ [0, 2],  ∈ (0, 1/2) and δ = Ω( 1/ poly(n)). Let S be a random order
stream on universe [n] and with length m. Given that C0−1 Fp (S) ≤ G0 ≤ Fp (S) and C0−1 m ≤
m0 ≤ m for some C0 = poly(−1 , log n), there exists an algorithm A, which makes a single
pass over S and outputs a number F such that
F ∈ (1 ± )Fp (S)
with probability at least 1 − δ, where the probability is over both the randomness of the
algorithm and of the order of the stream. The algorithm uses

i
h
4
O 12 log log n + log 1 + log n log 1δ

bits of memory in the worst case.

We postpone the full proof and detailed algorithmic constructions to the appendix.

6

Continue on (1±) Approximation to Fp With a Prior

Proof [Proof of Theorem 8] The proof relies on the correctness of SmallApprox, SmallCont and
LargeCont, which is guaranteed by Theorem 16 and Theorem 17 and Lemma 7. We prove
the theorem by setting δ = 0.9. For general δ = Ω(1/ poly(n)), one only needs to repeat
the Algorithm 2 in parallel O(log 1δ ) times and output the median of theses instances. Notice that the parallel repetitions rely on the same stream, which makes the repetitions not
independent. We handle this issue at the end of the proof.
By the correctness of SmallApprox, if it does not return Fail, then it returns a number
F ∈ (1 ± )Fp (S) with probability at least 0.99. SmallApprox uses space


 
1
1
1
O 2 log log n + log
log
.


δ
If m ≤ poly(−1 , log n), then SmallApprox never returns Fail.
We now suppose m ≥ poly(−1 , log n). By Theorem 17, B3 , the instance of SmallCont,
with probability at least 0.97, returns a sequence of numbers which are approximations to the
(r)
top k p-Inversely scaled frequencies of S for large enough Xi s. Similarly for B2 , except this is
(r)
for the small Xi s. Let L = B1 .query()∪B2 .query() be the sequence returned. By Lemma 4,
12

Algorithm 2: Fp -Algorithm with Approximation: C2Fp(p, , n, m0 , G0 )
Data:
p ∈ [0,
i
h 2], a real number;
Fp (S)
, Fp
C0

(S) for some C0 = Θ [poly(−1 , log n)];
i
m0 ∈ Cm0 , m ;

L∈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

h

S = ha1 , a2 , . . . , am i is random order stream of length m;
Result: F ∈ (1 ± )Fp (S);
Initialize(p, n,
 , δ):
1
k ← Θ 2 ;
(r)
Xi ∼ p-Inverse distribution
 for i ∈ [n] and r ∈ [k], pairwise independent;
1
w0 ← d0 log log n + log  for some large constant d0 ;
(r)
Denote K ∈ Rn×k , whose coordinate Ki,r = Xi vi (only for notational purposes);
B1 ← new SmallApprox(p, n, );
B2 ← new SmallCont(p, n, k, , w0 , L, {Xir });
B3 ← new LargeCont(p, n, k, , w0 , L, {Xir });
Update(a):
B1 .update(a); B2 .update(a); B3 .update(a);
Query:
if B1 .query() 6=Fail then
return B1 .query()
else if B2 .query() =Fail or B3 .query() =Fail then
return Fail;
else
R ← the (k/2)-th largest element of B2 .query() ◦ B3 .query();
return (R)p /2

1/p

with probability at least 0.99, the (k/2)-th largest element of L is in (1±)21/p Fp (S). After
a proper scaling, we obtain the desired approximation.
The space requirement follows from Theorem 17 and Theorem 16.
We now show why the median of repetitions boosts the probability from 0.9 to an arbitrary 1−δ. Let Ω1 be the space of all possible random bits of the pairwise-independent p-ST.
Since it is pairwise independent, we have that |Ω1 | = poly(n). Additionally, let Ω2 be the
set of all possible orders of the stream and Ω3 be the set of all other random bits used in the
algorithm. Consider the events E1 and D1 for LargeCont as defined in Theorem 16. We have
that E1 = Ω01 ×Ω2 ×Ω3 , where Ω01 ⊂ Ω1 and |Ω01 |/|Ω1 | ≥ 0.98. Since P[D1 |E1 ] ≥ 1−1/ poly(n),
we argue that there exists a product space D10 = Ω01 × Ωu ⊂ D1 with


1
|Ω2 × Ω3 | .
|Ωu | ≥ 1 −
poly(n)
13

Indeed, for each ω ∈ Ω01 , let Dω ⊂ Ω2 × Ω3 be the event (D|ω). By the proof of Lemma 16,
ω|
we have |Ω|D
≥ 1 − 1/ poly(n). We can choose our parameters such that
2 ×Ω3 |
∀ω ∈ Ω01 : |Ω1 | (1 − P [Dω ]) =

1
.
poly(n)

Therefore, letting Ωu = ∩ω∈Ω01 Dω , we obtain the desired Ωu . Hence, conditioned on D10 , we
1
.
have P[E1 |D10 ] ≥ 0.98 and P[D10 ] ≥ 1 − poly(n)
1
Similarly, for SmallCont, we can find an event D20 such that P[D20 ] ≥ 1 − poly(n)
and
0
0
0
P[E2 ∩ F2 |D2 ] ≥ 0.98. Now conditioning on event D1 ∩ D2 , the algorithm outputs the desired
answer with probability at least 0.94. By repeating O(log δ −1 ) times and take the median
of all outputs, by a standard argument we boost the probability to 1 − δ.
In the following sections we will construct SmallCont in Section 6.2 and LargeCont Section 6.3. Before that, we first introduce our heavy hitter algorithm in random order streams
in the next section.

6.1

An Fp Heavy Hitters Algorithm in Random Order Streams

In this section, we describe an Fp heavy hitters algorithm for 0 ≤ p < 2 in the random order
model. This algorithm serves as a basic routine for approximating the frequency moments.
The algorithm outputs the identity of a constant Fp -heavy hitter using only a small portion
of the stream. The algorithm requires an approximation to Fp and to F1 . Formally, the
algorithm is presented in Algorithm 8 of Section C. At a high level, if there exists a heavy
hitter in the stream, the updates of the heavy hitter are evenly distributed among the stream
updates. This property of the random order model enables the algorithm to uses a small
trunk of updates to learn the index of the heavy hitter. For the small trunk of stream updates,
we use BPTree[BCI+ 16] to learn the identity of the heavy hitter. The formal guarantee of
the BPTree algorithm is as follows.
Theorem 9 ([BCI+ 16]) Given an insertion-only stream S over a universe [n] with length
m, after one pass over the stream, algorithm BPTree(, δ), for some constants , δ ∈ (0, 1),
outputs a set M ⊂ [n] × R, such that with probability at least 1 − δ, for all i ∈ [n], if
fi2 (S) ≥ 2 F2 (S)
then (i, fbi ) ∈ M with that fbi ∈ (1 ± )fi (S). BPTree uses O
space in the worst case.

1
2


log δ1 (log n + log m) bits of

To boost the probability of detecting the heavy hitter, we use Θ(log n) sequential trunks
of the stream to detect the heavy hitter. We argue that if i∗ is a heavy hitter, then with
high probability i∗ is detected in a constant fraction of these trunks. We use the Misra-Gries
[MG82] algorithm, MG, to store heavy hitter indices. MG is a deterministic algorithm. The
formal guarantee of this algorithm is,
14

Theorem 10 ([MG82]) Given a stream S over a universe [n] with length m, after one
pass over the stream, MG(c), for some constant 0 < c ≤ 1, outputs a set M ⊂ [n], such that
if
fi (S) ≥ cm
then i ∈ M . MG uses O(log n) bits of space in the worst case.
To show the guarantees of the algorithm, we first show the following lemma.
Lemma 11 Let S = ha1 , a2 , . . . , am i be a random order stream with universe [n]. Let S 0 =
hai1 , ai2 , . . . , aik i be a substream of a fixed sequence of distinct integers {i1 , i2 , . . . , ik } ⊂ [m].
Then
k2
E [F2 (S 0 )] ≤ k + 2 · F2 (S).
m
Proof We put a distinct label on each aggregate of each item. Let Kij be the indicator of
the j-th update of an item i being included in S 0 . Let
2

fi (S)
X
Xi = 
Kil  .
w=1

We have

fi (S)

Xi =

X

Kil + 2

w=1

and

E (Kil1 Kil2 ) =
Additionally with E (Ki,l ) =

k
,
m

X

Kil1 Kil2

w1 <l2

k2
k(k − 1)
≤ 2.
m(m − 1)
m

we obtain the desired statement.

Lemma 12 Let S = ha1 , a2 , . . . , am i be a random order stream with universe [n]. Let
S1 , S2 , . . . , St be distinct substreams of S (no overlaps), each of length k. Suppose 2tk ≤ m
1
and t = Θ(log n). Then, with probability at least 1 − poly(n)
, ∃I ⊂ [t] s.t. |I| ≥ 0.99t, and for
each i ∈ I,


4k 2
F2 (Si ) ≤ c4 · k + 2 F2 (S)
m
for some positive absolute constant c4 .

Proof For each i ∈ [t], let Ki be the indicator that


4k 2
F2 (Si ) ≤ c4 · k + 2 · F2 (S) .
m
15

P
Consider the Doob martingale formed by E( Kj |K1 , K2 , . . . , Ki )ti=1 . Let
hX
i
Wi = E
Kj |K1 , K2 , . . . , Ki
hX
i
−E
Kj |K1 , K2 , . . . , Ki−1 .
We observe that,

k2
F2 (S 0 )
(m − tk)2
4k 2
≤ k + 2 F2 (S) .
m

E [F2 (Si ) |K1 , K2 , . . . , Ki−1 ] ≤ k +

where S 0 is the stream after removing the initial i − 1 trunks. By Markov’s inequality, we
have



4k 2
≤ 0.001,
P F2 (Si ) > c4 · k + 2 · F2 (S)
m
P
for some constant c4 . Hence E( Kj ) ≥ 0.999t. By the Azuma-Hoeffding inequality,
X
X 

1
P
,
Kj − E
Kj ≤ 0.001t ≤ e−Ω(t) ≤
poly(n)

as desired.

Theorem 13 Let S = ha1 , a2 , . . . , am i be a random order stream. Suppose



Fp (S) = Ω poly log n m . m
b ≤ poly log n m.

1
, algorithm HHR returns
Then, conditioned on an event E with probability at least 1 − poly(n)
p
a set H ⊂ [n] such that if fi ≥ c0 Fp (S) then i ∈ H and |H| = Θ(1). The algorithm halts
with at most
#
"
poly (−1 , log n) m
b2
O
2/p
Fp (S)

stream updates.

Proof Throughout the proof,we use poly(n) to denote some large enough polynomial in
n. Since Fp (S) = Ω poly log n , we have that the number of stream updates consumed by
the algorithm is
!
poly(−1 log n)m
b
m
b2
log n · 2/p ≤ log n ·
m  m,
2/p
Fp
Fp

for sufficiently large Fp . Therefore, the algorithm will not output Fail. Let A be the event
that ∃I ⊂ [t] with |I| ≥ 0.99t and for each i ∈ I,


m21
F2 (Si ) ≤ c5 m1 + 2 F2 (S)
m
16

for some constant c5 . By Lemma 12,
P [A] ≥ 1 −

1
,
poly(n)

for some large polynomial in n. Let H ∗ ⊂ [n] be the set of (c0 , Fp )-heavy hitters in S, i.e.,
i ∈ H ∗ if and only if fip (S) ≥ c0 Fp (S). It is clear that |H ∗ | = Θ (1). For each j ∈ H ∗ , let
Bji be the event that
1/p

fj (Si ) ≥ c6 ·

m1
c m1
· fj (S) ≥ 0
· Fp1/p (S).
m
m

Moreover, we have
m1
m1 p
· Fp1/p (S) ≥
F2 (S) and
m
m
m21
m1
· Fp2/p (S) = m1 · 2 · Fp2/p (S) ≥ m1 .
2
m
m
Thus, conditioned on Bji , j is a constant F2 heavy hitter in the substream Si . By Lemma 22,
for each j ∈ [t]
 
1
P Bji ≥ 1 −
poly (n)
V
i
for another large enough poly(n). Letting E = A ∧ ti=1 B1i ∧ B2i ∧ . . . ∧ B|H
∗ | , then
P [E] ≥ 1 −

1
.
poly(n)

By the guarantee of BPTree and a Chernoff bound, with probability at least
1−

1
,
poly(n)

at least 0.98 fraction of the BPTree instances output the heavy hitters. Since the Misra-Gris
algorithm is a deterministic algorithm, it outputs the heavy hitters. Lastly, for the size of
H, by the guarantee of BPTree, we immediately have |H| = Θ (|H ∗ |) = Θ (1).
Remark 14 Suppose 1 ≤ p < 2 and for each i ∈ supp(V (S)), fi ≥ 1, then
poly (−1 , log n) m
2/p

Fp (S)

≤

poly (−1 , log n) m
2/p−1

Fp (S) · Fp
(S)
−1
poly ( , log n)
≤
 1,
2/p−1
Fp
(S)
17

as long as Fp  poly (−1 , log n). Similarly, for 0 ≤ p < 1, we have
poly (−1 , log n) m
2/p

Fp (S)

≤

poly (−1 , log n) m
1/p

1/p

Fp (S) · Fp (S)
poly (−1 , log n)
≤
 1,
1/p
Fp (S)

for sufficiently large Fp . Thus, the heavy hitter algorithm consumes only a small portion of
the stream updates.

6.2

Contributions from Large Frequencies
(r)

Recall that Xi , for r ∈ [k]
 and i ∈ [n], are the limited independence p-inverse random
1
variables, where k = Θ 2 . Also recall that we wish to find the heavy hitters of the pscaling transformed stream. To do so, we separate the universe items into Θ(log n) levels,
based on the values of the scaled frequencies, and thus induce Θ(log n) substreams. A level
of the scaled stream is defined from line 2 to 3 in Agorithm 3. For each r ∈ [k], we denote
(r)
the level w universe items as Zw (formally defined in line 2). A critical level w0 is chosen
such that


1
w0
2 = poly
, log n ,

and sufficiently large. In this section, we describe an algorithm that finds all the heavy
hitters of the p-inverse scaled stream for w ≥ w0 . For each r ∈ [k], denote H (r) as follows,
o
n
(r)
H (r) := i ∈ [n] : Xi vi ≥ 21/p−1 Fp 1/p (S) .
Namely, H (r) is the set of heavy hitters after scaling by the p-Inverse random variables.

Lemma 15 Let S be a random order stream on universe [n] with length m. Suppose m
b =
Θ (m), L ∈ [poly(, log1 n )Fp (S) , Fp (S)] and w0 = Ω(log 1 + log log n) is sufficiently large.
Then, conditioning on two events E1 and D1 , algorithm LargeContwLen outputs a sequence
(r)
R of at most k numbers such that for each r ∈ [k], w ≥ w0 and i ∈ H (r) ∩ Zw , there exists a
(r)
number y ∈ R with y ∈ (1 ± )Xi vi . Here E1 depends only on the random bits of the p-ST,
is independent with the order of the stream, and
P [E1 ] ≥ 0.98

and P [D1 |E1 ] ≥ 1 −

1
.
poly(n)



1
1
The algorithm
uses
O
log
n
+
log
+
log
log
n
bits in the worst case and halts with at
2




m
most O poly(−1
stream updates.
,log n)

Proof For each i ∈ [n] and r ∈ [k], where we recall that k = Θ 12 , given a random order
stream S, denote
v := V (S) := (f1 , f2 , . . . , fn ) .
18

(r)
Let fei = Xir · vi be the scaled frequency of item i. Recall the definition of H (r) ,
o
n
(r)
H (r) := i ∈ [n] : Xi vi ≥ 21/p−1 kvkp .

S
Let H = kr=1 H (r) . Let the event A be that |H| = Θ
definition of the p-Inverse distribution, we obtain

1
2


, which we condition on. By

P [A] ≥ 0.99.
(r)

(r)

For each t ∈ [γ] (γ is defined in line 4), let Zw,t := Zw ∩{i : h(i) = t}. For each i ∈ H, let wi,r,t
i
h 1/p
F
(S)
1/p
(r)
be the level that i ∈ Zwi,r,t ,t . Recall that C = poly(−1 , log n) and L ∈ p C , Fp (S) .
Hence


(r)
CL
Xi = Θ wi,r,t
.
/p
2

Thus,

vi = Ω



2wi,r,t /p kvkp
C
L



.

By definition of the p-ST, we observe, for each i ∈ [n], r ∈ [k] and w ∈ [Θ(log n)]
 w 


2
(r)
P i ∈ Zw A = Θ
,
C p Lp
we obtain

h

E Fp



(r)
Sw,t



i
kvkpp
w
A =2 ·
γC p Lp

for any t ∈ [γ].

By Markov’s inequality, for fixed w, t, r, and a fixed i,

 w kvkp  i
h 
(r)
P Fp Sw,t \ {i} ≥ O C2 p Lpp A ≤

1
γ

≤ O(2 ).


Conditioned on A, |H| = O(k) = O 12 . Then, by a union bound, with probability at least
(r)
0.99, for every r ∈ [k], each i ∈ H (r) is a (0.5, Fp )-heavy hitter in a substream Sw,t for some
w, t (as long as γ = Ω(−2 ) is large enough). Let this event be E1 . Note that event E1 is
independent with the order of the stream.
(r)
Now consider the su-routine of estimating the length of the stream Swt in line 13 of
(r)
Algorithm 3. If i ∈ Zw,t , then
F1



(r)
Sw,t






2w/p kvkp
1
≥ fi (S) &
= Ω poly
, log n .
C L


Denote m1 = m01 m/m,
b
where

m01 =

m  (r)tc :(tc +zw ) 
F1 Sw,t
.
zw
19

Therefore, by Lemma 22 (with the same argument as in the proof of Proposition 18), with
probability at least 1 − 1/ poly(n), the estimated length m01 satisfies,
r
(r)
(r)
(r)
m·log n
0
m1 − F1 (Sw,t ) ≤ 4
(r) F1 (Sw,t ) = O(F1 (Sw,t ))
zw ·F1 (Sw,t )

(r)

for sufficiently large zw . Thus m1 is a constant approximation to F1 (Sw,t ). Thus, in line 15,
(r)
with probability at least 1 − 1/ poly(n), every element i ∈ H (r) ∩ Zw,t is in the output of the
HHR algorithm. Similarly, with probability at least 1 − 1/ poly(n), line 16 returns a (1 ± )
(r)
approximation to fi (S) for each i ∈ H (r) ∩ Zw,t .
For those sub-streams containing no heavy hitters, the set output
byHHR is arbitrary. For

2w/p kvk

p
. By Proposition 18,
each such item j, suppose it is output in level w. Then vj = O
CL
with probability at least 1 − 1/ poly(n), the estimated frequency of each of them does not
exceeds vj + 2w/p kvkp /(LC). Thus j would not be stored by the heap structure. Let D1
be the event that the above happens for all i, r. We obtain that

P [D1 |E1 ] ≥ 1 −

1
,
poly(n)

for sufficiently large w0 .
The last step in line 18 stores a (1 ± ) approximation of the estimated frequency in a
heap data structure. This data structure uses at most

 
1
1
O 2 log + log log n


bits.
It remains to show that the number of stream updates consumed by the algorithm is
bounded. Since w0 = Ω(log 1 + log log n) can be made sufficiently large, the algorithm halts
after seeing at most
m
−1
poly ( , log n)
stream updates.

Theorem 16 Let S be a random order stream on universe [n] with length m. Suppose
poly(, 1/ log n) Fp (S) ≤ L ≤ Fp (S) and w0 = Ω(log 1 + log log n). Then Algorithm 4 has
the same guarantee as stated in Lemma 15.
Proof Algorithm 4 introduces a deterministic guess of the length of the stream. The correctness thus follows directly from Lemma 15.

20

Algorithm
3:
Estimate
the
contribution
r
LargeContwLen(p, n, , w0 , L, m,
b {Xi }, S)

of

large

frequencies:

Data: 

1/p
Fp (S)
1/p
L∈
, Fp (S) , where C = poly(−1 , log n);
C

1
2
3

S = ha1 , a2 , . . . , am i is random order stream of length m;
w0 , the smallest level to be considered;
m
b ∈ ( cm1 , c1 m) is a constant approximation to m;
{Xir } for i = 1, 2, . . . , n, r = 1, 2, . . . , k are pairwise independent p-Inverse random
variables;
Result: R = (r1 , r2 , . . . , rk ), where each ri ∈ R;
Initialize:
n
o
n
o
(r)
(r)
(r)
(r)
CL
Z0 ← i ∈ [n] × [k] : Xi ≥ CL ; Zw ← i ∈ [n] × [k] : 2(l−1)/p
< Xi ≤ 2CL
w/p ;
(r)

4
5
6
7
8
9
10
11
12

(r)m :m

−1

b poly( ,log n)
zw ← mC
; /*zw  m*/;
b
2w/p
if Stream ends before output then
return Fail;

for w = w0 + 1, w0 + 2, . . . , Θ(log n) do
for each t ∈ [γ], r ∈ [k] do
(r)
(r)
Swt ← substream induced by Zw ∩ {i ∈ [n] : h(i) = t};
(r)

m1 ← estimate the length of Swt using S tc :(tc +zw ) updates; tc ← tc + zw ;

 (r)tc :−1 
2w
N ← HHR p, c0 , m1 , O C
.output(), for some small enough constant
p , Swt

13
14

c0 > 0; /*c0 ≈ 0.5*/;
tc ← tc + stream length consumed by HHR;

Rf ← QueryFrequency 2w0 , N, , S tc :(tc +zw ) ; tc ← tc + zw ;
for a ∈ N do
#
"

15
16
17

HEAP.update

18

19

(r)

Sw ← S|Z (r) the substream induced by Zw , and Sw 1 2 ← S m1 :m2 |Z (r) ;
w
w
γ ← Θ 12 , h : [n] → [γ], pairwise independent hash function;
HEAP(k): a heap structure to maintain the largest-k inputs;
tc ← 1: the current pointer to the stream updates;



(r)
log Xa ·Rf (a)
log(1+)

;

return HEAP.output();

6.3

Contributions from Small Frequencies

In this section, we describe the algorithm that approximates all heavy scaled frequencies
(r)
in small levels, i.e., w ≤ w0 . In those levels, Xi s are large. Therefore, the probability of
(r)
(r)
sampling such a large Xi is small. Thus the resulting sets Zw are small enough, i.e., of
(r)
size poly(−1 , log n), with high probability. If the stream length of Sw is also small (e.g.,
poly(−1 , log n)), we can then directly run BPTree on these streams to report all the IDs (i.e.,
21

Algorithm
4: Estimating
LargeCont(p, n, , w0 , L, {Xir }, S)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

the

contribution

of

large

frequencies:

Result: R = (r1 , r2 , . . . , rk ), where each ri ∈ R;
Initialize:
m
b ← 2;
m1 ← 0;
A1 ←LargeContwLen(p, n, , w0 , L, m,
b {Xir }, S);
A2 ←LargeContwLen(p, n, , w0 , L, m,
b {Xir }, S);
while Not the end of the stream do
Read an input a;
Input a to A1 and A2 ;
m ← m + 1;
Input a to LargeContwLen;
if 2m
b ≤ m1 then
Discard A1 ;
A1 ← A2 ;
m
b ← m1 ;
A2 ←
LargeContwLen(p, n, , w0 , L, m,
b {Xir }, S m:−1 );
return whatever A1 returns;

hashed IDs) of the heavy hitters. We then use a modified CountSketch instance to report
the frequencies of these heavy hitters.
We modify the CountSketch [CCFC02] algorithm as follows. Each counter of the CountSketch
is restricted to be no more than O(log log n + log 1/) bits. If a counter exceeds this number
of bits, we put an ∞ marker on the counter. It is easy to see that if fi = O(poly(log n,
1
)), then the i0 -frequency can be reported as in the original algorithm. However if fi =

ω(poly(log n, 1/)), then one can simply report ∞. If we have
at
 1 that1 the universe size is 
most poly(log n, 1/), then the modified algorithm will use O 2 log δ (log log n + log 1/)
bits of space for error probability at most 0 < δ < 1.
However, if the stream length is large, i.e., poly(n), we can simply pick the initial
Θ(poly(−1 , log n))-length portion of the stream to estimate the heavy hitters and the frequencies. This is because in a random order stream, one can use a portion of the stream
to sample sufficiently many stream updates of the heavy hitters. Hence we obtain a good
approximation. Since we can consider only a small universe and a small stream length,
BPTree works with the desired space. The guarantee of the algorithm is as follows.
Theorem 17 Let S be a random order stream on universe [n] with length m. Then, conditioned on three events E2 , F2 and D2 , algorithm SmallCont outputs a sequence R of at most
(r)
k numbers such that for each r ∈ [k], w < w0 and i ∈ H (r) ∩ Zw , there exists a number
(r)
y ∈ R with y ∈ (1 ± )Xi vi . Here E2 depends only on the random bits of the p-ST and is
independent with the order of the stream. F2 is also independent of the stream conditioning
22

on D2 and E2 . Furthermore,
P [E2 ] ≥ 0.98,

The algorithm uses O[log n +

1
2

P [D2 |E2 ] ≥ 1 −

1
poly(n)

and

P [F2 |E2 , D2 ] ≥ 0.9.
4
log 1 + log log n ] bits in the worst case.

Proof By the same argument of the proof of Lemma
  15,with probability at least 0.98, if
(r)
(r)
(r)
for each i ∈ H ∩ Zw for all w ≤ w0 , i is a Ω w10 , Fp -heavy hitter of the stream Sw .
Let this event be E2 , which only depends on the random bits of the p-ST transformation.
For the rest of the proof, we condition on this event.
For each w ∈ [w0 ], let mw be the length of the stream BPTree used to approximate the
(r)
(r)
heavy

 hitter.

 Let event D2 be that for each r ∈ [k], w ≤ w0 and i ∈ H ∩ Zw , i is a
(r),:m
Θ w10 , F2 -heavy hitter in Sw w and


(r),:mw
f i Sw
m

∈ (1 ± ) fi (S) .


(r)
1
. First, if Fp Sw = O(poly(−1 , log n)), then by definition
We argue that P (D2 ) ≥ 1− poly(n)
mw

(r)

(r)
of m
 have that mw = m and the claim is true for any i ∈ H ∩ Zw . Next, we consider
 w , we
(r)
Fp Sw = Ω(poly(−1 , log n)) and sufficiently large, i.e., the memory exceeds in Line 12. We

have that mw = Θ (poly(−1 , log n)). By the same argument as in the proof of Theorem 13,
i.e., picking
"  2 #
(r)

mw = Ω

F1 Sw


2/p
(r)
Fp
Sw

,

(r)

then with probability at least 1 − 1/ poly(n), any i ∈ H (r) ∩ Zw is a (Θ (1) , F2 )-heavy hitter
(r)
in stream Sw . By Lemma 24, with probability at least 1 − 1/ poly(n), for each w ≤ w0 ,
mw = poly(−1 , log n).
Lastly, let event F2 be the event that all the HHR instances are correct and all the
CountSketch instances are correct. It follows immediately that P (F2 ) ≥ 0.9. Conditioned
on F2 , it is easy to see that the frequencies of each heavy hitter are reported with the desired
precision.
It remains to bound the space
used by the algorithm. Each BPTree instance takes

1
O w0 log w0 ·(log log n + log  ) bits of space. Each modified count sketch instance takes


O w20 log w0 log log n + log 1
bits of space. There are in total O(w0 ) count sketch instances and O(w0 /2 ) BPTree instances.

1
1 3
log
log
n
+
log
Therefore, the total space
used
is
O
·
2



1
log log log n + log  .
23

6.4

Frequency Query in the Random Order Model

If an item has large frequency, we can estimate its frequency with a small number of stream
updates. The formal algorithm is presented in Algorithm 6. It has the following guarantee:
Proposition 18 Given a random order stream S on universe [n] with length m. For a fixed

b i∗ (S)
= Ω 12 log 1δ then, with probability
i∗ , if mf
m
 1 − δ, Algorithm 6 returns a number
 at least
f , s.t. mf
∈ (1 ± )fi (S). Otherwise, mf
=O
m
b
m
b
space and consumes m
b stream updates.

m log
m
b

1
δ

. The algorithm uses O(log n) bits of

Proof By Lemma 22, with probability at least 1 − δ,
q
q 1
q 1
b
fi∗ (S :m
log δ
log δ
) fi∗ (S)
fi∗ (S)
,
− m ≤4
max
,
m
b
m
b
m
m
b

which we condition on. Consider Case 1:

Now consider case 2:

7

mf
b i∗ (S)
m

b
mfi∗ (S :m
)
m
b

=O

1
2

mf
b i∗ (S)
m

1
2

=Ω

− fi∗ (S) ≤ fi∗ (S) .


log 1δ . We obtain,

b
mfi∗ (S :m
)
m
b


log 1δ , we obtain,

− fi∗ (S) = O



m log
m
b

1
δ



.

Deterministic Algorithm for Fp Approximation

In this section we introduce our deterministic algorithm for Fp approximation, which follows from our randomized algorithm with an initial space-efficient randomness extraction
procedure applied to a prefix of the stream.

7.1

Upper Bound

Theorem 19 Fix p ≥ 0,  ∈ (0, 1). There exists a deterministic algorithm that makes
a single pass over a random order stream S on the universe [n], and outputs a number
F ∈ (1 ± )Fp (S) with probability at least 1 − δ, where the randomness is over the order of
the stream updates. The algorithm uses

4
1
1
1
1 1
1
O 2 log log n + log
log + log n · (log log n + log ) · + log n log


δ
δ δ

bits of memory, provided δ ≥ 1/ poly(n).

24

√
Proof W.l.o.g., we assume  ≥ 1/ n, since otherwise we can simply store an approximate counter for each item in the stream. It is sufficient to show that we are able to
de-randomize the randomized algorithm using the random updates from the stream using a
near-logarithmic number of bits of space. First we pick s = O(log log n + log δ −1 ) and store
all the universe items, their frequencies and their first arrival times until we obtain s distinct
items in the stream. Let z1 denote when the this happens. We assume the stream is long
enough that this step can be done, since otherwise we obtain an exact estimate of Fp . We
show in Section 7.1.1 how to obtain a nearly uniformly random seed of s bits.
We thus obtain a nearly uniform sample from all the prime numbers with O(log log n +
log 1δ ) bits (note that there are poly(log n/δ) many such prime numbers). Let this sampled
prime number be q. For the next O(log n/δ) distinct universe items, denoted by R, we argue
that with probability at least 1 − δ, all of them are distinct modulo q. Indeed, consider
any r1 , r2 ∈ R with r1 6= r2 . Then r1 − r2 can have at most log n prime factors ([HW79],
p.355). For all |R|
pairs, their differences can have at most O(log3 n/δ 3 ) distinct prime
2
factors in total. Thus with probability at least 1 − δ, q does not divide any of the differences.
Therefore the set R is mapped to distinct numbers modulo q. The value q can be stored
using at O(log log n + log 1δ ) bits.
Next we approximately store the frequencies of each item in R using the random order
stream. To do this, we first fix the following numbers g1 = 1, g2 = 2, g3 = 4, . . . , gi = 2i−1 .
For each r ∈ R, we store the largest number i such that fr (S z1 :gi ) = poly(log n, −1 ) and
fr (S z1 :gi ) as well. Therefore, such an operation only costs O( logδ n (log log n + log 1δ + log −1 ))
bits. By Lemma 23, the frequency of each item is preserved up to a (1 ± ) factor with
probability at least 1 − 1/ poly(n). Note that if the stream ends before we observe all of R,
we obtain a good approximation to Fp (S) immediately. We also store the first occurrence in
the stream of each item in R. We also store the parity of the first appearance time of each
item.
Repeating the extraction argument in Section 7.1.1 for the set R, we can now extract
O(log n) bits that is (1 ± δ) close to uniform. Given these bits, it now suffices to run our
earlier randomized algorithm on the remaining part of the stream.
There is one last problem remaining, however. Namely, it may be the case that the stream
used for extracting random bits contributes too much to Fp (S), causing the estimation of the
randomized algorithm to have too much error (since the prefix and the suffix of the stream
share the same items, we need to take the p-th power of the sum of their frequencies). This
problem can be solved as follows – we can continue the frequency estimation in parallel with
the randomized algorithm until the Fp value becomes at least a 1/ factor larger than the
time when we initialized our randomized algorithm. Therefore, if the stream ends before this
happens, then we use the frequency estimates for calculating Fp (S) from our deterministic
algorithm. Otherwise we use the value of the randomized algorithm (which is seeded with the
seed found by our deterministic algorithm). In either case, the overall error is at most Fp .

25

7.1.1

Derandomization


Let s > 0 be a parameter. Suppose we store t = O δs distinct universe items with their
approximate frequencies as well as the IDs and the parities of their first appearances in the
stream. Denote the set of these items as H and the overall length of the stream as m0 . Firstly,
we sort the items by their approximate counts and take the smallest δt/100 items as set L.
We additionally sort the items in L by their IDs, and obtain a bits string b of length |L|,
where each bit bi is the parity of the first appearance of the i-th item in L. Since L contains
0
the smallest δt/100 items of H, we have for each w ∈ L, fw (S 0:m ) ≤ m0 /t/(1 − δ/100). Thus
for each bit bi ,
2
1
P[bi = 0], P[bi = 1] ∈ ± 0 .
2 m
and
|L|





1
5|L|
1
δ
1
2
|L|
⊂ |L| 1 ± 0 ⊂ |L| 1 ±
.
∀x ∈ {0, 1} : P[b = x] ∈
±
2 m0
2
m
2
20
As such, we obtain a bits stream of length Ω(s), that is close to uniform bits up to a (1 ± δ)
factor.

References
[AGMS99] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking join and selfjoin sizes in limited storage. In Proceedings of the eighteenth ACM SIGMODSIGACT-SIGART symposium on Principles of database systems, pages 10–20.
ACM, 1999.
[AKO11]

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

[AMS96]

N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the
frequency moments. In Proceedings of the twenty-eighth annual ACM symposium
on Theory of computing, pages 20–29. ACM, 1996.

[And12]

A. Andoni. High frequency moment via max stability. Unpublished manuscript,
2012.

[BCI+ 16]

V. Braverman, S. R. Chestnut, N. Ivkin, J. Nelson, D. P. Woodruff, and
Z. Wang. Bptree: an `2 heavy hitters algorithm using constant memory. preprint
arXiv:1603.00759, 2016.

[BKSV14]

V. Braverman, J. Katzman, C. Seidell, and G. Vorsanger. An optimal algorithm
for large frequency moments using o (nˆ(1-2/k)) bits. In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum
fuer Informatik, 2014.
26

[BO10]

V. Braverman and R. Ostrovsky. Recursive sketching for frequency moments.
arXiv preprint arXiv:1011.2571, 2010.

[CCFC02]

M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data
streams. In International Colloquium on Automata, Languages, and Programming, pages 693–703. Springer, 2002.

[CCM08]

A. Chakrabarti, G. Cormode, and A. McGregor. Robust lower bounds for communication and stream computation. In Proceedings of the fortieth annual ACM
symposium on Theory of computing, pages 641–650. ACM, 2008.

[CJP08]

A. Chakrabarti, T. Jayram, and M. Patrascu. Tight lower bounds for selection
in randomly ordered streams. In SODA, pages 720–729, 2008.

[CKS03]

A. Chakrabarti, S. Khot, and X. Sun. Near-optimal lower bounds on the multiparty communication complexity of set disjointness. In Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on, pages 107–117.
IEEE, 2003.

[CMVW16] M. Crouch, A. McGregor, G. Valiant, and D. P. Woodruff. Stochastic streams:
Sample complexity vs. space complexity. In LIPIcs-Leibniz International Proceedings in Informatics, volume 57. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
[DLOM02] E. Demaine, A. López-Ortiz, and J. Munro. Frequency estimation of internet
packet streams with limited space. Algorithms—ESA 2002, pages 11–20, 2002.
[DP09]

D. P. Dubhashi and A. Panconesi. Concentration of measure for the analysis of
randomized algorithms. Cambridge University Press, 2009.

[GH09]

S. Guha and Z. Huang. Revisiting the direct sum theorem and space lower
bounds in random order streams. Automata, Languages and Programming,
pages 513–524, 2009.

[GM09]

S. Guha and A. McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on Computing, 38(5):2044–2059,
2009.

[HW79]

G. H. Hardy and E. M. Wright. An introduction to the theory of numbers.
Oxford University Press, 1979.

[Ind00]

P. Indyk. Stable distributions, pseudorandom generators, embeddings and data
stream computation. In Foundations of Computer Science, 2000. Proceedings.
41st Annual Symposium on, pages 189–197. IEEE, 2000.

27

[IW05]

P. Indyk and D. Woodruff. Optimal approximations of the frequency moments
of data streams. In Proceedings of the thirty-seventh annual ACM symposium
on Theory of computing, pages 202–208. ACM, 2005.

[KNPW11] D. M. Kane, J. Nelson, E. Porat, and D. P. Woodruff. Fast moment estimation
in data streams in optimal space. In Proceedings of the forty-third annual ACM
symposium on Theory of computing, pages 745–754. ACM, 2011.
[KNW10]

D. M. Kane, J. Nelson, and D. P. Woodruff. On the exact space complexity of
sketching and streaming small norms. In Proceedings of the twenty-first annual
ACM-SIAM symposium on Discrete Algorithms, pages 1161–1178. SIAM, 2010.

[MG82]

J. Misra and D. Gries. Finding repeated elements. Science of computer programming, 2(2):143–152, 1982.

[MP80]

J. I. Munro and M. S. Paterson. Selection and sorting with limited storage.
Theoretical computer science, 12(3):315–323, 1980.

[Woo04]

D. Woodruff. Optimal space lower bounds for all frequency moments. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms,
pages 167–175. Society for Industrial and Applied Mathematics, 2004.

A

Proofs

Lemma 20
(1 − x)−α ≥ 1 + αx


1
for any x ∈ 0, 2α
and α ≥ 0.

Lemma 21

(1 + x)−α ≤ 1 −


1
for any x ∈ 0, 2α
and α ≥ 0.

and

(1 − x)−α ≤ 2

α
x and
2

(1 + x)−α ≤ 1

Proof [ of Lemma 4] For each (i, j) ∈ [k] × [n], f(i,j) (S 0 ) = fj (S)Xi,j , where Xi,j is an
α-Inverse random variable. We define the indicator random variables

Ai,j := I f(i,j) (S 0 ) ≥ 21/α (1 − ) kV (S)kα
and

0
1/α
Bi,j := I f(i,j) (S ) ≥ 2 (1 + ) kV (S)kα .

Thus

|U+ | =

X

(i,j)∈[k]×[n]

Ai,j

and |U − | =

28

X

(i,j)∈[k]×[n]

Bi,j .

By definition of the α-Inverse distribution,
1
fi,j (S 0 )α
(1 − )−α
and
2
kV (S)kαα
1
fi,j (S 0 )α
= 1] = (1 + )−α
.
2
kV (S)kαα

P [Ai,j = 1] =
P [Bi,j
Hence,

k
k
(1 − )−α ≥ (1 + α)
2
2
k
V(|U+ |) ≤ (1 − )−α ≤ k.
2

E (|U+ |) =

By Chebishev’s inequality,

X
P

Ai,j

i∈[k],j∈[n]

for k ≥ 160/(α2 2 ). Thus,



1
< k ≤
2

k
α
k
2



2 =



4
α2

and



1
2 k

≤ 0.05,


1
P |U+ | < k ≤ 0.05.
2

Similarly,



1
P |U − | ≥ k ≤ 0.05.
2

By a union bound, with probability at least 0.1, we have
|U |+ ≥

k
2

and

U− <

k
,
2

which we condition on. Thus
|U+ ∩ U− | = U+ \U − >

k k
− = 0,
2 2

concluding the proof.

Lemma 22 Let S = ha1 , a2 , . . . , am i be a random order stream on the universe [n]. Let
S 0 = hai1 , ai2 , . . . , aik i be a substream of fixed k distinct integers {i1 , i2 , . . . , ik } with k ≤ m.
Then, for any j ∈ [n]

q
q 1
q 1 
log δ
log δ
fj (S 0 )
fj (S)
fj (S)
P
− m ≥4
max
,
k
k
m
k
≤ 2δ.

29

Proof We assign unique labels to each of the updates of item j, i.e., let these updates be
b1 , b2 , . . . , bfj (S) .
Let
Z1 , Z2 , . . . , Zfj (S)
be the indicators of these items to be in S 0 . Then

m−1
(m − 1)!
k!(m − k)!
k
k−1
P [Zi = 1] = m =
·
= .
(k − 1)!(m − k)!
m!
m
k

Pfj
We now consider the Doob Martingale E[ l=1
Zl |Z1 , Z2 , . . . , Zr ] for r = 1, 2, . . . , fj . Let
" r
#
X
Dr = E
Zl |Z1 , Z2 , . . . , Zr
−E
We have

" l=1
r
X
l=1

#

Zl |Z1 , Z2 , . . . , Zr−1 .

P
Zl
k − j−1
k
P [Dr = 1] ≤
≤ .
Pl=1
j−1
m
m − l=1 Zl

Thus

V (Dr |Z1 , Z2 , . . . , Zr−1 ) ≤

k
.
m

By Bernstein’s inequality [DP09](Theorem 8.2),
"
#


X
k
−γ 2
P
Zl −
· fj (S) > γ ≤ 2 exp
,
γ
m
2V [1 + 3V
]
l
where
V =

fj
X
r=1

V (Dr |Z1 , Z2 , . . . , Zr−1 ) ≤

k
· fj (S) .
m

q
q
q

k
1
Plugging in γ = 4 log 1δ max
f
(S),
log
, we obtain
m j
δ
P

"

X
l

#


k
1
Zl −
· fj (S) > γ ≤ 2 exp − log
≤ 2δ.
m
δ

30

Lemma 23 Let S = ha1 , a2 , . . . , am i be a random order stream on the universe [n]. Let
S 0 = hai1 , ai2 , . . . , aik i be a substream of k fixed distinct integers {i1 , i2 , . . . , ik } with k ≤ m.
Then,
q

q 1 
q 1
log δ
log δ
F1 (S 0 )
F1 (S)
F1 (S)
− m ≥4
max
,
P
k
k
m
k
≤ 2δ.

Proof This is identical to the proof of Lemma 22.

Lemma 24 Let S = ha1 , a2 , . . . , am i be a random order stream on the universe [n]. Let
S 0 = hai1 , ai2 , . . . , aik i be a substream of k fixed distinct integers {i1 , i2 , . . . , ik } with k ≤ m.
Suppose F0 (S) ≥ −2 and for each i ∈ [n], k ≤ m − fi . Then,
"

fi #
X
k
1− 1−
≤ E (F0 (S 0 ))
m − fi
i∈[n]:fi >0
"

f #
X
k i
≤
1− 1−
m
i∈[n]:fi >0

and


P [|F0 (S 0 ) − E (F0 (S 0 ))| ≥ F0 (S)] ≤ exp −2 F0 (S) .

Proof Consider stream S 0 , and let Zi denote the indicator random variable indicating that
element i is sampled. We have that

m−fi
k
P [Zi = 1] = 1 − m
k

(m − fi − k + 1)(m − fi − k + 2) . . . (m − k)
=
.
(m − fi + 1)(m − fi + 2) . . . (m)

Thus


1−

k
m − fi

fi


f
k i
≤ P [Zi = 1] ≤ 1 −
.
m

For concentration, we will use a Bernstein inequality for martingales [DP09](Theorem 5.1).
For each Zi , when it is revealed, F0 changes by at most 1. Thus,


P [|F0 (S 0 ) − E (F0 (S 0 ))| > F0 (S)] ≤ 2 exp −2 F0 (S) .

31

Lemma 25 (Substream polylog Approx.) Let S = ha1 , a2 , . . . , am i be a random order
stream on the universe [n]. Let S 0 = hai1 , ai2 , . . . , aik i be a substream of k fixed distinct
integers K = {i1 , i2 , . . . , ik } with k ≤ m. Then for fixed p ≥ 0, δ ∈ (0, 1/2), with probability
at least 1 − δ,

  kp
2
20n 1−p
log
F (S) − 4 log 20n
≤ Fp (S 0 ).
min 1, 5m
k2
δ
(5m)p p
δ

δ
Proof Given δ 0 ∈ 0, 20n
, we split the universe [n] into two sets,


5m log δ10
N1 = i ∈ [n] : fi ≥
and N2 = [n]\N1 .
k
Accordingly, define
S1 = haj : aj ∈ N1 i and S2 = haj : aj ∈ N2 i.

S10 and S20 are defined similarly for the set of K.
First, by Lemma 22, with probability at least 1 − 2nδ 0 , for each i ∈ N1 ,
r
r
k
1
kfj (S)
fi (S 0 ) = fi (S) ± 4 log 0
m
δ
m
k
3k
⇒
fi (S) ≤ fi (S 0 ) ≤
fi (S).
5m
m
For the remainder of N2 , with probability at least 1 − 2δ 0 ,


k
1
0
F1 (S2 ) ≥ max
F1 (S2 ) − 4 log 0 , 0 .
m
δ
Therefore, with probability at least 1 − (2n + 2)δ 0 ,


kp
k
1
0
Fp (S ) ≥ p p Fp (S1 ) + max
F1 (S2 ) − 4 log 0 , 0
5m
m
δ

1 1−p
p
5m log δ0
k
1
k
≥ p p Fp (S1 ) +
Fp (S2 ) − 4 log 0
5m
k
m
δ

1−p !
2
p
5m
1
k
1
≥ min 1, 2 log 0
Fp (S) − 4 log 0 .
p
k
δ
(5m)
δ
Setting δ 0 = δ/(20n), we obtain the desired upper bound.
Lemma 26 (Substream polylog upper bound) Let S = ha1 , a2 , . . . , am i be a random
order stream on the universe [n]. Let S 0 = hai1 , ai2 , . . . , aik i be a substream of k fixed distinct
integers K = {i1 , i2 , . . . , ik } with k ≤ m. Then for fixed p ∈ [1, 2], δ ∈ (0, 1/2), with
probability at least 1 − δ,

p 

20n
k
20n
0
Fp (S ) ≤ 17 log
Fp (S) + 4 log
.
δ
m
δ
32

Proof Analogous to the proof of Lemma 25, we split the universe items into two parts, N1
and N2 . For N1 , the corresponding substream is S10 and we have that with probability at
least 1 − 2nδ 0 ,
3p k p
Fp (S10 ) ≤
Fp (S1 ).
mp
For the other part of the universe, N2 , we have that with probability at least 1 − 2nδ 0 , for
each i ∈ N2 ,
r
r
1
1
1
k
5 log ≤ 17 log 0 .
fi (S 0 ) ≤ fi (S) + 4 log
m
δ
δ
δ
0
Also with probability at least 1 − 2δ ,
F1 (S20 ) ≤

k
1
F1 (S2 ) + 4 log 0 .
m
δ

Denote f ∗ = maxi∈N2 fi (S 0 ). We obtain,
X p−1
Fp (S20 ) ≤
f ∗ fi (S 0 )
i∈N2

p

1
≤ 17 log 0 F1 (S20 )
δ

p 

1
1
k
Fp (S2 ) + 4 log 0 .
≤ 17 log 0
δ
m
δ

By setting δ 0 =

δ
,
20n

we obtain the desired bound.

Proof [of Theorem 27]
Consider a stream of two numbers a, b ∈ [n]. Then there are only two permutations.
Namely S1 = ha, bi, S2 = hb, ai. Since A is correct for at least 60% of the permutations, A
has to be correct on both S1 and S2 . Therefore, A can be used to solve the communication
problem EQUALITY deterministically, see, e.g., Section 3.5 of [AMS96]. Thus an Ω(log n)
bits of space lower bound follows from the deterministic communication complexity of the
EQUALITy problem.

B
B.1

More Proofs on Derandomization
Lower Bound

We prove the following lower bound.
Theorem 27 For any one-pass deterministic streaming algorithm A, if A outputs a (1 ±
0.1)-approximation to Fp (S) for at least 60% of all the permutations of stream updates in S,
for any S, then A must use Ω(log n) bits of memory.
33

Proof [Proof of Theorem 27]
Consider a stream of two numbers a, b ∈ [n]. Then there are only two permutations.
Namely S1 = ha, bi, S2 = hb, ai. Since A is correct for at least 60% of the permutations, A
has to be correct on both S1 and S2 . Therefore, A can be used to solve the communication
problem EQUALITY deterministically, see, e.g., Section 3.5 of [AMS96]. Thus an Ω(log n)
bits of space lower bound follows from the deterministic communication complexity of the
EQUALITY problem.

C

Other Algorithms

34

Algorithm
5:
Estimate
n
o the
(r)
SmallCont.(p, n, , w0 , L, Xi
, S)

contribution

of

small

frequencies:

Data: 

1/p
Fp (S)
1/p
L∈
, Fp (S) , where C = poly(−1 , log n);
C

1
2
3
4

5
6
7
8
9
10
11
12

S = ha1 , a2 , . . . , am i is random order stream of length m;
w0 , the smallest level to be considered;
{Xir } for i = 1, 2, . . . , n, r = 1, 2, . . . , k are pairwise independent p-Inverse random
variables;
Result: R = (r1 , r2 , . . . , rk ), where each ri ∈ R;
Initialize:
o
n
o
n
(r)
(r)
(r)
(r)
CL
< Xi ≤ 2CL
Z0 ← i ∈ [n] × [k] : Xi ≥ CL ; Zw ← i ∈ [n] × [k] : 2(l−1)/p
w/p ;
(r)

while sizeof(memory(B)) ≤ Θ w0 log w0 log log n + log 1
(r)
B.update(stream updates of Sw );
m0 ← m0 + 1;

14

16
17

20
21
22
23



do

Hw ← B.return();
for i ∈ Hw do

fi ← mm0 fi S m0 :2m0 ; /*m is calculated at the end of the stream.*/;

15

19

m :m (r)

Run in parallel:
for w ∈ [w0 ] do
Hash the IDs of Zw to the universe [poly(log n, −1 )];
CSw .input(Sw );
Run in parallel:
for r ∈ [k] do


B ←BPTree.initialize w10 , 0.01
w0 ; m0 ← 0;

13

18

(r)

Sw ← S|Z (r) the substream induced by Zw , and Sw 1 2 ← S m1 :m2 |Z (r) ;
w
w
 2
CSw ←CountSketch , w 0 /*Modified countsketch instance such that each counter is


restricted to use O log log n bits.*/;

At the end of the stream:
for i ∈ Hw do
fi0 ← CSw (i);
if fi 6= ∞ then
fi ← fi0 ;
return

Sw0

w=0 Hw ;

35

Algorithm 6: Estimate the frequency of an element: QueryFrequency(i∗ , m,
b , δ, S)

1
2
3
4
5

Data:
S = ha1 , a2 , . . . , am i is a random order stream;
, δ ∈ (0, 1/2);
i∗ ∈ [n], the frequency to be queried;
m
b : the length of the stream used to query the frequency of item i∗ ;
Result: fb ∈ R;
Query:
if |S| < m
b then
return 0;
else

return

b)
fi∗ (S 1:m
;
m
b

Algorithm 7: Fp -algorithms for small streams: SmallApprox(p, n, S)

1
2
3
4

Data:
S = ha1 , a2 , . . . , am i is a random order stream of length m;
Result: F : F ∈ ((1 − )Fp (S), (1 + )Fp (S)) is a (1 ± )-approximation to Fp (S);
Run an optimal turnstile streaming algorithm
A for Fp , with the following modification: if

at any point the counter exceeds poly 1 poly log n then
d
e return Fail. else
return whatever the algorithm A returns.

36

Algorithm 8: Fp -Heavy Hitter Algorithm: HHR(p, c0 , m,
b F, S)
Data: ;
0 < c0 ≤ 1 is a constant;
p ∈ (0, 2) a real number;
, for some constant
parameter C > 1;
m
b ≥ hm
C
i
F ∈

1
2
3
4

5
6
7
8
9
10
11

12
13
14

Fp (S)
, Fp
C1

(S) , for some parameter C1 = poly(−1 , log n);

S = ha1 , a2 , . . . , am i is a random order stream of length m;
Result: H ⊂ [n]: a set of (c0 , Fp )-heavy hitters.
Initialize:
b2
m1 ← Fm
2/p ;
t ← c1 log n; /*for some sufficiently large constant c1 > 0*/;
M ← MG(c2 ); /*a Misra-Gris algorithm instance, for small enough constant
c2 ≤ c0 */;
if m1 ≤ (log n)c3 then
m1 ← (log n)c3 ; /* c3 > 0 is a large enough constant*/;

while not at end of the stream do
Let S1 , S2 , . . . , St be consecutive stream updates each of length m1 ;
for j = 1 to t do
Hj ←BPTree(Sj , c2 , 0.01);
/*Use the BPTree to detect constant heavy hitters, errs with probability at
most 0.01*/;
M .update(Hj ); /*Input all elements in Hj to MG*/;
return M.outputs().
return Fail.

37

