# Separations for Estimating Large Frequency Moments on Data Streams

David P. Woodruff
Carnegie Mellon University. E-mail<EMAIL_ADDRESS>Samson Zhou Carnegie
Mellon University. E-mail<EMAIL_ADDRESS>
###### Abstract

We study the classical problem of moment estimation of an underlying vector
whose $n$ coordinates are implicitly defined through a series of updates in a
data stream. We show that if the updates to the vector arrive in the random-
order insertion-only model, then there exist space efficient algorithms with
improved dependencies on the approximation parameter $\varepsilon$. In
particular, for any real $p>2$, we first obtain an algorithm for $F_{p}$
moment estimation using
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\right)$
bits of memory. Our techniques also give algorithms for $F_{p}$ moment
estimation with $p>2$ on arbitrary order insertion-only and turnstile streams,
using $\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\right)$ bits of space and two passes, which is the first optimal
multi-pass $F_{p}$ estimation algorithm up to $\log n$ factors. Finally, we
give an improved lower bound of $\Omega\left(\frac{1}{\varepsilon^{2}}\cdot
n^{1-2/p}\right)$ for one-pass insertion-only streams. Our results separate
the complexity of this problem both between random and non-random orders, as
well as one-pass and multi-pass streams.

##  1 Introduction

The efficient computation of statistics has emerged as an increasingly
important goal for large databases storing information generated from
financial markets, internet traffic, IoT sensors, scientific observations,
etc. The one-pass streaming model formally defines an implicit and underlying
dataset through sequential updates that arrive one at a time and describe the
evolution of the dataset over time. The goal is to aggregate or approximate
some statistic of the input data using space that is sublinear in the size of
the input.

The frequency moment estimation problem is fundamental to data streams. Since
the celebrated paper of Alon, Matias, and Szegedy [AMS99], the frequency
moment estimation problem has been a central problem in the streaming model;
more than two decades of research [AMS99, CKS03, BJKS04, Woo04, IW05, Ind06,
Li08, KNW10, KNPW11, Gan11, BO13, BKSV14, BDN17, BVWY18, GW18, WZ20] has
studied the space or time complexity of this problem.

We first consider the _insertion-only_ model, where updates take the form
$u_{1},\ldots,u_{m}$ in a stream of length $m$ and each update $u_{t}$ is in
$[n]=\\{1,2,\ldots,n\\}$ for $t\in[m]$. We assume for simplicity that
$m\leq\operatorname*{poly}(n)$. The updates implicitly define a frequency
vector $f\in\mathbb{R}^{n}$ so that each update effectively increases a
coordinate of $f$ in the sense that $f_{i}=|\\{t\,:\,u_{t}=i\\}|$ for each
$i\in[n]$. Given $p,\varepsilon>0$, the $F_{p}$ moment estimation problem is
to approximate $F_{p}=\sum_{i\in[n]}(f_{i})^{p}$ within a $(1\pm\varepsilon)$
factor. The complexity of this problem differs greatly for the range of $p$.
For $p>2$, [BJKS04, CKS03] showed that even for the streaming model, the space
usage for $F_{p}$-estimation requires polynomial factors in $n$ and $m$,
whereas polylogarithmic factors are achievable for $p\leq 2$ [AMS99, Ind06,
Li08, KNW10, KNPW11, BDN17].

We initially focus on the frequency moment estimation problem in the _random-
order_ model, where the set of stream updates to the underlying frequency
vector is worst case, but the order of their arrival is uniformly random. As
usual, the algorithms we initially consider are only permitted a single pass
over the stream, though we later relax this constraint to permit adversarial
ordering of updates, as well as both positive and negative integer updates
(with magnitude bounded by $\operatorname*{poly}(n)$) to the coordinates of
the frequency vector in the _turnstile_ model. Random-order streams have been
shown to be a natural assumption for problems of sorting and selecting in
limited space [MP80] and many other real-world applications [GM06, GM07,
DLM02, CJP08]. Interestingly, there has sometimes been a significant
qualitative difference between random-order streams and adversarial (or
arbitrary) order streams [KMM12, BKSV14, BVWY18]. In particular for
$F_{p}$-moment estimation, the best known lower bound is
$\Omega\left(\frac{1}{\varepsilon^{2}}\right)$ [CCM16]. While the best known
upper bound for $p\in(0,2]$ on arbitrary order insertion-only streams is
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\log n\right)$ [AMS99, KNW10,
KNPW11], Braverman _et. al._ [BVWY18] gave an algorithm for $p\in(0,2)$ on
random-order streams that only used
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{2}}+\log n\right)$ space,
where for a function $g(n,\varepsilon)$, we use
$\tilde{\mathcal{O}}\left(g(n,\varepsilon)\right)$ to denote a function
bounded by $g(n,\varepsilon)\cdot\operatorname*{polylog}(g(n,\varepsilon))$.
They also gave an algorithm for $F_{2}$-moment estimation that only uses
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{2}}+\log n\right)$ space, but
requires the assumption that $F_{2}\geq F_{1}\cdot\log n$, i.e., the second
moment must be a logarithmic factor larger than the length of the stream.

The above works raise a number of important questions. A tantalizing open
question, studied extensively in [JW19], and dating back to the original work
of Alon, Matias, and Szegedy [AMS99], is the exact space complexity of
$F_{p}$-moment estimation in insertion-only streams. For $p>2$, the best known
upper bound for $F_{p}$-moment estimation on arbitrary order insertion-only
streams is the minimum of
$\mathcal{O}\left(\frac{n^{1-2/p}}{\varepsilon^{20}}\right)$ [BKSV14] and
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{2}}\cdot n^{1-2/p}\right)$
[Gan11, GW18]. For insertion-only streams, the best known lower bound is
$\tilde{\Omega}\left(\frac{n^{1-2/p}}{\varepsilon^{2}\log n}\right)$ [Gan12].
We summarize these results in Figure 1.

Reference | Space Complexity | Stream Order
---|---|---
[IW05, MW10, And17] | $\tilde{\mathcal{O}}\left(n^{1-2/p}\varepsilon^{-\mathcal{O}\left(1\right)}\right)$ | Arbitrary
[BKSV14] | $\mathcal{O}\left(n^{1-2/p}\varepsilon^{-20}\right)$ | Arbitrary
[AKO11] | $\tilde{\mathcal{O}}\left(n^{1-2/p}\varepsilon^{-2-6/p}\right)$ | Arbitrary
[BGKS06] | $\tilde{\mathcal{O}}\left(n^{1-2/p}\varepsilon^{-2-4/p}\right)$ | Arbitrary
[Gan11, GW18] | $\tilde{\mathcal{O}}\left(n^{1-2/p}\varepsilon^{-2}\right)$ | Arbitrary
This work | $\tilde{\mathcal{O}}\left(n^{1-2/p}\varepsilon^{-4/p}\right)$ | Random or Two-Pass Arbitrary
[AMS99, Woo04] | $\Omega\left(n^{1-5/p}+\varepsilon^{-2}\right)$ | Arbitrary
[CKS03] | $\Omega\left(n^{1-2/p}\varepsilon^{-2/p}\right)$ | Arbitrary
[WZ12] | $\Omega\left(n^{1-2/p}\varepsilon^{-4/p}/\log^{\mathcal{O}\left(1\right)}n\right)$ | Arbitrary, $\mathcal{O}\left(1\right)$-Passes
[Gan12] | $\Omega\left(n^{1-2/p}\varepsilon^{-2}/\log n\right)$ | Arbitrary
[AMOP08, CCM16] | $\Omega(n^{1-2.5/p}/\log n+\varepsilon^{-2})$ | Random
This work | $\Omega\left(n^{1-2/p}\varepsilon^{-2}\right)$ | Arbitrary
Fig. 1: Summary of recent work for large frequency moment estimation

There are also major gaps in our understanding for $F_{p}$-moment estimation
for $p>2$ in random order streams. The best known111After discussion with the
authors, there appears to be an error in [GH09], which claims a stronger lower
bound. lower bound is $\Omega(n^{1-2.5/p}/\log n+\varepsilon^{-2})$ [AMOP08,
CCM16], while no upper bounds that do better in random order streams than in
arbitrary insertion streams are known.

###  1.1 Our Results

In this paper, we show a separation not only between random-order and
arbitrary insertion-only streams for the $F_{p}$ moment estimation problem,
but also one-pass and multi-pass streams. We first show improved bounds for
the $F_{p}$ moment estimation problem for every $p>2$ in the random-order
insertion-only streaming model.

######  Theorem 1.1.

For $p>2$, there exists an algorithm that outputs a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment of a random-order
insertion-only stream with probability at least $\frac{2}{3}$, while using
total space (in bits)
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\right)$.

Theorem 1.1 utilizes the random-order model to improve the algorithm on
arbitrary-order insertion-only streams using
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{2}}\cdot n^{1-2/p}\right)$
space [Gan11, GW18], in terms of the dependence on $\frac{1}{\varepsilon}$. We
then give an algorithm that uses roughly the same bounds even for the two-pass
streaming model, even if the order of the updates is adversarial.

######  Theorem 1.2.

For $p>2$, there exists a two-pass streaming algorithm that outputs a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment with probability at
least $\frac{2}{3}$.

  * •

If the stream is insertion-only, the algorithm uses
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\right)$
bits of space (see Theorem 3.6).

  * •

If the steam has turnstile updates, the algorithm uses
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\right)$
bits of space (see Theorem 3.5).

Theorem 1.2 is the first algorithm to match the lower bound of
$\tilde{\Omega}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\right)$ for
multi-pass frequency moment estimation [WZ12] up to $\log n$ factors.

By contrast, we give a lower bound for $F_{p}$ estimation in the one-pass
insertion-only streaming model when the order of the updates is adversarial.

######  Theorem 1.3.

For any constant $p>2$ and parameter
$\varepsilon=\Omega\left(\frac{1}{n^{1/p}}\right)$, any one-pass insertion-
only streaming algorithm that outputs a $(1+\varepsilon)$-approximation to the
$F_{p}$ moment of an underlying frequency vector with probability at least
$\frac{9}{10}$ requires $\Omega\left(\frac{1}{\varepsilon^{2}}\cdot
n^{1-2/p}\right)$ bits of space.

Theorem 1.3 improves the lower bound of
$\Omega\left(\frac{1}{\varepsilon^{2}\log n}\cdot n^{1-2/p}\right)$ for
general insertion-only streams for $p>2$ by [Gan11]. Together, Theorem 1.1 and
Theorem 1.3 for small enough $\varepsilon>0$ show a somewhat surprising result
that random-order streams are strictly easier than arbitrary insertion-only
streams. Similarly, Theorem 1.2 and Theorem 1.3 together show that multiple
passes are strictly easier than a single pass on arbitrary insertion-only
streams.

###  1.2 Our Techniques

We first describe our random-order insertion-only algorithm. At a high level,
our algorithm interleaves the recent heavy-hitters algorithm of [BGW20] with a
subsampling procedure to estimate the contributions of various level sets
toward the frequency moment.

Approximate frequencies of heavy-hitters. The heavy-hitters algorithm of
[BGW20] partitions the updates of a random-order stream into blocks of
updates. It then randomly chooses a number of coordinates from the universe
$[n]$ to test in each block. The heavy-hitters will pass the test and
subsequently be tracked across a number of following blocks before estimates
for their frequencies are output. Due to the uniformity properties of the
random-order stream, the heavy-hitters are sufficiently “spread out”, so the
algorithm crucially outputs a $(1+\varepsilon)$-approximation to the frequency
of each heavy-hitter; algorithms with the same guarantee and space complexity
for arbitrary-order streams do not exist [Gan12].

Using level sets to estimate frequency moments. Given the subroutine for
finding $(1+\varepsilon)$-approximations to the frequencies of heavy-hitters,
we now build upon a standard subsampling approach to estimate the frequency
moment. Informally, we conceptually define the level sets so that level set
$\Lambda_{i}$ contains the coordinates $k\in[n]$ such that
$f_{k}^{p}\in\left[\frac{F_{p}}{2^{i}},\frac{2F_{p}}{2^{i}}\right]$. Since the
level sets partition the universe, it is easy to see that if we define the
contribution $C_{i}$ of a level set $\Lambda_{i}$ by the sum of the
contributions of all their coordinates,
$C_{i}:=\sum_{k\in\Lambda_{i}}f_{k}^{p}$, then $F_{p}$ is just the sum of all
the contributions of the level sets, $F_{p}=\sum_{i}C_{i}$.

[IW05] showed that the contributions of each “significant” level set can be
estimated by subsampling at exponentially smaller rates and considering the
approximate frequencies of the heavy-hitters in each of the subsamples. For
example, a single item with contribution $F_{p}$ will be detected at the top
level, while $n$ items with contribution $1$ will be detected at a subsampling
level where there are roughly $\Theta\left(\frac{1}{\varepsilon^{p}}\right)$
survivors in expectation. Crucially, $(1+\varepsilon$)-approximations to the
contribution of the surviving heavy-hitters in each subsampling level can then
be rescaled by the sampling rate to obtain “good” approximations to the
contributions of each significant level set; these very good estimates are not
available in standard subsampling schemes for arbitrary order streams.

We adapt this approach for $p>2$ to obtain Theorem 1.1. The first observation
is that an item $i$ with $f_{i}^{p}\geq\varepsilon^{2}F_{p}$ should be
identified to control the variance but also satisfies
$f_{i}^{2}\geq\varepsilon^{4/p}/n^{1-2/p}\cdot F_{2}$, so we can identify
these items using the heavy-hitter algorithm of [BGW20] with the corresponding
threshold; this induces the overall $n^{1-2/p}/\varepsilon^{4/p}$ dependency.
Moreover as we subsample, the space of the universe decreases in expectation
from $n$ to $n/2$ to $n/4$ and so forth. Thus determining the $L_{p}$-heavy
hitters at lower subsampling rates can be done using significantly less space.
We can take advantage of this by requiring that our heavy-hitter algorithm
aggressively seeks heavy-hitters with lower thresholds at lower subsampling
rates. We can thus achieve a geometric series and avoid an additional
$\mathcal{O}\left(\log n\right)$ factor in our space.

From random-order to two-pass arbitrary order. As stated, our algorithm
necessitates the random-order model so that the heavy-hitter subroutine can
output $(1+\varepsilon)$-approximations to the frequencies of heavy-hitters
across different subsampling levels; these approximations are then used to
obtain $(1+\varepsilon)$-approximations to the contributions of each level
set. The state-of-the-art heavy-hitter algorithms in insertion-only [BCI+17]
or turnstile [CCF04] streams with arbitrary arrival order do not give a
$(1+\varepsilon)$-approximation to the frequency of each heavy-hitter while
still using space dependency $\frac{1}{\varepsilon^{2}}$. Fortunately, our
approach can be remedied in two-passes over the data stream by first using a
pass to identify each of the heavy-hitters across the different subsampling
levels and then using the second pass to exactly count their frequencies; note
that since $n^{1-2/p}/\varepsilon^{4/p}\geq\frac{1}{\varepsilon^{2}}$ for
$n\geq\frac{1}{\varepsilon^{2}}$, we are still permitted space to track the
frequencies of $\min\left(n,\frac{1}{\varepsilon^{2}}\right)$ items. We can
then obtain $(1+\varepsilon)$-approximations to the contributions of each
significant level set, thus obtaining a $(1+\varepsilon)$-approximation to the
$F_{p}$ frequency moment.

Source of the separation. In summary, our improved upper bounds in both the
random-order and multi-pass models exploit each model to obtain
$(1+\varepsilon)$-approximate frequencies of the heavy-hitters in each
subsampling level. Due to the uniformity of heavy-hitters across the stream in
the random-order model, we are able to obtain $(1+\varepsilon)$-approximate
frequencies by simply tracking the frequency of the heavy-hitters within a
small block of the stream and then scaling by the entire length of the stream.
For multi-pass models, we are able to identify heavy-hitters in the first pass
and exactly track their frequencies in the second pass. By contrast, obtaining
$(1+\varepsilon)$-approximate frequencies in adversarially ordered insertion-
only streams with the same space guarantees in a single pass cannot be done
[Gan12].

Lower bound. To prove our improved lower bound, we first recall the standard
approach for showing $F_{p}$ moment estimation lower bounds in insertion-only
streams for $p>2$ that uses the multiplayer set disjointness problem, e.g.,
[BJKS04, Gan12]. In this problem, $t$ players have binary vectors of length
$n$ and the promise is that the largest coordinate in the sum of all vectors
is either (1) at most $1$ or (2) exactly $t$. For
$t=\varepsilon^{1/p}n^{1/p}$, the $F_{p}$ frequency moment of the sum of the
binary vectors differs by a factor of $(1+\varepsilon)$ between the two cases,
so that a $(1+\varepsilon)$-approximation to $F_{p}$ solves the multiplayer
set disjointness problem. The total communication complexity of the
multiplayer set disjointness problem is $\Omega\left(\frac{n}{t}\right)$ so
one of the $t$ players communicates $\Omega\left(\frac{n}{t^{2}}\right)$ bits,
and thus a lower bound of $\Omega\left(\frac{1}{\varepsilon^{2/p}}\cdot
n^{1-2/p}\right)$ follows.

To improve the $\varepsilon$ dependency in the lower bound to
$\frac{1}{\varepsilon^{2}}$, we define the $(t,\varepsilon,n)$-player set
disjointness estimation problem so that there are $t+1$ players
$P_{1},\ldots,P_{t+1}$ with private coins in the standard blackboard model.
The first $t$ players each receive a vector ${\mathbf{v}}_{s}\in\\{0,1\\}^{n}$
for $s\in[t]$, while player $P_{t+1}$ receives an index $j\in[n]$ and a bit
$c\in\\{0,1\\}$. For ${\mathbf{u}}=\sum_{s\in[t]}{\mathbf{v}}_{s}$, the inputs
are promised to satisfy $u_{i}\leq 1$ for each $i\neq j$ and either $u_{j}=1$
or $u_{j}=t$, similar to the multiparty set disjointness problem. With
probability at least $\frac{9}{10}$, $P_{t+1}$ must differentiate between the
three possible input cases (1) $u_{j}+\frac{ct}{\varepsilon}\leq t$, (2)
$u_{j}+\frac{ct}{\varepsilon}\in\left\\{\frac{t}{\varepsilon},\frac{t}{\varepsilon}+1\right\\}$,
or (3) $u_{j}+\frac{ct}{\varepsilon}=(1+\varepsilon)\frac{t}{\varepsilon}$,
where $\varepsilon\in(0,1)$. We call coordinate $j\in[n]$ the _spike_ location
and show that the $(t,\varepsilon,n)$-player set disjointness estimation
problem requires $\Omega\left(\frac{n}{t}\right)$ total communication by using
a direct sum embedding to decompose the conditional information complexity
into a sum of $n$ single coordinate problems. The intuition is that the first
$t$ players do not know the spike location, so they must effectively solve the
problem on each coordinate. We then bound the conditional information
complexity of each single coordinate problem by the Hellinger distances
between inputs for which the outputs differ. We thus apply the same reduction
and set $t=\Theta\left(\frac{1}{\varepsilon}\cdot n^{1/p}\right)$ to obtain
the desired lower bound.

We remark that the $(t,\varepsilon,n)$-player set disjointness estimation
problem can be seen as a generalization of the augmented $L_{\infty}$ promise
problem introduced by [LW13]. In the augmented $L_{\infty}$ promise problem,
there are only three players, but each coordinate in the first two players’
input vectors can be as large as $\varepsilon k$ for some fixed parameter $k$.
[LW13] used the augmented $L_{\infty}$ promise problem to give a lower bound
of $\Omega\left(\frac{\log n}{\varepsilon^{2}}\cdot n^{1-2/p}\right)$ for
$F_{p}$ moment estimation on turnstile streams. However, since their reduction
crucially allows players to use turnstile updates, we cannot adapt their
techniques to obtain a reduction for insertion-only streams.

###  1.3 Preliminaries

For a positive integer $n$, we use the notation $[n]$ to denote the set of
integers $\\{1,2,\ldots,n\\}$. For a frequency vector $f$ with dimension $n$
and $p\geq 2$, we define the $F_{p}$ moment function by
$F_{p}(f):=\sum_{k\in[n]}|f_{k}|^{p}$ and the $L_{p}$ norm of $f$ by
$L_{p}(f)=(F_{p}(f))^{1/p}$. When $f$ is defined through the updates of a
insertion-only data stream, we simply use $F_{p}$ to denote $F_{p}(f)$. Thus
for a subset $I\subseteq[n]$, the notation $F_{p}(I)$ is understood to mean
$\sum_{k\in I}f_{k}^{p}$. We also use the notation $\|f\|_{p}$ to denote the
$L_{p}$ norm of $f$. The $F_{p}$ moment estimation problem and the norm
estimation problem are often used interchangeably, as a
$(1+\varepsilon)$-approximation algorithm to one of these problems can be
modified to output a $(1+\varepsilon)$-approximation to the other using a
rescaling of $\varepsilon$, for constant $p>0$.

We use $\log$ and $\ln$ to denote the base two logarithm and natural
logarithms, respectively. We use $\operatorname*{poly}(n)$ to denote a fixed
constant degree polynomial in $n$ and $\frac{1}{\operatorname*{poly}(n)}$ to
denote some arbitrary degree polynomial in $n$ corresponding to the choice of
constants in the algorithms. We use $\operatorname*{polylog}(n)$ to denote
polylogarithmic factors of $n$.

The $L_{p}$-heavy hitters problem is to output all coordinates $i$ such that
$f_{i}\geq\varepsilon\cdot L_{p}$; such a coordinate is called a _heavy-
hitter_. The problem allows coordinates $j$ with $f_{j}\leq\varepsilon\cdot
L_{p}$ to be output, provided that $f_{j}\geq\frac{\varepsilon}{2}\cdot
L_{p}$. Moreover, each coordinate output by the algorithm must also have a
frequency estimation with additive error at most $\frac{\varepsilon}{2}\cdot
L_{p}$.

##  2 $F_{p}$ Estimation for $p>2$ in Random-Order Streams

In this section, we give our $F_{p}$ estimation algorithm for $p>2$. We first
introduce an algorithm CountHH on random-order insertion-only streams that
outputs an approximate frequency for each $L_{2}$ heavy-hitter.

######  Theorem 2.1.

[Theorem 28 in [BGW20]] There exists a one-pass algorithm CountHH on random-
order insertion-only streams that outputs a list $H$ of ordered pairs
$(j,\widehat{f_{j}})$ such that $\widehat{f_{j}}=(1\pm 2\varepsilon)f_{j}$,
for each $j\in H$, where $f$ is the underlying frequency vector. Moreover, we
have that $j\in H$ for each $j\in[n]$ with $f_{j}^{2}\geq\varepsilon^{2}\cdot
F_{2}$ and $j\not\in H$ for each $j$ with
$f_{j}^{2}\leq\frac{\varepsilon^{2}}{2}\cdot F_{2}$. The algorithm uses
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\left(\log^{2}\frac{1}{\varepsilon}+\log^{2}\log
m+\log n\right)+\log m\right)$ bits of space and succeeds with probability at
least $38/39$.

A standard heavy-hitter algorithm such as CountSketch [CCF04] or BPTree
[BCI+17] outputs each $j\in[n]$ with
$f_{j}^{2}\geq\frac{\varepsilon^{2}}{2}\cdot F_{2}$ but only finds a constant-
factor approximation to the frequency of each heavy-hitter. By comparison,
CountHH crucially uses the random-order stream to output a
$(1+\varepsilon)$-approximation to the ferquency of each heavy-hitter; we
defer the full details of the algorithm to Appendix A. We use CountHH in a
subsampling approach to approximate the contributions of each of the level
sets, defined as follows:

######  Definition 2.2 (Level sets and contribution).

Given $\widehat{F_{p}}$ such that $\widehat{F_{p}}\leq F_{p}\leq
1.01\cdot\widehat{F_{p}}$ and a uniformly random $\zeta\in[1,2]$, we define
the _level set_ $\Lambda_{i}$ for each $i\in[\log 4n]$ so that

$\Lambda_{i}:=\left\\{k\,|\,f_{k}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]\right\\}.$

Then we define the _contribution_ $C_{i}$ of level set $\Lambda_{i}$ to be
$C_{i}:=\sum_{k\in\Lambda_{i}}f_{k}^{p}$. We define the _fractional
contribution_ $\phi_{i}$ of level set $\Lambda_{i}$ to be the ratio
$\phi_{i}:=\frac{C_{i}}{\zeta\widehat{F_{p}}}$, so that $\phi_{i}\in[0,1.01]$.

For a stream of length $m=\operatorname*{poly}(n)$, let $\alpha$ be an integer
such that $2^{\alpha}>m^{p}$. We say a level set $\Lambda_{i}$ is
_significant_ if its fractional contribution $\phi_{i}$ is at least
$\frac{\varepsilon}{2\alpha\log n}$. Otherwise, we say the level set is
_insignificant_.

Observe that it suffices to obtain a multiplicative
$\left(1+\frac{\varepsilon}{2}\right)$-approximation to the contribution of
each significant level set and estimate the contributions of the insignificant
level sets to be zero, since there are at most $\alpha\log n$ level sets and
thus the total additive error from the insignificant level sets is at most
$\frac{\varepsilon}{2\alpha\log n}\cdot F_{p}\cdot\alpha\log
n=\frac{\varepsilon}{2}\cdot F_{p}$.

To estimate the contribution of each level set, we use a combination of
CountHH and subsampling to approximate the frequencies of a number of heavy-
hitters. The main idea is that subsampling induces a separate substream with a
frequency vector with a smaller $F_{p}$. Thus the items in the level sets
$\Lambda_{i}$ with small $i$ will be heavy-hitters of the frequency vector
while the items in the level sets $\Lambda_{i}$ with larger $i$ will be heavy-
hitters of the substreams with smaller sampling rates (if the items are
subsampled), due to the lower $F_{p}$ of the substreams. We can then use a
$(1+\varepsilon)$-approximation to the frequency of each sampled heavy-hitter
to estimate a $(1+\varepsilon)$-approximation to the contribution of the level
set, due to uniformity properties of random-order streams. Note that this is
where we crucially use CountHH over other possible heavy-hitter algorithms,
due to its advantage of providing $(1+\varepsilon)$-approximate frequencies in
the random-order model. We describe our algorithm for $F_{p}$ estimation with
$p>2$ for random-order insertion-only streams in Algorithm 1.

Algorithm 1 $F_{p}$ Estimation in the Random-Order Insertion-Only Model, $p>2$

1:Accuracy parameter $\varepsilon\in(0,1)$, $\widehat{F_{p}}\leq F_{p}\leq
1.01\cdot\widehat{F_{p}}$

2:$(1+\varepsilon)$-approximation to $F_{p}$.

3:Let $\zeta\in[1,2]$ be chosen uniformly at random and $\alpha$ be a positive
integer such that $2^{\alpha}>m^{p}$.

4:Let $\eta>\sum_{j\geq 0}2^{-j(p/16-1/8)}$ be a sufficiently large constant.

5:$\gamma\leftarrow 2^{11}$, $n_{i}\leftarrow\min\left(\left(\frac{16\alpha
p\log n}{\varepsilon^{1-2/p}}\right)^{(2p)/(p-2)},\frac{10\gamma
n}{2^{i}}\right)$, $\varepsilon_{i}=\frac{\varepsilon}{16\eta\cdot
2^{i(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$

6:Let $I^{r}_{i}$ be a (nested) subset of $[n]$ subsampled at rate
$p_{i}:=\min(1,2^{-i}\gamma)$.

7:Let $H^{r}_{i}$ be the output of CountHH with threshold parameter
$\frac{(\varepsilon_{i})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{i}}\right)^{1/2-1/p}$
on the substream induced by $I^{r}_{i}$.

8:for $i\in[\alpha\log n]$, $r\leq\mathcal{O}\left(\log\log n\right)$ do

9: $\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$

10: Let $S^{r}_{i}$ be the set of ordered pairs $(j,\widehat{f_{j}})$ in
$H^{r}_{\ell_{i}}$ with
$\left(\widehat{f_{j}}\right)^{p}\in\left[\frac{\zeta\widehat{F_{p}}}{2^{i}},\frac{2\zeta\widehat{F_{p}}}{2^{i}}\right]$.

11:
$\widehat{C_{i}}\leftarrow\operatorname*{median}_{r}\frac{1}{p_{\ell_{i}}}\cdot\left(\sum_{(j,\widehat{f_{j}})\in
S^{r}_{i}}\left(\widehat{f_{j}}\right)^{p}\right)$

12:return $\tilde{F_{p}}:=\sum_{i}\widehat{C_{i}}$

######  Remark 2.3.

We remark that Algorithm 1 is written requiring an input $\widehat{F_{p}}$
such that $\widehat{F_{p}}\leq F_{p}\leq 1.01\cdot\widehat{F_{p}}$ in order to
correctly index the level sets defined by Definition 2.2. Algorithm 1 can be
rewritten by setting $X=(F_{1})^{p}$ to be an upper bound on $F_{p}$ and
redefining the level sets in Definition 2.2 so that
$\Lambda_{i}:=\left\\{k\,|\,f_{k}^{p}\in\left[\frac{\zeta\cdot
X}{2^{i}},\frac{2\zeta\cdot X}{2^{i}}\right]\right\\}$. Then we again have
$F_{p}=\sum_{i}C_{i}$ across the contributions of all the level sets.

We first show that there exists a subsampling rate such that items in each
level set will be reported as a heavy-hitter if they are successfully
subsampled. Moreover, each item reported as a heavy-hitter will also be
reported with an “accurate” estimate of its frequency.

######  Lemma 2.4.

Let $\varepsilon\in(0,1)$, $\Lambda_{i}$ be a fixed level set, and let
$\ell:=\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. For a fixed
$r$, let $\mathcal{E}_{1}$ be the event that $|I^{r}_{\ell}|\leq\frac{10\gamma
n}{2^{\ell}}$ and let $\mathcal{E}_{2}$ be the event that
$F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}$. Conditioned on
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, there exists a $(j,\widehat{f_{j}})$
in $S^{r}_{i}$ for each $j\in\Lambda_{i}\cap I^{r}_{\ell}$ such that with
probability at least $\frac{7}{8}$,

$\left(1-\frac{\varepsilon}{8\alpha\log n}\right)\cdot
f_{j}^{p}\leq\left(\widehat{f_{j}}\right)^{p}\leq\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)\cdot f_{j}^{p}.$

###### Proof.

Recall that Algorithm 1 considers $H^{r}_{\ell}$ across
$r\leq\mathcal{O}\left(\log\log n\right)$ independent subsamples of $[n]$, to
construct $\widehat{C_{i}}$ by subsampling at rate
$p_{\ell}:=\min(1,2^{-\ell}\gamma)$.

Suppose $2^{i}\cdot\varepsilon^{2}<\gamma$, so that
$\ell:=\ell_{i}=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}\leq\log\gamma$
since $\varepsilon_{k}\leq\varepsilon$ for all $k$. Then
$p_{\ell}=\min(1,2^{-\ell}\gamma)=1$ and all items are subsampled, i.e.,
$H^{r}_{\ell}=[n]$. By Definition 2.2 of the level sets, each item
$j\in\Lambda_{i}$ satisfies
$f_{j}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$.
Since $\varepsilon^{2}\geq\frac{1}{2^{i}}$, then we have
$f_{j}^{p}\geq\varepsilon^{2}\cdot\widehat{F_{p}}$. We also have
$\widehat{F_{p}}\leq F_{p}\leq 1.01\cdot\widehat{F_{p}}$ and $n^{1/2-1/p}\cdot
F_{p}^{1/p}\geq F_{2}^{1/2}$. Thus, each item in $j\in\Lambda_{i}$ satisfies

$f_{j}\geq\frac{\varepsilon^{2/p}}{1.01^{1/p}}\cdot
F_{p}^{1/p}\geq\frac{\varepsilon^{2/p}}{1.01^{1/p}n^{1/2-1/p}}\cdot
F_{2}^{1/2},$

so that $f_{j}^{2}\geq\frac{\varepsilon^{4/p}}{1.01n^{1-2/p}}F_{2}$. Then by
Theorem 2.1, each item $j\in\Lambda_{i}$ corresponds to some estimate
$\left(\widehat{f_{j}}\right)^{2}$ reported by $H^{r}_{\ell}$ output by
CountHH with threshold $\frac{(\varepsilon_{\ell})^{2/p}}{80\gamma}$, as
$\varepsilon_{\ell}\leq\varepsilon$ and $n_{\ell}=n$. Hence,
$\widehat{f_{j}^{p}}$ is a $\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)$-approximation to $f_{j}^{p}$. Furthermore, CountHH rounds the
estimate of the frequency of each heavy-hitter to the nearest power of
$\left(1+\frac{\varepsilon}{16p\alpha\log n}\right)$. Hence,
$\widehat{f_{j}^{p}}$ is a $\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)$-approximation to $f_{j}^{p}$.

Now suppose $2^{i}\cdot\varepsilon^{2}\geq\gamma$, so that
$\ell:=\ell_{i}=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}\geq\log\gamma$
and $p_{\ell}:=\min(1,2^{-\ell}\gamma)\geq\frac{\gamma}{2\cdot
2^{i}\varepsilon_{\ell}^{2}}$. Again by Definition 2.2 of the level sets, each
item $j\in\Lambda_{i}$ satisfies
$f_{j}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$.
Now if $j\notin I^{r}_{\ell}$, then it will not be reported by CountHH. Thus
we assume that $j\in I^{r}_{\ell}$.

Conditioning on the event $\mathcal{E}_{2}$, we have that

$F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}\leq\frac{20\gamma
F_{p}}{2^{i}\varepsilon^{2}}.$

Since $\widehat{F_{p}}\leq F_{p}\leq 1.01\cdot\widehat{F_{p}}$, then we have
that $f_{j}^{p}\geq\frac{\varepsilon^{2}}{80\gamma}\cdot F_{p}(I^{r}_{\ell})$
and thus

$f_{j}\geq\frac{\varepsilon^{2/p}}{(80\gamma)^{1/p}}\cdot
F_{p}^{1/p}(I^{r}_{\ell}).$

Instead of applying the inequality $n^{1/2-1/p}\cdot F_{p}^{1/p}\geq
F_{2}^{1/2}$, we note that conditioning on the event $\mathcal{E}_{1}$, we
have that $|I^{r}_{\ell}|\leq n_{\ell}=\frac{10\gamma n}{2^{\ell}}$. Hence,
the frequency vector defined by the substream $I^{r}_{\ell}$ potentially has
much smaller support size than $n$. Thus we have

$f_{j}\geq\frac{\varepsilon^{2/p}}{(80\gamma)^{1/p}}\cdot\left(\frac{1}{n_{\ell}}\right)^{1/2-1/p}\cdot
F_{2}^{1/2}(I^{r}_{\ell}).$

By Theorem 2.1, each item $j\in\Lambda_{i}\cap I^{r}_{\ell}$ corresponds to
some estimate $\widehat{f_{j}}$ reported by $H^{r}_{\ell}$ output by CountHH
with threshold
$\frac{(\varepsilon_{\ell})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{\ell}}\right)^{1/2-1/p}$,
since $\varepsilon_{\ell}\leq\varepsilon$. Moreover, the estimate of the
frequency of each heavy-hitter reported by CountHH is within a factor of
$\left(1+\frac{\varepsilon}{16p\alpha\log n}\right)$ of the true frequency,
since $n_{i}\geq\left(\frac{16\alpha p\log
n}{\varepsilon^{1-2/p}}\right)^{(2p)/(p-2)}$ implies that the threshold is at
most $\frac{\varepsilon}{16p\alpha\log n}$. Hence for sufficiently small
$\varepsilon$, $\left(\widehat{f_{j}}\right)^{p}$ is a
$\left(1+\frac{\varepsilon}{8\alpha\log n}\right)$-approximation to
$f_{j}^{p}$. ∎

In summary, an item $k\in\Lambda_{i}$ may not always be sampled by
$I^{r}_{\ell}$, but CountHH outputs a quantity $\widehat{f_{k}}$ such that
$\left(\widehat{f_{k}}\right)^{p}$ is a
$\left(1+\frac{\varepsilon}{8\alpha\log n}\right)$-approximation to
$f_{k}^{p}$ if $k\in I^{r}_{\ell}$.

These approximations allow us to recover a $(1+\varepsilon)$-approximation to
the $F_{p}$ moment through Lemma 2.5, which is our main correctness statement
and which we now show. Lemma 2.5 claims that the output $\tilde{F_{p}}$ of our
algorithm serves as a $(1+\varepsilon)$-approximation to the $F_{p}$ moment of
the underlying frequency vector. The proof of Lemma 2.5 first considers an
idealized process and shows that we obtain “good” approximations to the
contributions of each significant level set. Since the contributions of the
insignificant level sets can be ignored, we thereby obtain a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment. We then show that when
the process is not idealized, the estimate $\tilde{F_{p}}$ only occurs a small
error and thus still guarantees a $(1+\varepsilon)$-approximation to the
$F_{p}$ moment.

######  Lemma 2.5.

With probability at least $\frac{2}{3}$, we have that
$|\tilde{F_{p}}-F_{p}|\leq\varepsilon\cdot F_{p}$.

###### Proof.

Let $\Lambda_{i}$ be a fixed level set and let
$\ell:=\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. Let
$k\in\Lambda_{i}\cap S^{r}_{\ell}$, so that
$f_{k}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$
and $k$ is subsampled at the level in which its estimated frequency
$\left(\widehat{f_{k}}\right)^{p}$ is used to estimate the contribution
$C_{i}$ of level set $\Lambda_{i}$. Then Lemma 2.4 shows that we obtain an
estimate $\left(\widehat{f_{k}}\right)^{p}$ such that

$\left(1-\frac{\varepsilon}{8\alpha\log n}\right)\cdot
f_{k}^{p}\leq\left(\widehat{f_{k}}\right)^{p}\leq\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)\cdot f_{k}^{p},$

with constant probability. In an idealized process, we would have

$\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}}\leq\left(\widehat{f_{k}}\right)^{p}\leq\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}},$

so that the estimate $\left(\widehat{f_{k}}\right)^{p}$ is used toward the
estimation $\widehat{C_{i}}$ of contribution $C_{i}$ of level set
$\Lambda_{i}$. However, this may not always be the case because the value of
$f_{k}^{p}$ may be near the boundary of the interval
$\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$
and the value of the estimate $\left(\widehat{f_{k}}\right)^{p}$ may lie
outside of the interval, so that the estimate
$\left(\widehat{f_{k}}\right)^{p}$ is used toward the estimation of some other
level set $\Lambda_{i^{\prime}}$. We first analyze an idealized process, so
that $\left(\widehat{f_{k}}\right)^{p}$ is correctly classified for all $k$
across all level sets, and show that the output is a
$(1+\mathcal{O}\left(\varepsilon\right))$-approximation to $F_{p}$. We then
argue that because we randomize the boundaries of each interval due to the
selection of $\zeta$, the overall guarantee is only slightly worsened but
remains a $(1+\varepsilon)$-approximation to $F_{p}$.

Idealized process. We first show that for an idealized process where
$\left(\widehat{f_{k}}\right)^{p}$ is correctly classified for all $k$ across
all level sets, then for a fixed level set $i$, we have
$|\widehat{C_{i}}-C_{i}|\leq\frac{\varepsilon_{\ell}}{2}\cdot F_{p}$ with
probability at least $1-\frac{1}{\operatorname*{polylog}(n)}$. Let
$\mathcal{E}_{1}$ be the event that $|I^{r}_{\ell}|\leq\frac{10\gamma
n}{2^{\ell}}$ and let $\mathcal{E}_{2}$ be the event that
$F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}$. Lemma 2.4 shows that
conditioned on $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, then CountHH outputs a
$\left(1+\frac{\varepsilon}{8\alpha\log n}\right)$-approximation to
$f_{k}^{p}$ if $k\in I^{r}_{\ell}$. We thus analyze the approximation
$\widehat{C^{r}_{i}}$ to $C_{i}$ for a given set of subsamples, where we
define

$\widehat{C^{r}_{i}}:=\frac{1}{p_{\ell_{i}}}\cdot\sum_{(k,\widehat{f_{k}})\in
S^{r}_{i}}\left(\widehat{f_{k}}\right)^{p},$

so that $\widehat{C_{i}}=\operatorname*{median}_{r}\widehat{C^{r}_{i}}$.
Conditioned on $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, we note that
$\widehat{C^{r}_{i}}$ is a $\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)$-approximation to

$D^{r}_{i}:=\frac{1}{p_{\ell_{i}}}\cdot\sum_{k\in
S^{r}_{i}\cap\Lambda_{i}}f_{k}^{p}.$

We thus analyze the expectation and variance of $D^{r}_{i}$.

We first analyze the expectation of $D^{r}_{i}$. Note that

$\mathbb{E}\left[D^{r}_{i}\right]=\frac{1}{p_{\ell}}\cdot\sum_{k\in\Lambda_{i}}p_{\ell}\cdot
f_{k}^{p}=C_{i}.$

We next analyze the variance of $D^{r}_{i}$, which results from whether items
$k\in\Lambda_{i}$ are sampled by $I^{r}_{\ell}$. Since
$p_{\ell}\geq\frac{\gamma}{2\cdot 2^{i}\varepsilon_{\ell}^{2}}$, we have

$\operatorname*{Var}(D^{r}_{i})=\frac{1}{p^{2}_{\ell}}\cdot\sum_{k\in\Lambda_{i}}p_{\ell}f_{k}^{2p}\leq\sum_{k\in\Lambda_{i}}\frac{2\cdot
2^{i}\varepsilon_{\ell}^{2}}{\gamma}\cdot f_{k}^{2p}.$

Observe that for each $k\in\Lambda_{i}$, we have
$f_{k}^{2p}\leq\frac{16(F_{p})^{2}}{2^{2i}}$ and
$\frac{|\Lambda_{i}|}{2^{i}}\leq\phi_{i}\leq 1$. Thus for $\gamma=2^{11}$,

$\operatorname*{Var}(D^{r}_{i})\leq|\Lambda_{i}|\cdot\frac{2\cdot
2^{i}\varepsilon_{\ell}^{2}}{\gamma}\cdot\frac{16(F_{p})^{2}}{2^{2i}}\leq\phi_{i}\varepsilon_{\ell}^{2}(F_{p})^{2}\leq\frac{\varepsilon_{\ell}^{2}}{64}(F_{p})^{2}.$

Hence, by Chebyshev’s inequality, we have that

$\mathbf{Pr}\left[|D^{r}_{i}-C_{i}|\geq\frac{\varepsilon_{\ell}}{2}\cdot
F_{p}\right]\leq\frac{1}{16}.$

Since $C_{i}\leq F_{p}$ and $\widehat{C^{r}_{i}}$ is a
$\left(1+\frac{\varepsilon}{8\alpha\log n}\right)$-approximation to
$D^{r}_{i}$, then $\widehat{C^{r}_{i}}$ gives an approximation to $C_{i}$ with
additive error at most $\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}$ with probability at least
$\frac{15}{16}$, conditioned on the events $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$, and the correctness of the subroutine CountHH. By Theorem
2.1, the correctness of CountHH occurs with probability at least
$\frac{38}{39}$. By a union bound, we have that conditioned on
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, then

$\mathbf{Pr}\left[|\widehat{C^{r}_{i}}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}\right]\geq\frac{7}{8}.$

For a fixed $r$, let $\mathcal{E}_{1}$ be the event that
$|I^{r}_{\ell}|\leq\frac{10\gamma n}{2^{\ell}}$ and let $\mathcal{E}_{2}$ be
the event that $F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}$.
Recall that $I^{r}_{\ell}$ is a nested subset of $[n]$ subsampled at rate
$p_{\ell}:=\min(1,2^{-\ell}\gamma)$. Thus we have
$\mathbb{E}\left[|I^{r}_{\ell}|\right]\leq\frac{\gamma n}{2^{\ell}}$, so that
by Markov’s inequality, we have that
$\mathbf{Pr}\left[\mathcal{E}_{1}\right]\geq\frac{9}{10}$. Similarly, we have
$\mathbb{E}\left[F_{p}(I^{r}_{\ell})\right]\leq\frac{\gamma F_{p}}{2^{\ell}}$,
so that by Markov’s inequality, we have that
$\mathbf{Pr}\left[\mathcal{E}_{2}\right]\geq\frac{9}{10}$. Hence by a union
bound,
$\mathbf{Pr}\left[\mathcal{E}_{1}\wedge\mathcal{E}_{2}\right]\geq\frac{8}{10}$.

By Lemma 2.4, conditioned on the events $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$, we have that
$|\widehat{C^{r}_{i}}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}$ for a fixed $r$, with probability at
least $\frac{7}{8}$. Thus by a union bound, we have that
$|\widehat{C^{r}_{i}}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}$ for a fixed $r$, with probability at
least $\frac{5}{8}$. Since
$\widehat{C_{i}}=\operatorname*{median}_{r}\widehat{C^{r}_{i}}$ across
$r\leq\mathcal{O}\left(\log\log n\right)$ iterations, then we have that
$|\widehat{C_{i}}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}$ with probability at least
$1-\frac{1}{\operatorname*{polylog}(n)}$.

By a union bound over the $\alpha\log n$ level sets, then with probability at
least $1-\frac{1}{\operatorname*{polylog}(n)}$, we have that
$|\widehat{C_{i}}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell_{i}}\right)\cdot F_{p}$ simultaneously for all
$i\in[\alpha\log n]$, where
$\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. We form our
estimate $\tilde{F_{p}}$ to $F_{p}$ by setting
$\tilde{F_{p}}:=\sum_{i}\widehat{C_{i}}$ and we have $F_{p}=\sum_{i}C_{i}$.
Since $i\in[\alpha\log n]$,
$\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$, and
$\varepsilon_{\ell_{i}}=\frac{\varepsilon}{16\eta\cdot
2^{\ell_{i}(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$, then

$\displaystyle|\tilde{F_{p}}-F_{p}|$
$\displaystyle=\left|\sum_{i}\widehat{C_{i}}-\sum_{i}C_{i}\right|\leq\sum_{i}|\widehat{C_{i}}-C_{i}|\leq\sum_{i}\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell_{i}}\right)\cdot F_{p}$
$\displaystyle\leq\sum_{i\in[\alpha\log n]}\frac{\varepsilon}{4\alpha\log
n}\cdot
F_{p}+\sum_{i:\ell_{i}\leq\log\frac{1}{\varepsilon^{2}}}\varepsilon_{\ell_{i}}\cdot
F_{p}+\sum_{i:\ell_{i}>\log\frac{1}{\varepsilon^{2}}}\varepsilon_{\ell_{i}}\cdot
F_{p}$ $\displaystyle\leq\frac{\varepsilon}{4}\cdot
F_{p}+\log\frac{1}{\varepsilon^{2}}\cdot\frac{\varepsilon}{16\log\frac{1}{\varepsilon^{2}}}\cdot
F_{p}+\frac{\varepsilon}{16}\cdot F_{p},$

where the last bound on the last term follows from $\eta>\sum_{j\geq
0}2^{-j(p/16-1/8)}$. Thus we have that
$|\tilde{F_{p}}-F_{p}|\leq\frac{\varepsilon}{2}\cdot F_{p}$ with probability
at least $1-\frac{1}{\operatorname*{polylog}(n)}$ in an idealized process.

Effects of randomized boundaries. We say that for a fixed $r$, an item
$k\in[n]$ is _misclassified_ if there exists a level set $\Lambda_{i}$ such
that

$\frac{\zeta\cdot F_{p}}{2^{i}}\leq f_{k}^{p}\leq\frac{2\zeta\cdot
F_{p}}{2^{i}},$

but for an estimate $\left(\widehat{f_{k}}\right)^{p}$ output by CountHH on
the set $S^{r}_{\ell_{i}}$, we have

$\frac{\zeta\cdot
F_{p}}{2^{i}}\leq\left(\widehat{f_{k}}\right)^{p}\leq\frac{2\zeta\cdot
F_{p}}{2^{i}}.$

Recall that by Lemma 2.4, we have for any fixed value of $\zeta$ that

$\left(1-\frac{\varepsilon}{8\alpha\log n}\right)\cdot
f_{k}^{p}\leq\left(\widehat{f_{k}}\right)^{p}\leq\left(1+\frac{\varepsilon}{8\alpha\log
n}\right)\cdot f_{k}^{p}.$

Since $\zeta\in[1,2]$, then the probability that item $k\in[n]$ is
misclassified is at most $\frac{\varepsilon}{2\alpha\log n}$. Moreover, in the
event that item $k\in\Lambda_{i}$ is misclassified, it can only be
misclassified into either level set $\Lambda_{i+1}$ or level set
$\Lambda_{i-1}$, since $\left(\widehat{f_{k}}\right)^{p}$ is a
$\left(1\pm\frac{\varepsilon}{8\alpha\log n}\right)$ multiplicative
approximation to $f_{k}^{p}$.

Thus in the event that item $k\in[n]$ is misclassified, then
$\left(\widehat{f_{k}}\right)^{p}$ will be rescaled by an incorrect
probability, but only by at most a factor of two. Hence the error in the
computation of the contribution of $f_{k}^{p}$ to some level set $\Lambda_{i}$
is at most $2f_{k}^{p}$. Then in expectation across all $k\in[n]$, the error
due to the misclassification is at most
$2F_{p}\cdot\frac{\varepsilon}{2\alpha\log n}=\frac{\varepsilon}{\alpha\log
n}\cdot F_{p}$. Hence by Markov’s inequality for sufficiently large $n$, the
misclassification error is at most an additive $\frac{\varepsilon}{2}\cdot
F_{p}$ with probability at least $\frac{3}{4}$. Therefore in total, we have
that $|\tilde{F_{p}}-F_{p}|\leq\varepsilon\cdot F_{p}$ with probability at
least $\frac{2}{3}$. ∎

It remains to analyze the space complexity of the algorithm as well as remove
some additional unnecessary assumptions. See 1.1

###### Proof.

We first observe that we only require a $1.01$-approximation $\widehat{F_{p}}$
to $F_{p}$ as the input of Algorithm 1 to create the level sets and analyze
accordingly. However, we can instead define the level sets using any upper
bound $X$ on $\widehat{F_{p}}$ by setting level set $\Lambda_{i}$ to be the
indices $k\in[n]$ for which $f_{k}^{p}\in\left[\frac{\zeta
X}{2^{i}},\frac{2\zeta X}{2^{i}}\right]$, rather than
$\left[\frac{\zeta\widehat{F_{p}}}{2^{i}},\frac{2\zeta\widehat{F_{p}}}{2^{i}}\right]$,
and the same analysis will follow (see Remark 2.3). Intuitively, the fluidity
of the definition of the level sets can be seen from the fact that we
randomize the boundaries by going through a multiplicative $\zeta$ chosen
randomly from $[1,2]$ anyway, and additional empty level sets will not change
the approximation guarantee. Thus by Lemma 2.5, there exists an algorithm that
outputs a $(1+\varepsilon)$-approximation to the $F_{p}$ moment.

It remains to analyze the space complexity. By Theorem 2.1, CountHH with
threshold $\varepsilon$ requires
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\left(\log^{2}\frac{1}{\varepsilon}+\log^{2}\log
m+\log n\right)+\log m\right)$ bits of space. Algorithm 1 runs a separate
instance of CountHH with threshold
$\frac{(\varepsilon_{i})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{i}}\right)^{1/2-1/p}$
to output a set $H^{r}_{i}$ for $r\leq\mathcal{O}\left(\log\log n\right)$,
where $\gamma$ is a sufficiently large constant. Thus the total space for the
CountHH instances across all $i$ for a fixed $r$ is at most

$C_{1}\log n+\left(C_{1}^{2}\log n\right)\cdot\sum_{i\in[\alpha\log
n]}\frac{C_{1}(n_{i})^{1-2/p}}{(\varepsilon_{i})^{4/p}},$

for some positive constants $C_{1},\alpha>0$. In particular, we have
$\varepsilon_{i}=\frac{\varepsilon}{16\eta\cdot
2^{i(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$ and
$n_{i}=\min\left(\left(\frac{16\alpha p\log
n}{\varepsilon^{1-2/p}}\right)^{(2p)/(p-2)},\frac{10\gamma n}{2^{i}}\right)$
for a sufficiently large constant $\eta$. Then the total space for the CountHH
instances across all $i$ for a fixed $r$ is at most

$C_{1}\log n+\left(C_{1}\log^{2}n\right)\cdot\sum_{i=1}^{\alpha\log
n}\left(\frac{C_{2}n^{1-2/p}}{\varepsilon^{4/p}}\cdot\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}}\log^{2}\frac{1}{\varepsilon}+\frac{C_{2}\log^{2}n}{\varepsilon^{2}}\right),$

for some positive constants $C_{1},C_{2}>0$. Observe that
$\sum_{i=1}^{\infty}\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}}=\sum_{i=1}^{\infty}\frac{1}{2^{3i(1-2/p)/4}}$
is a geometric series that is upper bounded by an absolute constant. Hence,
the total space across all $i$ for a fixed $r$ is at most
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\log^{2}n\log^{2}\frac{1}{\varepsilon}+\frac{1}{\varepsilon^{2}}\log^{5}n\right)$
and the total space across all $r\leq\mathcal{O}\left(\log\log n\right)$ is

$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\log^{2}n\log^{2}\frac{1}{\varepsilon}\log\log
n+\frac{1}{\varepsilon^{2}}\log^{5}n\log\log n\right),$

which is $\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\right)$ space in total, since $n\geq\frac{1}{\varepsilon^{2}}$
implies $\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\geq\frac{1}{\varepsilon^{2}}$. ∎

##  3 $F_{p}$ Estimation for $p>2$ in Two-Pass Streams

In this section, we consider two-pass algorithms for $F_{p}$ estimation, with
$p>2$. For turnstile streams, we require the guarantees of the well-known
CountSketch algorithm for finding heavy-hitters.

######  Theorem 3.1.

[CCF04] There exists an algorithm CountSketch that reports all items $i\in[n]$
such that $f_{i}\geq\varepsilon L_{2}$ and no items $j\in[n]$ such that
$f_{j}\leq\frac{\varepsilon}{2}\cdot L_{2}$ in the turnstile streaming
algorithm. The algorithm uses
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\log^{2}n\right)$ bits of space and
succeeds with probability $1-\frac{1}{\operatorname*{poly}(n)}$.

For insertion-only streams, we use the more space-efficient BPTree algorithm
for finding heavy-hitters.

######  Theorem 3.2.

[BCI+17] There exists an algorithm BPTree that reports all items $i\in[n]$
such that $f_{i}\geq\varepsilon L_{2}$ and no items $j\in[n]$ such that
$f_{j}\leq\frac{\varepsilon}{2}\cdot L_{2}$ in the turnstile streaming
algorithm. The algorithm uses $\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\log
n\right)$ bits of space and succeeds with probability $0.99$.

Recall that the main idea of our one-pass algorithm in the random-order
insertion-only streaming model was to subsample at different rates and find
$(1+\varepsilon)$-approximations to the frequencies of the heavy-hitters in
each subsampling rate, which are then used to form estimates of the
contributions of each level set and ultimately estimate of the frequency
moment. The random-order setting crucially allowed us to obtain
$(1+\varepsilon)$-approximations to the frequencies of the heavy-hitters. By
contrast, in an adversarial-order setting, by the time a possible heavy-hitter
is detected, a significant fraction of its frequency may have already appeared
in the stream if we use a heavy-hitter algorithm with space dependency
$\frac{1}{\varepsilon^{2}}$. Fortunately, in a two-pass setting, we can use
the first pass to identify possible heavy-hitters and the second pass to find
their frequencies. We give the full details in Algorithm 2, where the
subroutine HeavyHitters denotes the algorithm CountSketch of Theorem 3.1 for
turnstile streams and BPTree of Theorem 3.2 for insertion-only streams.

Algorithm 2 $F_{p}$ Estimation on Two-Pass Streams, $p>2$

1:Accuracy parameter $\varepsilon\in(0,1)$, $\widehat{F_{p}}\leq F_{p}\leq
1.01\cdot\widehat{F_{p}}$

2:$(1+\varepsilon)$-approximation to $F_{p}$

3:Let $\eta>\sum_{j\geq 0}2^{-j(p/16-1/8)}$ be a sufficiently large constant.

4:$\gamma\leftarrow 2^{11}$, $n_{i}\leftarrow\frac{10\gamma n}{2^{i}}$,
$\varepsilon_{i}=\frac{\varepsilon}{16\eta\cdot
2^{i(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$

5:Let $I^{r}_{i}$ be a (nested) subset of $[n]$ subsampled at rate
$p_{i}:=\min(1,2^{-i}\gamma)$.

6:for first pass $i\in[\alpha\log n]$, $r\leq\mathcal{O}\left(\log\log
n\right)$: do

7: Let $H^{r}_{i}$ be the output of HeavyHitters with threshold parameter
$\frac{(\varepsilon_{i})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{i}}\right)^{1/2-1/p}$
on the substream induced by $I^{r}_{i}$.

8:for second pass do

9: Track the frequency $f_{k}$ for any coordinate $k\in\cup H^{r}_{i}$.

10: Let $S^{r}_{i}$ be the items $k\in[n]$ with
$f_{k}^{p}\in\left[\frac{\widehat{F_{p}}}{2^{i}},\frac{2\widehat{F_{p}}}{2^{i}}\right]$.

11: $\ell_{i}\leftarrow\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$

12: $D^{r}_{i}\leftarrow\frac{1}{p_{\ell_{i}}}\cdot\left(\sum_{k\in
S^{r}_{i}}f_{k}^{p}\right)$

13: $\widehat{C_{i}}\leftarrow\operatorname*{median}_{r}D^{r}_{i}$

14:return $\tilde{F_{p}}:=\sum_{i}\widehat{C_{i}}$

Using CountSketch as the subroutine for HeavyHitters on two-pass turnstile
streams and BPTree as the subroutine for HeavyHitters on two-pass insertion-
only streams, we obtain the following guarantees for Algorithm 2. We first
show that there exists a subsampling rate such that items in each level set
will be reported as a heavy-hitter. The proof is similar to the proof of Lemma
2.4, but we no longer require each reported item to also be reported with a
$(1+\varepsilon)$-approximation to their frequency. In fact, this cannot be
done in a single pass; we will instead track their frequencies in the second
pass.

######  Lemma 3.3.

Let $\varepsilon\in(0,1)$, $\Lambda_{i}$ be a fixed level set, and let
$\ell:=\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. For a fixed
$r$, let $\mathcal{E}_{1}$ be the event that $|I^{r}_{\ell}|\leq\frac{10\gamma
n}{2^{\ell}}$ and let $\mathcal{E}_{2}$ be the event that
$F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}$. Conditioned on
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, then HeavyHitters reports $j\in
S^{r}_{i}$ for each $j\in\Lambda_{i}\cap I^{r}_{\ell}$ with probability at
least $1-\frac{1}{\operatorname*{poly}(n)}$.

###### Proof.

We consider casework on the value of $i$. First suppose
$2^{i}\cdot\varepsilon^{2}<\gamma$, so that
$\ell:=\ell_{i}=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}\leq\log\gamma$
since $\varepsilon_{k}\leq\varepsilon$ for all $k$. By Definition 2.2 of the
level sets, each item $j\in\Lambda_{i}$ satisfies
$f_{j}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$.
We also have $\widehat{F_{p}}\leq F_{p}\leq 1.01\cdot\widehat{F_{p}}$ and
$n^{1/2-1/p}\cdot F_{p}^{1/p}\geq F_{2}^{1/2}$. Thus, each item in
$j\in\Lambda_{i}$ satisfies

$f_{j}\geq\frac{\varepsilon^{2/p}}{1.01^{1/p}}\cdot
F_{p}^{1/p}\geq\frac{\varepsilon^{2/p}}{1.01^{1/p}n^{1/2-1/p}}\cdot
F_{2}^{1/2},$

so that $f_{j}^{2}\geq\frac{\varepsilon^{4/p}}{1.01n^{1/2-1/p}}F_{2}$. Then by
Theorem 3.1 or Theorem 3.2, each item $j\in\Lambda_{i}$ is reported by
CountSketch or BPTree with threshold
$\frac{(\varepsilon_{\ell})^{2/p}}{80\gamma}$, as
$\varepsilon_{\ell}\leq\varepsilon$ and $n_{\ell}=n$.

Otherwise, suppose $2^{i}\cdot\varepsilon^{2}\geq\gamma$, so that
$\ell:=\ell_{i}=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}\geq\log\gamma$
and $p_{\ell}:=\min(1,2^{-\ell}\gamma)\geq\frac{\gamma}{2\cdot
2^{i}\varepsilon_{\ell}^{2}}$. Again by Definition 2.2 of the level sets, each
item $j\in\Lambda_{i}$ satisfies
$f_{j}^{p}\in\left[\frac{\zeta\cdot\widehat{F_{p}}}{2^{i}},\frac{2\zeta\cdot\widehat{F_{p}}}{2^{i}}\right]$.
If $j\notin I^{r}_{\ell}$, then $j$ certainly will not be reported by
HeavyHitters (regardless of whether HeavyHitters is CountSketch or BPTree).
Hence, we assume that $j\in I^{r}_{\ell}$.

Conditioning on the event $\mathcal{E}_{2}$,

$F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}\leq\frac{20\gamma
F_{p}}{2^{i}\varepsilon^{2}}.$

Given $\widehat{F_{p}}\leq F_{p}\leq 1.01\cdot\widehat{F_{p}}$, then
$f_{j}^{p}\geq\frac{\varepsilon^{2}}{80\gamma}\cdot F_{p}(I^{r}_{\ell})$.
Therefore,

$f_{j}\geq\frac{\varepsilon^{2/p}}{(80\gamma)^{1/p}}\cdot
F_{p}^{1/p}(I^{r}_{\ell}).$

Rather than applying the inequality $n^{1/2-1/p}\cdot F_{p}^{1/p}\geq
F_{2}^{1/2}$, we observe that conditioning on the event $\mathcal{E}_{1}$, it
follows that $|I^{r}_{\ell}|\leq n_{\ell}=\frac{10\gamma n}{2^{\ell}}$. Thus,
the frequency vector defined by the substream $I^{r}_{\ell}$ has significantly
smaller support size than $n$, which we can leverage to use a heavy-hitter
algorithm with a lower threshold. We have

$f_{j}\geq\frac{\varepsilon^{2/p}}{(80\gamma)^{1/p}}\cdot\left(\frac{1}{n_{\ell}}\right)^{1/2-1/p}\cdot
F_{2}^{1/2}(I^{r}_{\ell}).$

Therefore by Theorem 3.1 or Theorem 3.2, each item $j\in\Lambda_{i}\cap
I^{r}_{\ell}$ will be reported by $H^{r}_{\ell}$ output by HeavyHitters with
threshold
$\frac{(\varepsilon_{\ell})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{\ell}}\right)^{1/2-1/p}$,
since $\varepsilon_{\ell}\leq\varepsilon$. ∎

We now show our main correctness statement for our two-pass algorithms. Lemma
3.4 proves that the output $\tilde{F_{p}}$ of our algorithm gives a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment of the underlying
frequency vector. Although the guarantees of Lemma 3.4 are similar to the
guarantees of Lemma 2.5 are similar, the proof of Lemma 3.4 is much simpler.
We show that we obtain $(1+\varepsilon)$-approximations to the contributions
of each significant level set, thus obtaining a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment, since the contributions
of the insignificant level sets can be ignored. Unlike Lemma 2.5, we need not
concern about an idealized process since the frequency of each heavy-hitter is
exactly tracked in the second pass of the algorithm over the data stream, so
no heavy-hitters can be accidentally misclassified into an incorrect level
set.

######  Lemma 3.4.

With probability at least $\frac{2}{3}$, we have that
$|\tilde{F_{p}}-F_{p}|\leq\varepsilon\cdot F_{p}$.

###### Proof.

Let $\Lambda_{i}$ be a fixed level set and
$\ell:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. Let $\mathcal{E}_{1}$
be the event that $|I^{r}_{\ell}|\leq\frac{10\gamma n}{2^{\ell}}$ and let
$\mathcal{E}_{2}$ be the event that $F_{p}(I^{r}_{\ell})\leq\frac{10\gamma
F_{p}}{2^{\ell}}$. By Lemma 3.3, CountSketch returns each $k\in\Lambda_{i}\cap
I^{r}_{\ell}$ in $S^{r}_{i}$, conditioned on $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$. Thus in the second pass, Algorithm 2 tracks the
contribution $f_{k}^{p}$ explicitly, by tracking $f_{k}$. We first analyze the
approximation $\widehat{C^{r}_{i}}$ to $C_{i}$ for a given set of subsamples,
where we define

$D^{r}_{i}:=\frac{1}{p_{\ell}}\cdot\sum_{k\in\Lambda_{i}\cap
I^{r}_{\ell}}f_{k}^{p}.$

so that $\widehat{C_{i}}=\operatorname*{median}_{r}D^{r}_{i}$. Conditioned on
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, we note that

$\mathbb{E}\left[D^{r}_{i}\right]=\frac{1}{p_{\ell}}\cdot\sum_{k\in\Lambda_{i}}p_{\ell}\cdot
f_{k}^{p}=C_{i}.$

We also have

$\operatorname*{Var}(D^{r}_{i})=\frac{1}{p^{2}_{\ell}}\cdot\sum_{k\in\Lambda_{i}}p_{\ell}f_{k}^{2p}\leq\sum_{k\in\Lambda_{i}}\frac{2\cdot
2^{i}\varepsilon_{\ell}^{2}}{\gamma}\cdot f_{k}^{2p},$

since $p_{\ell}\geq\frac{\gamma}{2\cdot 2^{i}\varepsilon_{\ell}^{2}}$. Observe
that for each $k\in\Lambda_{i}$, we have
$f_{k}^{2p}\leq\frac{16(F_{p})^{2}}{2^{2i}}$ and
$\frac{|\Lambda_{i}|}{2^{i}}\leq\phi_{i}\leq 1$. Thus for $\gamma=2^{11}$,

$\operatorname*{Var}(D^{r}_{i})\leq|\Lambda_{i}|\cdot\frac{2\cdot
2^{i}\varepsilon_{\ell}^{2}}{\gamma}\cdot\frac{16(F_{p})^{2}}{2^{2i}}\leq\phi_{i}\varepsilon_{\ell}^{2}(F_{p})^{2}\leq\frac{\varepsilon_{\ell}^{2}}{64}(F_{p})^{2}.$

Hence, by Chebyshev’s inequality, we have that

$\mathbf{Pr}\left[|D^{r}_{i}-C_{i}|\geq\frac{\varepsilon_{\ell}}{2}\cdot
F_{p}\right]\leq\frac{1}{16}.$

In summary, $D^{r}_{i}$ gives an approximation to $C_{i}$ with additive error
at most $\frac{\varepsilon_{\ell}}{2}\cdot F_{p}$ with probability at least
$\frac{15}{16}$, conditioned on the events $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$, and the correctness of the subroutine CountSketch. Since
CountSketch fails with probability at most
$1-\frac{1}{\operatorname*{poly}(n)}$ by Theorem 3.1, then by a union bound,
we have that conditioned on $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$,

$\mathbf{Pr}\left[|D^{r}_{i}-C_{i}|\leq\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell}\right)\cdot F_{p}\right]\geq\frac{7}{8}.$

For a fixed $r$, let $\mathcal{E}_{1}$ be the event that
$|I^{r}_{\ell}|\leq\frac{10\gamma n}{2^{\ell}}$ and let $\mathcal{E}_{2}$ be
the event that $F_{p}(I^{r}_{\ell})\leq\frac{10\gamma F_{p}}{2^{\ell}}$.
Recall that $I^{r}_{\ell}$ is a nested subset of $[n]$ subsampled at rate
$p_{\ell}:=\min(1,2^{-\ell}\gamma)$, so that
$\mathbb{E}\left[|I^{r}_{\ell}|\right]\leq\frac{\gamma n}{2^{\ell}}$. Thus by
Markov’s inequality,
$\mathbf{Pr}\left[\mathcal{E}_{1}\right]\geq\frac{9}{10}$. Similarly,
$\mathbb{E}\left[F_{p}(I^{r}_{\ell})\right]\leq\frac{\gamma F_{p}}{2^{\ell}}$.
Thus by Markov’s inequality,
$\mathbf{Pr}\left[\mathcal{E}_{2}\right]\geq\frac{9}{10}$. By a union bound,
we first have
$\mathbf{Pr}\left[\mathcal{E}_{1}\wedge\mathcal{E}_{2}\right]\geq\frac{8}{10}$.
Applying another union bound, we have that
$|D^{r}_{i}-C_{i}|\leq\frac{\varepsilon_{\ell}}{2}\cdot F_{p}$ for a fixed
$r$, with probability at least $\frac{5}{8}$. Since
$\widehat{C_{i}}=\operatorname*{median}_{r}D^{r}_{i}$ across
$r\leq\mathcal{O}\left(\log\log n\right)$ iterations, then we have that
$|\widehat{C_{i}}-C_{i}|\leq\frac{\varepsilon_{\ell}}{2}\cdot F_{p}$ with
probability at least $1-\frac{1}{\operatorname*{polylog}(n)}$.

By a union bound over the indices $i\in[\alpha\log n]$, corresponding to the
$\alpha\log n$ level sets, then with probability at least
$1-\frac{1}{\operatorname*{polylog}(n)}$, we have that
$|\widehat{C_{i}}-C_{i}|\leq\frac{\varepsilon_{\ell}}{2}\cdot F_{p}$
simultaneously for all $i\in[\alpha\log n]$, where
$\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$. We form our
estimate $\tilde{F_{p}}$ to $F_{p}$ by setting
$\tilde{F_{p}}:=\sum_{i}\widehat{C_{i}}$ and we have $F_{p}=\sum_{i}C_{i}$.
Since $i\in[\alpha\log n]$,
$\ell_{i}:=\min\\{k:2^{k}>2^{i}\cdot\varepsilon_{k}^{2}\\}$, and
$\varepsilon_{\ell_{i}}=\frac{\varepsilon}{16\eta\cdot
2^{\ell_{i}(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$, then

$\displaystyle|\tilde{F_{p}}-F_{p}|$
$\displaystyle=\left|\sum_{i}\widehat{C_{i}}-\sum_{i}C_{i}\right|\leq\sum_{i}|\widehat{C_{i}}-C_{i}|\leq\sum_{i}\left(\frac{\varepsilon}{4\alpha\log
n}+\varepsilon_{\ell_{i}}\right)\cdot F_{p}$
$\displaystyle\leq\sum_{i\in[\alpha\log n]}\frac{\varepsilon}{4\alpha\log
n}\cdot
F_{p}+\sum_{i:\ell_{i}\leq\log\frac{1}{\varepsilon^{2}}}\varepsilon_{\ell_{i}}\cdot
F_{p}+\sum_{i:\ell_{i}>\log\frac{1}{\varepsilon^{2}}}\varepsilon_{\ell_{i}}\cdot
F_{p}$ $\displaystyle\leq\frac{\varepsilon}{4}\cdot
F_{p}+\log\frac{1}{\varepsilon^{2}}\cdot\frac{\varepsilon}{16\log\frac{1}{\varepsilon^{2}}}\cdot
F_{p}+\frac{\varepsilon}{16}\cdot F_{p},$

where the last bound on the last term follows from $\eta>\sum_{j\geq
0}2^{-j(p/16-1/8)}$. Therefore with probability at least
$1-\frac{1}{\operatorname*{polylog}(n)}$, we have that
$|\tilde{F_{p}}-F_{p}|\leq\frac{\varepsilon}{2}\cdot F_{p}$. ∎

We now justify the full guarantees claimed by Theorem 1.2. We first handle two
passes over a turnstile stream.

######  Theorem 3.5.

For $p>2$, there exists a two-pass turnstile streaming algorithm that outputs
a $(1+\varepsilon)$-approximation to the $F_{p}$ moment with probability at
least $\frac{2}{3}$, while using
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log^{2}n\log\log
n\right)$ bits of space.

###### Proof.

Our analysis is similar to the proof of Theorem 1.1. We again observe that by
redefining the level sets according to any upper bound on $F_{p}$, we do not
require a $1.01$-approximation $\widehat{F_{p}}$ to $F_{p}$ as the input of
Algorithm 2. Thus by Lemma 3.4, there exists an algorithm that outputs a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment on two pass turnstile
streams and it remains to analyze the space complexity. By Theorem 3.1,
CountSketch with threshold $\varepsilon$ requires
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\log^{2}n\right)$ bits of space to
output the indices of the heavy-hitters. Algorithm 2 runs a separate instance
of CountSketch with threshold
$\frac{(\varepsilon_{i})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{i}}\right)^{1/2-1/p}$
to output a set $H^{r}_{i}$ for $r\leq\mathcal{O}\left(\log\log n\right)$,
where $\gamma$ is a sufficiently large constant. Thus the total space in the
first pass across all indices $i$ for a fixed $r$ is at most

$\left(C_{1}\log^{2}n\right)\cdot\sum_{i\in[\alpha\log
n]}\frac{(n_{i})^{1-2/p}}{(\varepsilon_{i})^{4/p}},$

for some positive constants $C_{1},\alpha>0$. In particular, we have
$n_{i}=\frac{10\gamma n}{2^{i}}$ and
$\varepsilon_{i}=\frac{\varepsilon}{16\eta\cdot
2^{i(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$ for a sufficiently large
constant $\eta$. Then the total space in the first pass across all indices $i$
for a fixed $r$ is at most

$\left(C_{1}\log^{2}n\right)\cdot\sum_{i=1}^{\infty}\frac{C_{2}n^{1-2/p}}{\varepsilon^{4/p}}\cdot\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}},$

for some positive constants $C_{1},C_{2}>0$. Since
$\sum_{i=1}^{\infty}\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}}=\sum_{i=1}^{\infty}\frac{1}{2^{3i(1-2/p)/4}}$
is a geometric series that is upper bounded by a fixed constant, the total
space in the first pass across all $i$ for a fixed $r$ is
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log^{2}n\right)$.
Because $r\in\mathcal{O}\left(\log\log n\right)$, then the total space is
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log^{2}n\log\log
n\right)$.

In the second pass, we track the frequencies of each item reported by some
instance of CountSketch. Since at most
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log\log n\right)$
indices can be reported across all instances of CountSketch and
$\mathcal{O}\left(\log n\right)$ bits of space can be used to track the
frequency of each reported index, then the total space for the second pass is
at most $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log
n\log\log n\right)$. Thus, the total space is
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log^{2}n\log\log
n\right)$. ∎

Finally, we note that to report at most
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log\log n\right)$
indices of possible heavy-hitters in turnstile streams, CountSketch uses at
most $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\log^{2}n\log\log n\right)$ space. By the same reasoning, we use
space $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log
n\log\log n\right)$ in insertion-only streams by using the more space
efficient BPTree.

######  Theorem 3.6.

For $p>2$, there exists a two-pass insertion-only streaming algorithm that
outputs a $(1+\varepsilon)$-approximation to the $F_{p}$ moment with
probability at least $\frac{2}{3}$, while using
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log n\log\log
n\right)$ bits of space.

###### Proof.

The proof of correctness is exactly the same as that of Theorem 3.5 since
using BPTree as the subroutine for HeavyHitters rather than CountSketch offers
the same guarantee for insertion-only streams. By Theorem 3.2, BPTree with
threshold $\varepsilon$ requires
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\log n\right)$ bits of space to
output the indices of the heavy-hitters. To analyze the space complexity, note
that Algorithm 2 runs a separate instance of BPTree with threshold
$\frac{(\varepsilon_{i})^{2/p}}{80\gamma}\cdot\left(\frac{1}{n_{i}}\right)^{1/2-1/p}$
to output a set $H^{r}_{i}$ for $r\leq\mathcal{O}\left(\log\log n\right)$,
where $\gamma$ is a sufficiently large constant. Hence, the first pass across
all indices $i$ for a fixed $r$ uses space at most

$\left(C_{1}\log n\right)\cdot\sum_{i\in[\alpha\log
n]}\frac{(n_{i})^{1-2/p}}{(\varepsilon_{i})^{4/p}},$

for some absolute constants $C_{1},\alpha>0$. Since $n_{i}=\frac{10\gamma
n}{2^{i}}$ and $\varepsilon_{i}=\frac{\varepsilon}{16\eta\cdot
2^{i(p/16-1/8)}\log\frac{1}{\varepsilon^{2}}}$ for a sufficiently large
constant $\eta$, the first pass uses space at most

$\left(C_{1}\log
n\right)\cdot\sum_{i=1}^{\infty}\frac{C_{2}n^{1-2/p}}{\varepsilon^{4/p}}\cdot\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}},$

for some absolute constants $C_{1},C_{2}>0$, across all indices $i$ for a
fixed $r$. As
$\sum_{i=1}^{\infty}\frac{2^{i(1/4-1/(2p))}}{2^{i(1-2/p)}}=\sum_{i=1}^{\infty}\frac{1}{2^{3i(1-2/p)/4}}$
is a geometric series that is upper bounded by some constant, then the total
space in the first pass is $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\log n\right)$ across all indices $i$ for a fixed $r$. Since
$r\leq\mathcal{O}\left(\log\log n\right)$, then the total space in the first
pass is $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log
n\log\log n\right)$.

The second pass tracks the frequencies of each item reported by some instance
of BPTree. Since at most $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot
n^{1-2/p}\log\log n\right)$ indices can be reported across all instances of
BPTree and $\mathcal{O}\left(\log n\right)$ bits of space can be used to track
the frequency of each reported index, then the total space for the second pass
is at most $\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log
n\log\log n\right)$. Thus, the total space is
$\mathcal{O}\left(\frac{1}{\varepsilon^{4/p}}\cdot n^{1-2/p}\log n\log\log
n\right)$. ∎

##  4 Lower Bounds

In this section, we first consider the standard _blackboard_ communication
model, where a number of players each have a local input and the goal is to
solve some predetermined communication problem by sending messages to a shared
medium. Each player is assumed to have access to an unlimited amount of
private randomness. The sequence of messages on the shared blackboard is
called the _transcript_ and the maximum length of the transcript over all
inputs is the _communication cost_ of a given protocol. The communication
complexity of $f$, denoted by $R_{\delta}(f)$, is the minimal communication
cost of all protocols that succeed with probability at least $1-\delta$ for
all legal inputs to $f$. We now require a number of basic concepts and results
from information theory.

######  Definition 4.1 (Mutual information).

Given a pair of random variables $X$ and $Y$ with joint distribution $p(x,y)$,
the _mutual information_ is defined as
$I(X;Y):=\sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}$, for marginal
distributions $p(x)$ and $p(y)$.

######  Definition 4.2 (Information cost).

Let $\Pi$ be a randomized protocol that produces a random variable
$\Pi(X_{1},\ldots,X_{t})$ as a transcript on inputs $X_{1},\ldots,X_{t}$ drawn
from a distribution $\mu$. Then the _information cost_ of $\Pi$ with respect
to $\mu$ is defined as $I(P_{1},\ldots,P_{t};\Pi(P_{1},\ldots,P_{t}))$.

######  Definition 4.3 (Information complexity).

The information complexity of $f$ with respect to a distribution $\mu$ and
failure probability $\delta$ is the minimum information cost of a protocol for
$f$ with respect to $\mu$ that fails with probability at most $\delta$ on
every input and denoted by ${\mathsf{IC}}_{\mu,\delta}(f)$.

######  Definition 4.4 (Conditional information cost).

Suppose $((X_{1},\ldots,X_{t}),W)\sim\zeta$ for a mixture of product
distributions. The _conditional information cost_ of a randomized protocol
$\Pi$ with respect to $\zeta$ is
$I(X_{1},\ldots,X_{t};\Pi(X_{1},\ldots,X_{t})|W)$.

######  Definition 4.5 (Conditional information complexity).

The conditional information complexity of $f$ with respect to $\zeta$ and
failure probability $\delta$ is defined to be the minimum conditional
information cost of a protocol for $f$ with respect to $\zeta$ that fails with
probability at most $\delta$ and denoted by
${\mathsf{CIC}}_{\zeta,\delta}(f)$.

######  Fact 4.6.

For any distribution $\mu$ and failure probability $\delta\in(0,1)$, we have
$R_{\delta}(f)\geq{\mathsf{IC}}_{\mu,\delta}(f|W)$.

######  Definition 4.7 (Decomposable functions).

A function $f$ is $g$-decomposable with primitive $h$ if
$f({\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{t})=g(h({\mathbf{x}}_{1,1},\ldots,{\mathbf{x}}_{t,1}),\ldots,h({\mathbf{x}}_{1,n},\ldots,{\mathbf{x}}_{t,n}))$
for some function $h$, where ${\mathbf{x}}_{i,j}$ denotes the $j$-th
coordinate of ${\mathbf{x}}_{i}$.

######  Definition 4.8 (Embedding of a coordinate into a vector).

For a vector ${\mathbf{x}}\in\mathbb{R}^{n}$, $i\in[n]$ and $y\in\mathbb{R}$,
we use $\operatorname*{embed}({\mathbf{x}},i,y)$ to denote the vector
${\mathbf{v}}$ such that ${\mathbf{v}}_{i}=y$ and
${\mathbf{v}}_{j}={\mathbf{x}}_{j}$ for $j\neq i$.

######  Definition 4.9 (Collapsing distribution).

For a function $f$ that is $g$-decomposable with primitive $h$, we say
$({\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{t})$ is a collapsing input for $f$ if
for every $j$ and set $(y_{1},\ldots,y_{t})$ of legal inputs, we have

$f(\operatorname*{embed}({\mathbf{x}}_{1},j,y_{1}),\ldots,\operatorname*{embed}({\mathbf{x}}_{t},j,y_{t}))=h(y_{1},\ldots,y_{t}).$

A distribution $\mu$ on the input space is a _collapsing distribution_ for $f$
if every $({\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{t})$ in the support of $\mu$
is a collapsing input.

######  Lemma 4.10 (Information cost decomposition lemma, Lemma 5.1 in
[BJKS04]).

Let $\mu$ be a mixture of product distributions and suppose that
$((X_{1},\ldots,X_{t}),W)\sim\mu^{n}$. Then for a protocol $\Pi$ whose inputs
$(X_{1},\ldots,X_{t})\sim\mathcal{L}^{n}$ for some legal input set
$\mathcal{L}$, we have
$I(X_{1},\ldots,X_{t};\Pi(X_{1},\ldots,X_{t}|W))\geq\sum_{i}I(X_{1,i},\ldots,X_{t,i};\Pi(X_{1},\ldots,X_{t})|W)$,
where $X_{i,j}$ denotes the $j$-th component of $X_{i}$.

######  Lemma 4.11 (Reduction lemma, Lemma 5.5 in [BJKS04]).

Let $\Pi$ be a protocol for a decomposable function $f$ with input
$\mathcal{L}^{n}$ and primitive $h$, that fails with probability at most
$\delta$. Let $\mu$ be a mixture of product distributions and suppose
$((X_{1},\ldots,X_{t}),D)\sim\mu^{n}$. If $(X_{1},\ldots,X_{t})$ is a
collapsing distribution for $f$, then for all $j\in[n]$,

$I((X_{1,j},\ldots,X_{t,j});\Pi(X_{1},\ldots,X_{t})|D)\geq{\mathsf{CIC}}_{\mu,\delta}(h).$

For an input $X$ to a protocol $\Pi$, let $\pi(X)$ denote the probability
distribution over the transcripts produced by $\Pi$ across the private
randomness of the protocol. Let $\psi(X):=\sqrt{\pi(X)}$ denote the transcript
wave function of $X$ so that $\|\psi(X)\|_{2}=\|\pi(X)\|_{1}=1$.

######  Definition 4.12.

The Hellinger distance between $\psi_{1}$ and $\psi_{2}$ is the scaled
Euclidean distance defined by
$h(\psi_{1},\psi_{2}):=\frac{1}{\sqrt{2}}\|\psi_{1}-\psi_{2}\|_{2}$.

######  Fact 4.13 (Mutual information to Hellinger distance).

For $X\in\\{u,v\\}$, we have
$I(X;\Pi)\geq\frac{1}{2}\|\psi(u)-\psi(v)\|_{2}^{2}$.

######  Fact 4.14 (Soundness for Hellinger distance).

If $\Pi$ is a protocol for $g$ that fails with probability at most
$\delta\in(0,1)$ and $g(X_{1})\neq g(X_{2})$, then

$\frac{1}{2}\|\psi(X_{1})-\psi(X_{2})\|_{2}^{2}\geq 1-2\sqrt{\delta}.$

######  Lemma 4.15 (Theorem 7 in [Jay09]).

For a $t$-party protocol $\Pi$ on the input domain $\\{0,1\\}^{t}$, let
$A_{1},\ldots,A_{s}$ be a pairwise disjoint collection of $s=2^{k}$ subsets of
$[t]$ and $A=\cup_{i}A_{i}$. Then

$\sum_{i=1}^{s}\|\psi(\emptyset)-\psi(A_{i})\|_{2}^{2}\geq\|\psi(\emptyset)-\psi(A)\|_{2}^{2}\cdot\prod_{\ell=1}^{k}\left(1-\frac{1}{2^{\ell}}\right).$

######  Definition 4.16.

In the $(t,\varepsilon,n)$-player set disjointness estimation problem
$(t,\varepsilon,n)-{\textsc{DisjInfty}}$, there are $t+1$ players
$P_{1},\ldots,P_{t+1}$ with private coins in the standard blackboard model.
For $s\in[t]$, each player $P_{s}$ receives a vector
${\mathbf{v}}_{s}\in\\{0,1\\}^{n}$ and player $P_{t+1}$ receives both an index
$j\in[n]$ and a bit $c\in\\{0,1\\}$. For
${\mathbf{u}}=\sum_{s\in[t]}{\mathbf{v}}_{s}$, the inputs are promised to
satisfy $u_{i}\leq 1$ for each $i\neq j$ and either $u_{j}=1$ or $u_{j}=t$.
With probability at least $\frac{9}{10}$, $P_{t+1}$ must differentiate between
the three possible input cases:

  1. (1)

$u_{j}+\frac{ct}{\varepsilon}\leq t$

  2. (2)

$u_{j}+\frac{ct}{\varepsilon}\in\left\\{\frac{t}{\varepsilon},\frac{t}{\varepsilon}+1\right\\}$

  3. (3)

$u_{j}+\frac{ct}{\varepsilon}=(1+\varepsilon)\frac{t}{\varepsilon}$,

where $\varepsilon\in(0,1)$. We call coordinate $j\in[n]$ the _spike_
location.

Direct sum embedding. We use the direct sum technique by showing that even in
the case where $u_{i}\leq 1$ for all $i\in[n]$, the information cost of the
players is sufficiently high. We describe the embedding performed by each
player to sample coordinates independently conditioned on the auxiliary
variable $D$. We define the auxiliary variable $D=(D_{1},\ldots,D_{n})$ by
first defining a distribution $\mu$ for $D_{i}$ and $v_{s,i}$, for each fixed
coordinate $i\in[n]$ and across all players $s\in[t]$:

  1. (1)

$D_{i}\sim[t]$ uniformly at random, so that $D_{i}$ determines a player whose
input bit will be randomized while the remaining players have input bit zero.

  2. (2)

Conditioned on $D_{i}=s$, then each player $P_{r}$ with $r\neq s$ sets
$v_{r,i}=0$ while player $P_{s}$ independently and uniformly sets
$v_{s,i}\in\\{0,1\\}$.

We define the distribution $\zeta:=\mu^{n}$ so that the auxiliary random
variable $D=(D_{1},\ldots,D_{n})$ is the vector whose $i$-th coordinate
determines the player $P_{D_{i}}$ whose $i$-th bit $v_{D_{i},i}$ in their
input vector will vary, while the other players $P_{s}$ have $i$-th bit
$v_{s,i}$ zero in their vectors, for $s\neq D_{i}$. Observe that under the
distribution $\zeta$, we indeed have $u_{i}\leq 1$ for each coordinate
$i\in[n]$ of ${\mathbf{u}}=\sum_{s\in[t]}{\mathbf{v}}_{s}$. Finally, we fix
the input $c=0$ to player $P_{t+1}$ and pick $j\in[n]$ according to any
arbitrary distribution.

We now show that $\zeta$ is a collapsing distribution for
$(t,\varepsilon,n)-{\textsc{DisjInfty}}$.

######  Lemma 4.17.

For $c=0$ and arbitrary $j\in[n]$, $\zeta$ is a collapsing distribution for
$(t,\varepsilon,n)-{\textsc{DisjInfty}}$.

###### Proof.

The distribution $\zeta$ only places mass at $0^{t}$ or the elementary vector
${\mathbf{e}}_{D_{i}}\in\\{0,1\\}^{t}$ for each $i\in[n]$. Since $c=0$, then
for every input in the support of $\zeta$, we have

$(t,\varepsilon,n)-{\textsc{DisjInfty}}(\operatorname*{embed}({\mathbf{v}}_{1},i,y_{1}),\ldots,\operatorname*{embed}({\mathbf{v}}_{t},i,y_{t}))={\textsc{DisjInfty}}(y_{1},\ldots,y_{t}),$

regardless of the value of $j$. Hence, $\zeta$ is a collapsing distribution
for $(t,\varepsilon,n)-{\textsc{DisjInfty}}$. ∎

We now prove the communication complexity of the $(t,\varepsilon,n)$-player
set disjointness estimation problem.

######  Theorem 4.18.

The total communication complexity for the $(t,\varepsilon,n)$-player set
disjointness estimation problem is $\Omega\left(\frac{n}{t}\right)$.

###### Proof.

Let $\Pi$ be a protocol with minimum information cost that solves any input to
$(t,\varepsilon,1)-{\textsc{DisjInfty}}$ with probability at least $1-\delta$,
where $\delta=\frac{1}{10}$. By setting $c=0$ and choosing $j\in[n]$ from any
arbitrary distribution for the input to $P_{t+1}$, we have that $\zeta$ is a
collapsing distribution for $(t,\varepsilon,n)-{\textsc{DisjInfty}}$, by Lemma
4.17. $\zeta$ also induces the auxiliary random variable
$D=(D_{1},\ldots,D_{n})$ that determines the player $P_{D_{i}}$ whose $i$-th
bit $v_{D_{i},i}$ in their input vector will vary.

We note that the messages from each player $P_{s}$ with $s\in[t]$ do not
depend on the input of $P_{t+1}$. Moreover, the input of player $P_{t+1}$ is
drawn from a distribution that is independent of the incoming message. Since
our protocol is required to be correct on all inputs as opposed to some
particular distribution, then it suffices to consider the protocol $\Pi$ only
on the input of the first $t$ players, which we denote by
$\Pi({\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t})$. Thus by applying the direct
sum technique on the embedding $\zeta=\mu^{n}$, we have from Fact 4.6 that

$R((t,\varepsilon,n)-{\textsc{DisjInfty}})\geq{\mathsf{IC}}_{\zeta,\delta}({\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t};\Pi({\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t}|D)).$

Since
${\mathsf{IC}}_{\zeta,\delta}({\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t};\Pi({\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t}|D))\geq\sum_{i=1}^{n}I(v_{1,i},\ldots,v_{t,i};\Pi(v_{1,i},\ldots,v_{t,i})|D)$
by the decomposition of information cost in Lemma 4.10, we have that

$R((t,\varepsilon,n)-{\textsc{DisjInfty}})\geq\sum_{i=1}^{n}I(v_{1,i},\ldots,v_{t,i};\Pi(v_{1,i},\ldots,v_{t,i})|D).$

Notably, Lemma 4.10 implicitly uses the chain rule for conditional entropy and
the subadditivity of conditional entropy.

Decomposition into single coordinate problem. Since $\zeta$ is a collapsing
distribution for $c=0$ by Lemma 4.17, then for the single coordinate problem
$(t,\varepsilon,1)-{\textsc{DisjInfty}}$ of
$(t,\varepsilon,n)-{\textsc{DisjInfty}}$,so that all vector inputs to each
player have dimension one, we have

$\sum_{i=1}^{n}I(v_{1,i},\ldots,v_{t,i};\Pi(v_{1,i},\ldots,v_{t,i})|D)\geq
n\cdot{\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}}),$

by Lemma 4.11. Thus we can lower bound the communication complexity of
$(t,\varepsilon,n)-{\textsc{DisjInfty}})$ by the single coordinate problem
through

$R((t,\varepsilon,n)-{\textsc{DisjInfty}})\geq
n\cdot{\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}}).$

In particular, we have that the input distribution $\zeta$ for
$(t,\varepsilon,n)-{\textsc{DisjInfty}}$ has single coordinate distribution
$\mu$ for $(t,\varepsilon,1)-{\textsc{DisjInfty}}$. Thus it remains to show
that
${\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}})=\Omega\left(\frac{1}{t}\right)$.

Complexity of single coordinate problem. Without loss of generality, we
consider the single coordinate problem by considering the first coordinates
$v_{1,1},\ldots,v_{t,1}$ of the input vectors
${\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{t}$. By the definition of conditional
information complexity, we have

${\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}})=I(v_{1,1},\ldots,v_{t,1};\Pi|D_{1})\geq\frac{1}{t}\sum_{s\in[t]}I(v_{1,1},\ldots,v_{t,1};\Pi|D_{1}=s).$

Conditioned on $D_{1}=s$, we have $v_{s,1}\in\\{0,1\\}$ uniformly at random
and $v_{r,1}=0$ for $r\neq s$. Thus by Fact 4.13 relating mutual information
to Hellinger distance, we have

${\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}})\geq\frac{1}{t}\sum_{s=1}^{t}\frac{1}{2}\|\psi(\emptyset)-\psi(\\{s\\})\|_{2}^{2},$

where we use $\emptyset$ to denote that $v_{s,1}=0$ and $\\{s\\}$ to denote
that $v_{s,1}=1$. Instead of analyzing the sum of each of the squared
Hellinger distances, we instead use Lemma 4.15 to analyze the squared
Hellinger distance from $\emptyset$ to $[t]$, which represents that
$v_{1,1}=\ldots=v_{t,1}=1$. For $t=2^{k}$, we set the parameter $s$ in Lemma
4.15 to $t$ and $A_{i}=\\{i\\}$, so that

${\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}})\geq\frac{1}{t}\left(\frac{1}{2}\|\psi(\emptyset)-\psi([t])\|_{2}^{2}\right)\cdot\prod_{\ell=1}^{k}\left(1-\frac{1}{2^{\ell}}\right).$

Since $(t,\varepsilon,1)-{\textsc{DisjInfty}}$ on inputs $\emptyset$ and $[t]$
achieve different outputs, then by Fact 4.14,

$\frac{1}{2}\|\psi(\emptyset)-\psi([t])\|_{2}^{2}\geq 1-2\sqrt{\delta},$

where $\delta$ is the probability of failure. Similarly, we have
$\prod_{\ell=1}^{k}\left(1-\frac{1}{2^{\ell}}\right)\geq\prod_{\ell=1}^{\infty}\left(1-\frac{1}{2^{\ell}}\right)\approx
0.28878$, by the definition of the digital search tree constant. Thus, we have
that
${\mathsf{CIC}}_{\mu}((t,\varepsilon,1)-{\textsc{DisjInfty}})=\Omega\left(\frac{1}{t}\right)$,
which implies
$R((t,\varepsilon,n)-{\textsc{DisjInfty}})=\Omega\left(\frac{n}{t}\right)$. ∎

We remark that the communication complexity of Theorem 4.18 matches the
communication complexity of $t$-player set disjointness. However, since the
problem requires correctness on all inputs, then we can distinguish between
the possible input cases by focusing on the specific coordinate $j$ given to
player $P_{t+1}$. By contrast, the reduction of [Gan12] from $t$-player set
disjointness requires an algorithm to “test” all coordinates $i\in[n]$ for the
spike location. Thus the reduction requires that an $F_{p}$ moment estimation
algorithm succeeds with probability $1-\frac{1}{\operatorname*{poly}(n)}$,
thereby losing a multiplicative $\mathcal{O}\left(\log n\right)$ factor and
achieving $\Omega\left(\frac{n^{1-2/p}}{\varepsilon^{2}\log n}\right)$ in the
space lower bound for $F_{p}$ moment estimation. Since our communication
problem gives the specific spike location as input, our reduction only
requires an $F_{p}$ moment estimation algorithm that succeeds with constant
probability. We remark that a similar technique was used in [LW13] for the
$L_{\infty}$ promise problem.

Reduction. Let $t=\Theta\left(\frac{1}{\varepsilon}\cdot n^{1/p}\right)$. We
reduce $(1+\varepsilon)$-approximate $F_{p}$ moment estimation to an instance
of $(t,\varepsilon)-{\textsc{DisjInfty}}$ as follows. Let ${\mathcal{A}}$ be
any fixed randomized one-pass insertion-only streaming algorithm that outputs
a $\left(1+\frac{\varepsilon}{3}\right)$-approximation to the $F_{p}$ moment
of the underlying frequency vector with probability at least $\frac{2}{3}$.
Recall that the first $t$ players each receive a vector ${\mathbf{v}}_{s}$
with $s\in[t]$ and player $P_{t+1}$ receives both a special index $j\in[n]$
and a bit $c\in\\{0,1\\}$.

  * •

For each $s\in[t]$, player $P_{s}$ takes the state of the algorithm
${\mathcal{A}}$, inserts the coordinates of vector ${\mathbf{v}}_{s}$, and
passes the state of the algorithm to player $P_{s+1}$.

  * •

Player $P_{t+1}$ takes the state of ${\mathcal{A}}$, adds the vector
$\frac{ct}{\varepsilon}\cdot{\mathbf{e}}_{j}$, where ${\mathbf{e}}_{j}$ is the
elementary vector with a one in position $j$ and zeros elsewhere, and then
queries the state of ${\mathcal{A}}$ to obtain a
$\left(1+\frac{\varepsilon}{3}\right)$-approximation to the $F_{p}$ moment of
underlying frequency vector.

######  Theorem 4.19.

For any constant $p>2$ and parameter
$\varepsilon=\Omega\left(\frac{1}{n^{1/p}}\right)$, any one-pass insertion-
only streaming algorithm that outputs a $(1+\varepsilon)$-approximation to the
$F_{p}$ moment of an underlying frequency vector with probability at least
$\frac{9}{10}$ requires $\Omega\left(\frac{1}{\varepsilon^{2}}\cdot
n^{1-2/p}\right)$ bits of space.

###### Proof.

Player $P_{t+1}$ receives the state of ${\mathcal{A}}$ on the input
${\mathbf{u}}=\sum_{s\in[t]}{\mathbf{v}}_{s}$ and induces a frequency vector
${\mathbf{x}}:={\mathbf{u}}+\frac{ct}{\varepsilon}\cdot{\mathbf{e}}_{j}$.
Recall that the inputs are promised to satisfy $u_{i}\leq 1$ for each $i\neq
j$ and either $u_{j}=1$ or $u_{j}=t$. If $c=0$, then
${\mathbf{x}}={\mathbf{u}}$ so that for a constant $C>0$ and
$t=\frac{C}{\varepsilon}\cdot n^{1/p}$,

$\|{\mathbf{x}}\|^{p}_{p}\leq F_{0}+t^{p}\leq
n+\frac{C^{p}}{\varepsilon^{p}}\cdot n.$

If $c=1$ and $u_{j}\leq 1$, then for $t=\frac{C}{\varepsilon}\cdot n^{1/p}$,
we have
$\|{\mathbf{x}}\|^{p}_{p}\geq\left(\frac{t}{\varepsilon}\right)^{p}=\frac{C^{p}}{\varepsilon^{2p}}\cdot
n$ and thus

$\|{\mathbf{x}}\|^{p}_{p}\leq
F_{0}+\left(1+\frac{t}{\varepsilon}\right)^{p}\leq n+p+\frac{p\cdot
C^{p}}{\varepsilon^{2p}}\cdot n.$

Finally, if $c=1$ and $u_{j}=t$, then

$\|{\mathbf{x}}\|^{p}_{p}\geq\left(t+\frac{t}{\varepsilon}\right)^{p}=\left(1+\frac{1}{\varepsilon}\right)^{p}\cdot\frac{C^{p}}{\varepsilon^{2p}}\cdot
n.$

For sufficiently small $\varepsilon\in(0,1)$ with
$\varepsilon=\Omega\left(\frac{1}{n^{1/p}}\right)$ and constant $p>2$, there
exists a constant $C>0$ such that these three cases are separated by a
multiplicative $(1+\varepsilon)$. Since ${\mathcal{A}}$ outputs a
$\left(1+\frac{\varepsilon}{3}\right)$-approximation to the $F_{p}$ moment of
the underlying frequency vector, then player $P_{t+1}$ obtains a
$\left(1+\frac{\varepsilon}{3}\right)$-approximation to
$\|{\mathbf{x}}\|_{p}^{p}$ and can differentiate between the three cases, thus
solving $(t,\varepsilon)-{\textsc{DisjInfty}}$ with probability at least
$\frac{9}{10}$. By Theorem 4.18, ${\mathcal{A}}$ uses
$\Omega\left(\frac{n}{t}\right)$ total communication across the $t+1$ players.
Therefore, the space complexity of ${\mathcal{A}}$ is
$\Omega\left(\frac{n}{t^{2}}\right)=\Omega\left(\frac{1}{\varepsilon^{2}}\cdot
n^{1-2/p}\right)$ for $t=\Theta\left(\frac{1}{\varepsilon}\cdot
n^{1/p}\right)$. The result then follows from rescaling $\varepsilon$. ∎

## Acknowledgements

The authors would like to thank support from NSF grant No. CCF-181584 and a
Simons Investigator Award and thank Krzysztof Onak for pointing toward the
reference [AMOP08].

## References

  * [AKO11] Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak.  Streaming algorithms via precision sampling.  In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pages 363–372, 2011.
  * [AMOP08] Alexandr Andoni, Andrew McGregor, Krzysztof Onak, and Rina Panigrahy.  Better bounds for frequency moments in random-order streams.  CoRR, abs/0808.2222, 2008.
  * [AMS99] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.
  * [And17] Alexandr Andoni.  High frequency moments via max-stability.  In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, pages 6364–6368, 2017.
  * [BCI+17] Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff.  Bptree: An $\ell_{2}$ heavy hitters algorithm using constant memory.  In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 361–376, 2017.
  * [BDN17] Jaroslaw Blasiok, Jian Ding, and Jelani Nelson.  Continuous monitoring of $\ell_{p}$ norms in data streams.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 81, pages 32:1–32:13, 2017\.
  * [BGKS06] Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha.  Simpler algorithm for estimating frequency moments of data streams.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 708–713, 2006.
  * [BGW20] Mark Braverman, Sumegha Garg, and David P. Woodruff.  The coin problem with applications to data streams.  Electron. Colloquium Comput. Complex., 27:139, 2020.
  * [BJKS04] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar.  An information statistics approach to data stream and communication complexity.  J. Comput. Syst. Sci., 68(4):702–732, 2004.
  * [BKSV14] Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger.  An optimal algorithm for large frequency moments using O$(n^{1-2/k})$ bits.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 531–544, 2014.
  * [BO13] Vladimir Braverman and Rafail Ostrovsky.  Approximating large frequency moments with pick-and-drop sampling.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX, and 17th International Workshop, RANDOM. Proceedings, 2013.
  * [BVWY18] 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 Programming, ICALP, pages 25:1–25:14, 2018.
  * [CCF04] Moses Charikar, Kevin C. Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  Theor. Comput. Sci., 312(1):3–15, 2004.
  * [CCM16] Amit Chakrabarti, Graham Cormode, and Andrew McGregor.  Robust lower bounds for communication and stream computation.  Theory Comput., 12(1):1–35, 2016.
  * [CJP08] Amit Chakrabarti, T. S. Jayram, and Mihai Patrascu.  Tight lower bounds for selection in randomly ordered streams.  In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 720–729, 2008\.
  * [CKS03] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun.  Near-optimal lower bounds on the multi-party communication complexity of set disjointness.  In 18th Annual IEEE Conference on Computational Complexity, pages 107–117, 2003.
  * [DLM02] Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro.  Frequency estimation of internet packet streams with limited space.  In Algorithms - ESA, 10th Annual European Symposium, Proceedings, pages 348–360, 2002.
  * [Gan11] Sumit Ganguly.  Polynomial estimators for high frequency moments.  CoRR, abs/1104.4552, 2011.
  * [Gan12] Sumit Ganguly.  A lower bound for estimating high moments of a data stream.  CoRR, abs/1201.0253, 2012.
  * [GH09] Sudipto Guha and Zhiyi Huang.  Revisiting the direct sum theorem and space lower bounds in random order streams.  In International Colloquium on Automata, Languages, and Programming, pages 513–524. Springer, 2009.
  * [GM06] Sudipto Guha and Andrew McGregor.  Approximate quantiles and the order of the stream.  In Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 273–279, 2006.
  * [GM07] Sudipto Guha and Andrew McGregor.  Lower bounds for quantile estimation in random-order and multi-pass streaming.  In Automata, Languages and Programming, 34th International Colloquium, ICALP, Proceedings, pages 704–715, 2007.
  * [GW18] Sumit Ganguly and David P. Woodruff.  High probability frequency moment sketches.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP, 2018.
  * [Ind06] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  J. ACM, 53(3):307–323, 2006.
  * [IW05] Piotr Indyk and David P. Woodruff.  Optimal approximations of the frequency moments of data streams.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 202–208, 2005.
  * [Jay09] T. S. Jayram.  Hellinger strikes back: A note on the multi-party information complexity of AND.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX, and 13th International Workshop, RANDOM. Proceedings, pages 562–573, 2009.
  * [JW19] Rajesh Jayaram and David P. Woodruff.  Towards optimal moment estimation in streaming and distributed models.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 29:1–29:21, 2019.
  * [KMM12] Christian Konrad, Frédéric Magniez, and Claire Mathieu.  Maximum matching in semi-streaming with few passes.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX, and 16th International Workshop, RANDOM, pages 231–242, 2012.
  * [KNPW11] Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff.  Fast moment estimation in data streams in optimal space.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pages 745–754, 2011.
  * [KNW10] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  On the exact space complexity of sketching and streaming small norms.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1161–1178, 2010.
  * [Li08] Ping Li.  Estimators and tail bounds for dimension reduction in $\ell_{\alpha}(0<\alpha\leq 2)$ using stable random projections.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 10–19, 2008.
  * [LW13] Yi Li and David P. Woodruff.  A tight lower bound for high frequency moment estimation with small error.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX, and 17th International Workshop, RANDOM. Proceedings, pages 623–638, 2013.
  * [MP80] J. Ian Munro and Mike Paterson.  Selection and sorting with limited storage.  Theor. Comput. Sci., 12:315–323, 1980.
  * [MW10] Morteza Monemizadeh and David P. Woodruff.  1-pass relative-error $\text{L}_{p}$-sampling with applications.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1143–1160, 2010.
  * [Woo04] David P. Woodruff.  Optimal space lower bounds for all frequency moments.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 167–175, 2004.
  * [WZ12] David P. Woodruff and Qin Zhang.  Tight bounds for distributed functional monitoring.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 941–960, 2012.
  * [WZ20] David P. Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  CoRR, abs/2011.07471, 2020.

##  Appendix A Approximately Counting Heavy-Hitters

In this section, we describe the procedure CountHH introduced by [BGW20] for
approximating the frequencies of the $L_{2}$-heavy hitters in a random-order
insertion-only stream. Their algorithm partitions the updates of a random-
order stream into blocks of updates. They then randomly choose a number of
different coordinates from the universe $[n]$ to test in each block. If there
is an update to a coordinate that is tested within a block, then the
coordinate is said to be _excited_. Once an item is excited, the algorithm
then explicitly tracks updates to the item across a number of subsequent
blocks. If the algorithm sees that the stream consistently updates a tracked
item, then the item is promoted to a heavy-hitter, and its frequency remains
tracked over a longer number of blocks. The frequency over the longer number
of blocks is then scaled up to provide an accurate estimation of the frequency
of the heavy-hitter in the entire stream. Otherwise if a tracked item is not
consistently updated by the stream, then it was likely a false positive due to
the randomness of the stream and the hash functions, and it is no longer
tracked by the algorithm. Any heavy-hitter on the stream has sufficiently high
probability of being updated in a block in which it is tested. Thus all heavy-
hitters will become excited with “good” probability and become tracked by the
algorithm.

The algorithm heavily relies on the fact that the stream is random-order and
insertion-only. In streams that are not insertion-only, any initially reported
heavy-hitter can simply be erased later in the stream. In streams that are not
random-order, the distribution of the heavy-hitters may not be uniform, so
they may not become excited in a block in which they are tested. Similarly,
the distribution of the heavy-hitters in the blocks for which they are tracked
must be representative of the overall frequency of the heavy-hitters due to
the random-order model.

[BGW20] showed that $\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\right)$ items
are tracked at a time. We wish to report an approximate frequency to a heavy-
hitter with accuracy $(1+\varepsilon)$. Thus, each heavy-hitter is tracked for
a small number of blocks, so that the counter for the heavy-hitter across
these blocks can be represented using
$\mathcal{O}\left(\log\frac{1}{\varepsilon}+\log\log n\right)$ bits. However,
the number of blocks is sufficiently large so that the tracking provides a
$(1+\varepsilon)$-approximation to the frequency of the item across the entire
stream, due to the uniformity properites of the random-order stream.

We first give the subroutine CountHHShort from [BGW20] for approximating the
number of heavy-hitters in Algorithm 3.

Algorithm 3 CountHHShort: Subroutine for counting the number of heavy-hitters
[BGW20]

1:Random order $a_{1},\ldots,a_{m}\in[n]$ of stream of updates to coordinates
of an underlying frequency vector, threshold parameter $\varepsilon\in(0,1)$,
stream length $m$ and $2$-approximation $\tilde{F_{2}}$ to $F_{2}$.

2:Estimated frequencies to $L_{2}$-heavy hitters.

3:$H\leftarrow\emptyset$

4:Partition the stream into $t=\varepsilon\sqrt{\tilde{F_{2}}}$ contiguous
blocks, $B_{1},\ldots,B_{t}$, each of length
$\frac{F_{1}}{\varepsilon\sqrt{\tilde{F_{2}}}}$.

5:Let $h^{1},\ldots,h^{10\ln(1/\varepsilon)}:[n]\to[t]$ and
$g:[n]\to[200\varepsilon^{-26}\ln^{4}(dm)]$ be independent pairwise hash
functions.

6:while processing block $B_{i}$ do

7: $S^{i}\leftarrow\emptyset$, $e^{i}=0$, initialize $c^{i}$ to the all $0$’s
vector.

8: Process all items $a_{j}\in B_{i}$.

9: while processing item $a_{j}$ do

10: if $e^{i}=0$ and $h^{q}(a_{j})=i$ for some $q\in[10\ln(1/\varepsilon)]$
then

11: $S^{i}\leftarrow S^{i}\cup\\{g(a_{j})\\}$.

12: if $|S^{i}|>100\varepsilon^{-2}\ln(1/\varepsilon)$ then

13: $e^{i}\leftarrow 1$

14: if $g(a_{j})\in S^{i-1}$, $h^{q}(a_{j})=i-1$ for some
$q\in[10\ln(1/\varepsilon)]$ and $e^{i-1}=0$ then

15: $c^{i-1}(g(a_{j}))=c^{i-1}(g(a_{j}))+1$

16: if $e^{i-1}=0$ and there is a unique $k\in S^{i-1}$ with $c^{i-1}(k)=1$
then

17: if there is no uncompleted Identify instance already running and $|H|\leq
2\varepsilon^{-2}$ then

18: $H\leftarrow
H\cup{\textsc{Identify}}(\\{h^{q}\\}_{q},g,i,k,m,a_{iF_{1}/(\varepsilon\sqrt{\tilde{F_{p}}})+1},\ldots,a_{m})$

19:return $|H|$

Algorithm 4 Algorithm for identifying heavy-hitters [BGW20]

1:Hash functions $\\{h^{q}\\}_{q}$, hash function $g$, block number $i$,
tracking hash value $k$, stream length $m$, stream updates
$a_{iF_{1}/(\varepsilon\sqrt{\tilde{F_{p}}})+1},\ldots,a_{m}$.

2:Set of heavy-hitters

3:${\mathsf{id}}\leftarrow\emptyset$, $\ell\leftarrow 1$

4:while ${\mathsf{id}}\neq\emptyset$ or $\ell>100\ln(1/\varepsilon)$ do

5: if $|\\{j\in B_{i+\ell}|g(j)=k\text{ and }h^{q}(j)=i-1\text{ for some
}q\in[10\ln(1/\varepsilon)]\\}|=1$ then

6: ${\mathsf{id}}\leftarrow j$

7: else

8: $\ell\leftarrow\ell+1$

9:if ${\mathsf{id}}=\emptyset$ then

10: return $\emptyset$

11:$p=4000\varepsilon^{-2}\ln m$

12:Let $\xi$ be the number of occurrences of ${\mathsf{id}}$ in the multiset
$\uplus_{v=1}^{p}B_{i+\ell+v}$.

13:if $\xi\geq(1.01/\sqrt{2})p$ then

14:
$\widehat{f_{{\mathsf{id}}}}=\frac{\varepsilon\sqrt{\tilde{F_{p}}}}{p}\cdot\xi$

15: return $({\mathsf{id}},\widehat{f_{{\mathsf{id}}}})$

16:else

17: return $\emptyset$

Algorithm 5 CountHH: Algorithm for counting the number of heavy-hitters
[BGW20]

1:Random order $a_{1},\ldots,a_{m}\in[n]$ of stream of updates to coordinates
of an underlying frequency vector, threshold parameter $\varepsilon\in(0,1)$,
stream length $m$ and $2$-approximation $\tilde{F_{p}}$ to $F_{p}$.

2:Estimated frequencies to $L_{2}$-heavy hitters.

3:Let $\widehat{F_{2}^{(t)}}$ be the output of an $F_{2}$-sketch at time $t$.

4:for each update $a_{t}$ with $t\in[m]$ do

5: if $t=2^{j}-1$ for some integer $j\geq 0$ then

6: Let $H_{j}$ be the output of ${\textsc{CountHHShort}}_{j}$ with parameter
$\frac{\varepsilon}{10}$.

7: Initialize instance
${\textsc{CountHHShort}}_{j+1}(1.01\cdot\widehat{F_{2}^{(t)}},2^{j+1},a_{t+1},\ldots,a_{t+2^{j+1}})$
with parameter $\frac{\varepsilon}{10}$.

8: Discard $H_{j-1}$ and ${\textsc{CountHHShort}}_{j-1}$.

9:Let $j$ be the largest index with an instance ${\textsc{CountHHShort}}_{j}$.

10:return $\left(i,\frac{m}{2^{j}},\widehat{x_{i}}\right)$ in $H_{j-1}$ for
which
$\frac{m}{2^{j}}\cdot\widehat{x_{i}}\geq\left(1-\frac{\varepsilon}{5}\right)\varepsilon\cdot\frac{\sqrt{\widehat{F_{2}^{(m)}}}}{1.01}$.

We now recall a number of key properties shown in [BGW20].

######  Lemma A.1 (No false positives by Identify, Lemma 4 in [BGW20]).

With probability at least $1-1/m$, no instance of Identify reports an element
$j\neq\emptyset$ with $f_{j}^{2}\leq\frac{\varepsilon^{2}}{2}\cdot F_{2}$.

######  Corollary A.2 ($|H|$ is small, Corollary 29 in [BGW20]).

With probability at least $1-1/m$, we have $|H|\leq 2\varepsilon^{-2}$ at all
times during the stream.

######  Lemma A.3 (Heavy-hitters in consecutive blocks, Lemma 5 in [BGW20]).

Let $HH$ be the set of items $j$ with $f_{j}^{2}\geq\varepsilon^{2}\cdot
F_{p}$. With probability at least $1-1/\sqrt{m}$, we simultaneously have for
all $j\in HH$ and every sequence of $4000\varepsilon^{-2}\ln m$ consecutive
blocks, $B_{i+1},\ldots,B_{i+4000\varepsilon^{-2}\ln m}$, that coordinate $j$
appears in at least $4000(1.01/\sqrt{2})\varepsilon^{-2}\ln m$ of these
blocks.

######  Lemma A.4 (Accuracy of heavy-hitter estimations, Lemma 6 in [BGW20]).

With probability at least $1-1/m^{98}$, we simultaneously have for all $j$
with $f_{j}^{2}\geq\frac{\varepsilon^{2}}{2}\cdot F_{2}$ and every sequence of
$p:=4000\varepsilon^{-2}\ln m$ consecutive blocks, the number of occurrences
$\xi$ of $j$ in $\uplus_{v=1}^{p}B_{i+\ell+v}$ satisfies
$\xi\in(1\pm\varepsilon)\cdot\frac{p\cdot
f_{j}}{\varepsilon\sqrt{\tilde{F_{2}}}}$.

######  Lemma A.5 (Identification of heavy-hitters, Lemma 7 in [BGW20]).

With probability at least $39/40$, simultaneously for all $j\in HH$, there
exists some $q\in[10\ln(1/\varepsilon)]$ such that:

  1. (1)

$h^{q}(j)=i$ with $e^{i}=0$ and $g(j)\in S^{i}$ after $B_{i}$ is processed

  2. (2)

$g(j)$ is the unique value $k\in S^{i}$ with $c^{i}(k)=1$

  3. (3)

No instance of Identify is already running and $|H|\leq 2\varepsilon^{-2}$.

Together, these statements give the following guarantees: See 2.1