# Streaming Algorithms with Few State Changes

Rajesh Jayaram Google Research. E-mail<EMAIL_ADDRESS>David P. Woodruff
Carnegie Mellon University and Google Research. E-mail<EMAIL_ADDRESS>Samson Zhou Texas A&M University. Work done in part while at UC Berkeley and
Rice University. E-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we study streaming algorithms that minimize the number of
changes made to their internal state (i.e., memory contents). While the design
of streaming algorithms typically focuses on minimizing space and update time,
these metrics fail to capture the asymmetric costs, inherent in modern
hardware and database systems, of reading versus writing to memory. In fact,
most streaming algorithms write to their memory on _every update_ , which is
undesirable when writing is significantly more expensive than reading. This
raises the question of whether streaming algorithms with small space _and_
number of memory writes are possible.

We first demonstrate that, for the fundamental $F_{p}$ moment estimation
problem with $p\geq 1$, any streaming algorithm that achieves a constant
factor approximation must make $\Omega(n^{1-1/p})$ internal state changes,
regardless of how much space it uses. Perhaps surprisingly, we show that this
lower bound can be matched by an algorithm that also has near-optimal space
complexity. Specifically, we give a $(1+\varepsilon)$-approximation algorithm
for $F_{p}$ moment estimation that uses a near-optimal
$\widetilde{\mathcal{O}}_{\varepsilon}(n^{1-1/p})$ number of state changes,
while simultaneously achieving near-optimal space, i.e., for $p\in[1,2]$, our
algorithm uses $\text{poly}\left(\log n,\frac{1}{\varepsilon}\right)$ bits of
space, while for $p>2$, the algorithm uses
$\widetilde{\mathcal{O}}_{\varepsilon}(n^{1-2/p})$ space. We similarly design
streaming algorithms that are simultaneously near-optimal in both space
complexity and the number of state changes for the heavy-hitters problem,
sparse support recovery, and entropy estimation. Our results demonstrate that
an optimal number of state changes can be achieved without sacrificing space
complexity.

##  1 Introduction

The streaming model of computation is a central paradigm for computing
statistics for datasets that are too large to store. Examples of such datasets
include internet traffic logs, IoT sensor networks, financial transaction
data, database logs, and scientific data streams (such as huge experiments in
particle physics, genomics, and astronomy). In the one-pass streaming model,
updates to an underlying dataset are processed by an algorithm one at a time,
and the goal is to approximate, collect, or compute some statistic of the
dataset while using space that is sublinear in the size of the dataset (see
[BBD+02, M+05] for surveys).

Formally, an insertion-only data stream is modeled by a sequence of updates
$u_{1},\ldots,u_{m}$, each of the form $u_{t}\in[n]$ for $t\in[m]$, where
$[n]=\\{1,\ldots,n\\}$ is the universe size. The updates implicitly define an
underlying frequency vector $f\in\mathbb{R}^{n}$ by
$f_{i}=|\\{t\,\mid\,u_{t}=i\\}|$, so that the value of each coordinate of the
frequency vector is the number of occurrences of the coordinate identity in
the data stream.

One of the most fundamental problems in the streaming literature is to compute
a $(1+\varepsilon)$ approximation of the $F_{p}$ moment of the underlying
frequency vector $f$, defined by $F_{p}(f)=(f_{1})^{p}+\ldots+(f_{n})^{p}$,
where $\varepsilon>0$ is an accuracy parameter. The frequency moment
estimation problem has been the focus of more than two decades of study in the
streaming model [AMS99, BJKS04, Woo04, IW05, Ind06, Li08, KNW10, LW13, BDN17,
BVWY18, GW18, JW18a, JW19, WZ21a, WZ21b, ABJ+22, BJWY22]. In particular,
$F_{p}$-estimation is used for $p=0.25$ and $p=0.5$ in mining tabular data
[CIKM02], for $p=1$ in network traffic monitoring [FKSV02] and dynamic earth-
mover distance approximation [Ind04], and for $p=2$ in estimating join and
self-join sizes [AGMS02] and in detecting network anomalies [TZ04]. Note that
a $(1+\varepsilon)$-approximation to the $F_{p}$ moment also gives a
$(1+\mathcal{O}\left(\varepsilon\right))$-approximation to the $L_{p}$ norm of
$f$, defined by

$L_{p}(f)=\|f\|_{p}=\left(F_{p}(f)\right)^{1/p}=\left((f_{1})^{p}+\ldots+(f_{n})^{p}\right)^{1/p}.$

Another fundamental streaming problem is to compute $L_{p}$-heavy hitters:
given a threshold parameter $\varepsilon\in(0,1]$, the $L_{p}$-heavy hitters
problem is to output a list $L$ containing all $j\in[n]$ such that
$f_{j}\geq\varepsilon\cdot\|f\|_{p}$, and no $j\in[n]$ with
$f_{j}<\frac{\varepsilon}{2}\cdot\|f\|_{p}$. The heavy-hitter problem is used
for answering iceberg queries [FSG+98] in database systems, finding elephant
flows and spam prevention in network traffic monitoring [BEFK17], and perhaps
has an even more extensive history than the $F_{p}$ moment estimation problem
[MG82, BM91, CCF04, CM05, MAA05, MM12, Ind13, BCIW16, LNNT16, BCI+17, BGL+18,
LNW18, INW22, BLMZ23, LT23].

The primary goal of algorithmic design for the streaming model is to minimize
the space and update time of the algorithm. However, the generic per-update
processing time fails to capture the nuanced reality of many modern database
and hardware systems, where the _type_ of updates that are made on a time step
matter significantly for the real-world performance of the algorithm.
Specifically, it is typically the case that updates that only require reads to
the memory contents of the algorithm are significantly faster than updates
that also modify the memory of the algorithm, i.e., writes. Thus, while many
streaming problems are well-understood in terms of their space and update
time, little is known about their write complexity: namely, the number of
state changes made over the course of the stream.

In this paper, we propose the number of state changes of a streaming algorithm
as a complexity-theoretic parameter of interest, and make the case for its
importance as a central object of study, in addition to the space and update-
time of an algorithm. While there is significant practical motivation for
algorithms that update their internal state infrequently (see Section 1.1 for
a discussion), from a theoretical perspective it is not clear that having few
state changes is even possible. Specifically, most known streaming algorithms
write to their memory contents on _every_ update of the stream. Moreover, even
if algorithms using fewer state changes existed, such algorithms would not be
useful if they required significantly more space than prior algorithms that do
not minimize the number of state changes. Therefore, we ask the following
question:

> Is it possible to design streaming algorithms that make few updates to their
> internal state in addition to being space-efficient?

Our main contribution is to answer this question positively. Specifically, we
demonstrate that algorithms exist that are simultaneously near-optimal in
their space and state-change complexity. This demonstrates further that we do
not need to pay extra in the space complexity to achieve algorithms with few
state changes.

###  1.1 Motivation for Minimizing State Changes

#### Asymmetric read/write costs of non-volatile memory.

The primary motivation of minimizing state changes arises from the simple
observation that different actions performed over the same allocated memory
may have different costs. For example, non-volatile memory (NVM) is low
latency memory that can be retained when power to the system is turned off and
therefore can dramatically increase system performance. Although NVM offers
many benefits over dynamic random access memory (DRAM), writing to NVM is
significantly more costly than reading from NVM, incurring higher energy
costs, higher latency, and suffering lower per-chip bandwidth [BFG+15]. In
fact, [MSCT14] noted that an NVM cell generally wears out between $10^{8}$ and
$10^{12}$ writes. Hence, in contrast to DRAM, NVM has a significant asymmetry
between read and write operation costs [DWS+08, DJX09, ACM+11, QGR11, XDJX11,
ABCR12, KSDC14], which has been the focus of several works in system design
[YLK+07, CL09, LIMB09, ZZYZ09] and database data structure design [CGN11,
Vig12, Vig14].

One specific type of non-volatile memory is NAND flash memory, which is an
electronic memory storage unit that can be electrically erased, written, and
read in blocks that are generally significantly smaller than the entire
device. NAND flash memory can be found in a number of common devices, such as
smartphones, USB flash drives, memory cards, or solid-state drives. However,
[BT11] notes that, at the time, individual NAND flash memory cells would wear
out after $10^{4}$ to $10^{6}$ write/erase operations. Indeed, Apple notes
that “all iOS devices and some macOS devices use a solid-state drive (SSD) for
permanent storage” and recommends minimizing disk writes to optimize device
performance [App23]. Although a line of work considered wear leveling to limit
memory wear [Cha07, CHK07, INR92], they did not immediately produce high-
probability wear guarantees, thus motivating work that focused on hashing
algorithms that choose which memory cell to write/overwrite each item,
depending on the previous number of writes already incurred by that cell
[EGMP14]. Subsequently, the development of specific system software, e.g., the
garbage collector, virtual memory manager, or virtual machine hypervisor,
automatically handled balancing write operations across memory cells over long
time horizons, so that an individual cell would not fail much faster than the
overall unit. Therefore, subsequent works focused on minimizing the overall
number of write operations [BFG+15] to the device rather than minimizing the
number of write operations to a specific cell.

#### Asymmetric read/write costs of large data storage systems.

Power consumption is a major consideration for large enterprise data storage
subsystems, which can often impact the density of servers and the total cost
of ownership [ZCT+05, CYW+12]. In [BHK+91], it was observed that given steady
hit ratios of read operations, write operations will eventually dominate file
system performance and thus be the main source of power consumption. Indeed,
[NDR08, TDN11] noted that there are substantial periods of time where all the
traffic in the request stream to the Microsoft data storage centers servicing
applications, such as Hotmail and Messenger, is write traffic.

In addition, for distributed data systems that each serve a number of clients,
even when one server is updated, they must periodically notify the other
servers about their changes to maintain some level of synchronization across
the entire system. Therefore, write operations to a single server can still
induce expensive overheads from communication costs between servers, and thus,
reducing the number of writes has long been a goal in disk arrays, distributed
systems, and cache-coherent multiprocessors.

#### Challenges with deterministic algorithms.

From a theoretical perspective, minimizing the number of internal state
changes immediately rules out a large class of deterministic streaming
algorithms. For example, counting the stream length can be performed
deterministically by simply repeatedly updating a counter over the course of a
stream. Similarly, $L_{1}$-heavy hitters can be tracked deterministically and
in sublinear space using the well-known Misra-Gries data structure [MG82].
Another example is the common merge-and-reduce technique for clustering in the
streaming model, which can be implemented deterministically if the coreset
construction in each reduce step is deterministic. Other problems such as
maintaining Frequent Directions [GLPW16] or $L_{2}$ regression in the row
arrival model [BDM+20, BFL+23] also admit highly non-trivial deterministic
algorithms that use sublinear space. However, these approaches all update the
algorithm upon each stream update and thus seem inherently at odds with
achieving a sublinear number of internal state changes over the course of the
stream.

#### Relationship with sampling.

On the other hand, sampling-based algorithms inherently seem useful for
minimizing the number of internal state changes. There are a number of
problems that admit sublinear-size coresets based on importance sampling, such
as clustering [BFLR19, BFL+21, CAWZ23], graph sparsification [AG09, BHM+21],
linear regression [CMP20], $L_{p}$ regression [WY23], and low-rank
approximation [BDM+20]. These algorithms generally assign some value
quantifying the “importance” of each stream update as it arrives and then
sample the update with probability proportional to the importance. Thus if
there are few additional operations, then the number of internal state changes
can be as small as the overall data structure maintained by the streaming
algorithm. On the other hand, it is not known that space-optimal sampling
algorithms exist for a number of other problems that admit sublinear-space
streaming algorithms, such as $F_{p}$ estimation, $L_{p}$-heavy hitters,
distinct elements, and entropy estimation. Hence, a natural question is to ask
whether there exist space-optimal streaming algorithms for all of these
problems that also incur a small number of internal state changes.

###  1.2 Our Contributions

In this work, we initiate the study of streaming algorithms that minimize
state changes, and demonstrate the existence of algorithms which achieve
optimal or near-optimal space bounds while simultaneously achieving an optimal
or near optimal number of internal state changes.

#### Heavy-hitters.

We first consider the $L_{p}$-heavy hitters problem, where the goal is to
output estimates $\widehat{f_{j}}$ to the frequency $f_{j}$ of every item
$j\in[n]$ such that
$\left\lvert\widehat{f_{j}}-f_{j}\right\rvert\leq\frac{\varepsilon}{2}\cdot\|f\|_{p}$,
given an input accuracy parameter $\varepsilon\in(0,1)$. Accurate estimation
of the heavy-hitter frequencies is important for many other streaming
problems, such as moment estimation, $L_{p}$ sampling [AKO11, JW18b, JWZ22],
cascaded norms [JW09, JLL+20], and others. Note that under such a guarantee,
along with a $2$-approximation of $\|f\|_{p}$, we can automatically output a
list that contains all $j\in[n]$ such that
$f_{j}\geq\varepsilon\cdot\|f\|_{p}$ but also no index $j\in[n]$ such that
$f_{j}<\frac{\varepsilon}{4}\cdot\|f\|_{p}$. We defer discussion of how to
obtain a $2$-approximation to $\|f\|_{p}$ for the moment and instead focus on
the additive error guarantee for all $\widehat{f_{j}}$. Our main result for
the heavy hitters problem is the following:

######  Theorem 1.1.

Given a constant $p\geq 1$, there exists a one-pass insertion-only streaming
algorithm that has
$\mathcal{O}\left(n^{1-1/p}\right)\cdot\operatorname*{poly}\left(\log(nm),\frac{1}{\varepsilon}\right)$
internal state changes, and solves the $L_{p}$-heavy hitter problem, i.e., it
outputs a frequency vector $\widehat{f}$ such that

$\mathbf{Pr}\left[\|\widehat{f}-f\|_{\infty}\leq\frac{\varepsilon}{2}\cdot\|f\|_{p}\right]\geq\frac{2}{3}.$

For $p\in[1,2]$, the algorithm uses
$\mathcal{O}\left(\frac{1}{\varepsilon^{4+4p}}\right)\cdot\operatorname*{polylog}(mn)$
bits of space, while for $p>2$, the algorithm uses
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4+4p}}n^{1-2/p}\right)$ bits
of space.

We next give a lower bound showing that any algorithm solving the
$L_{p}$-heavy hitters problem requires $\Omega(n^{1-1/p})$ state updates.

######  Theorem 1.2.

Let $\varepsilon\in(0,1)$ be a constant and $p\geq 1$. Any algorithm that
solves the $L_{p}$-heavy hitters problem with threshold $\varepsilon$ with
probability at least $\frac{2}{3}$ requires at least
$\frac{1}{2\varepsilon}n^{1-1/p}$ state updates.

Together, Theorem 1.1 and Theorem 1.2 show that we achieve a near-optimal
number of internal state changes. Furthermore, [BIPW10, JST11] showed that for
any $p>0$, the $L_{p}$-heavy hitters problem requires
$\Omega\left(\frac{1}{\varepsilon^{p}}\log n\right)$ words of space, while
[BJKS04, Gro09, Jay09] showed that for $p>2$ and even for constant
$\varepsilon>0$, the $L_{p}$-heavy hitters problem requires
$\Omega\left(n^{1-2/p}\right)$ words of space. Therefore, Theorem 1.1 is near-
optimal for all $p\geq 1$, for both the number of internal state updates and
the memory usage.

#### Moment estimation.

We then consider the $F_{p}$ moment estimation problem, where the goal is to
output an estimate of $F_{p}(f)=(f_{1})^{p}+\ldots+(f_{n})^{p}$ for a
frequency vector $f\in\mathbb{R}^{n}$ implicitly defined through an insertion-
only stream. Our main result is the following:

######  Theorem 1.3.

Given a constant $p\geq 1$, there exists a one-pass insertion-only streaming
algorithm that has $\tilde{\mathcal{O}}\left(n^{1-1/p}\right)$ internal state
changes, and outputs $\widehat{F_{p}}$ such that

$\mathbf{Pr}\left[\left\lvert\widehat{F_{p}}-F_{p}\right\rvert\leq\varepsilon\cdot
F_{p}\right]\geq\frac{2}{3}.$

For $p\in[1,2]$, the algorithm uses
$\mathcal{O}\left(\frac{1}{\varepsilon^{4+4p}}\right)\cdot\operatorname*{polylog}(mn)$
bits of space, while for $p>2$, the algorithm uses
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4+4p}}n^{1-2/p}\right)$ space.

We next give a lower bound showing that any approximation algorithm achieving
$(2-\Omega(1))$-approximation to $F_{p}$ requires $\Omega(n^{1-1/p})$ state
updates.

######  Theorem 1.4.

Let $\varepsilon\in(0,1)$ be a constant and $p\geq 1$. Any algorithm that
achieves a $2-\varepsilon$ approximation to $F_{p}$ with probability at least
$\frac{2}{3}$ requires at least $\frac{1}{2}n^{1-1/p}$ state updates.

Theorem 1.4 shows that our algorithm in Theorem 1.3 achieves a near-optimal
number of internal state changes. Moreover, it is known that any one-pass
insertion-only streaming algorithm that achieves
$(1+\varepsilon)$-approximation to the $F_{p}$ moment estimation problem
requires $\Omega\left(\frac{1}{\varepsilon^{2}}+\log n\right)$ bits of space
[AMS99, Woo04] for $p\in[1,2]$ and
$\Omega\left(\frac{1}{\varepsilon^{2}}n^{1-2/p}\right)$ bits of space [WZ21a]
for $p>2$, and thus Theorem 1.3 is also near-optimal in terms of space for all
$p\geq 1$.

###  1.3 Technical Overview

#### Heavy-hitters.

We first describe our algorithm for $L_{p}$-heavy hitters using near-optimal
space and a near-optimal number of internal state changes. For ease of
discussion, let us assume that $F_{p}=\widetilde{\Theta}_{\varepsilon}(n)$, so
that the goal becomes to identify the coordinates $j\in[n]$ with
$f_{j}\geq\varepsilon\cdot n^{1/p}$, given an input accuracy parameter
$\varepsilon\in(0,1)$.

We first define a subroutine SampleAndHold based on sampling a number of items
into a reservoir $Q$. As we observe updates in the stream, we sometimes update
the contents of $Q$ and sometimes observe that some stream updates are to
coordinates that are being held by the reservoir. For the items that have a
large number of stream updates while they are being held by the reservoir, we
create separate counters for these items.

We first describe the intuition for $p>2$. We create a reservoir $Q$ of size
$\kappa=\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$ and sample each
item of the stream into the reservoir $Q$ with probability roughly
$\widetilde{\Theta}_{\varepsilon}\left(\frac{1}{n^{1/p}}\right)$. Note that at
some point we may attempt to sample an item of the stream into the reservoir
$Q$ when the latter is already full. In this case, we choose a uniformly
random item of $Q$ to be replaced by the item corresponding to the stream
update.

Our algorithm also checks each stream update to see if it matches an item in
the reservoir; if there is a match, we create an explicit counter tracking the
frequency of the item. In other words, if $j\in[n]$ arrives as a stream update
and $j\in Q$ is in the reservoir, then our algorithm SampleAndHold creates a
separate counter for $j$ to count the number of subsequent instances of $j$.

Now for a heavy hitter $j\in[n]$, we have $f_{j}\geq\varepsilon\cdot n^{1/p}$
and thus since the sampling probability is
$\widetilde{\Theta}_{\varepsilon}\left(\frac{1}{n^{1/p}}\right)$, then we can
show that $j$ will likely be sampled into our reservoir $Q$ at some point. In
fact, since the reservoir $Q$ has size
$\kappa=\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$, then in
expectation, $j$ will be retained by the reservoir for roughly
$\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$ stream updates before it is
possibly replaced by some other item. Moreover, since
$f_{j}\geq\varepsilon\cdot n^{1/p}$, then we should expect another instance of
$j$ to arrive in $\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$ additional
stream updates, where the expectation is taken over the randomness of the
sampled positions, under the assumption that $F_{p}=\Theta(n)$, which implies
also that the stream length is at most $\mathcal{O}\left(n\right)$. Therefore,
our algorithm will create a counter for tracking $j$ before $j$ is removed
from the reservoir $Q$. Furthermore, we can show that the counter for $j$ is
likely created sufficiently early in the stream to provide a
$(1+\varepsilon)$-approximation to the frequency $f_{j}$ of $j$. Then to
decrease the number of internal state updates, we can use Morris counters to
approximate the frequency of subsequent updates for each tracked item.

#### Counter maintenance for heavy-hitters.

The main issue with this approach is that too many counters can be created. As
a simple example, consider when all items of each coordinate arrive together,
one item after the other. Although this is a simple case for counting heavy-
hitters, our algorithm will create counters for almost any item that it
samples, and although our reservoir uses space
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$, the total number of
items sampled over the course of the stream is
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-1/p})$ and thus the number of
created counters can also be
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-1/p})$, which would be too much
space. We thus create an additional mechanism to remove half of the counters
each time the number of counters becomes too large, i.e., exceeds
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$.

The natural approach would be to remove half of the counters with the smallest
tracked frequencies. However, one could imagine a setting where $m=\Theta(n)$
and the $p$-th moment of the stream is also $\Theta(n)$, but there exists a
heavy-hitter with frequency $\Theta(n^{1/p})$ that appears every
$\Theta(n^{1-1/p})$ updates. In this case, even if the heavy-hitter is
sampled, its corresponding counter will be too low to overcome the other
counters in the counter maintenance stage. Therefore, we instead remove the
counters with the smallest tracked frequencies for each set of counters that
have been maintained for a number of steps between $2^{z}$ and $2^{z+1}$ for
each integer $z\geq 0$, which overcomes per-counter analysis in similar
algorithms based on sampling [BO13, BKSV14].

Since our algorithm samples each item of the stream of length
$\mathcal{O}\left(n\right)$ with probability
$\frac{1}{\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1/p})}$, then we expect
our reservoir to have $\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$ internal
state changes. On the other hand, the counters can increment each time another
instance of the tracked item arrives. To that end, we replace each counter
with an approximate counter that has a small number of internal state changes.
In particular, by using Morris counters as mentioned above, the number of
internal state changes for each counter is $\operatorname*{poly}\left(\log
n,\frac{1}{\varepsilon},\log\frac{1}{\delta}\right)$ times over the course of
the stream. Therefore, the total number of internal state changes is
$\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$ while the total space used is
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$.

For $p\in[1,2]$, we instead give the reservoir $Q$ a total of
$\kappa=\operatorname*{poly}_{\varepsilon}(\log n)$ size, so that the total
space is $\operatorname*{poly}_{\varepsilon}(\log n)$ while the total number
of internal state changes remains
$\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$.

#### Removing moment assumptions.

To remove the assumption that
$F_{p}=\widetilde{{\mathcal{O}}}_{\varepsilon}(n)$, we note that if each
element of the stream of length $m$ is sampled with probability $q<1$, then
the expected number of sampled items is $qm$, but the $p$-th power of the
expected number of sampled items is $(qm)^{p}$. Although this is not the
$p$-th moment of the stream, we nevertheless can expect the $F_{p}$ moment of
the stream to decrease at a faster rate than the number of sampled items. Thus
we create $L=\mathcal{O}\left(\log(nm)\right)$ substreams so that for each
$\ell\in[L]$, we subsample each stream update $[m]$ with probability
$\frac{1}{2^{\ell-1}}$. For one of these substreams $J_{\ell}$, we will have
$F_{p}(J_{\ell})=\widetilde{{\mathcal{O}}}_{\varepsilon}(n)$. We show that we
can estimate the frequency of the heavy-hitters in the substream $J_{\ell}$
and then rescale by the inverse sampling rate to achieve a
$(1+\varepsilon)$-approximation to the frequency of the heavy-hitters in the
original stream.

It then remains to identify the correct stream $\ell$ such that
$F_{p}(J_{\ell})=\widetilde{{\mathcal{O}}}_{\varepsilon}(n)$. A natural
approach would be to approximate the moment of each substream, to identify
such a correct stream. However, it turns out that our $F_{p}$ moment
estimation algorithm will ultimately use our heavy hitter algorithm as a
subroutine. Furthermore, other $F_{p}$ moment estimation algorithms, e.g.,
[AMS99, Ind06, Li08, GW18], use a number of internal state changes that is
linear in the stream length and it is unclear how to adapt these algorithms to
decrease the number of internal state changes. Instead, we note that with high
probability, the estimated frequency of each heavy-hitter by our algorithm can
only be an underestimate. This is because if we initialize counters throughout
the stream to track the heavy hitters, then our counters might miss some
stream updates to the heavy hitters, but it is not possible to overcount the
frequency of each heavy hitter, i.e., we cannot count stream updates that do
not exist. Moreover, this statement is still true, up to a $(1+\varepsilon)$
factor, when we use approximate counters. Therefore, it suffices to use the
maximum estimation for the frequency for each heavy hitter, across all the
substreams. We can then use standard probability boosting techniques to
simultaneously accurately estimate all $L_{p}$-heavy hitters.

#### Moment estimation.

Given our algorithm for finding $(1+\varepsilon)$-approximations to the
frequencies of $L_{p}$-heavy hitters, we now adapt a standard subsampling
framework [IW05] to reduce the $F_{p}$ approximation problem to the problem of
finding the $L_{p}$-heavy hitters. The framework has subsequently been used in
a number of different applications, e.g., [WZ12, BBC+17, LSW18, BWZ21, WZ21a,
MWZ22, BMWZ23] and has the following intuition.

For ease of discussion, consider the level set $\Gamma_{i}$ consisting of the
coordinates $j\in[n]$ such that
$f_{j}\in\left(\frac{F_{p}}{2^{i}},\frac{F_{p}}{2^{i+1}}\right]$ for each $i$,
though we remark that for technical reasons, we shall ultimately define the
level sets in a slightly different manner. Because the level sets partition
the universe $[n]$, then if we define the contribution
$C_{i}:=\sum_{j\in\Gamma_{i}}(f_{k})^{p}$ of a level set $\Gamma_{i}$ to be
the sum of the contributions of all their coordinates, then we can decompose
the moment $F_{p}$ into the sum of the contributions of the level sets,
$F_{p}=\sum_{i}C_{i}$. Moreover, it suffices to accurately estimate the
contributions of the “significant” level sets, i.e., the level sets whose
contribution is at least a
$\operatorname*{poly}\left(\varepsilon,\frac{1}{\log(nm)}\right)$ fraction of
the $F_{p}$ moment, and crudely estimate the contributions of the
insignificant level sets.

[IW05] observed that the contributions of the significant level sets can be
estimated by approximating the frequencies of the heavy hitters for substreams
induced by subsampling the universe at exponentially smaller rates. We
emphasize that whereas we previously subsampled updates of the stream $[m]$
for heavy hitters, we now subsample elements of the universe $[n]$. That is,
we create $L=\mathcal{O}\left(\log(nm)\right)$ substreams so that for each
$\ell\in[L]$, we subsample each element of the universe $[n]$ into the
substream with probability $\frac{1}{2^{\ell-1}}$. For example, a single item
with frequency $F_{p}^{1/p}$ will be a heavy hitter in the original stream,
which is also the stream induced by $\ell=1$. On the other hand, if there are
$n$ items with frequency $(F_{p}/n)^{1/p}$, then they will be $L_{p}$-heavy
hitters at a subsampling level where in expectation, there are roughly
$\Theta\left(\frac{1}{\varepsilon^{p}}\right)$ coordinates of the universe
that survive the subsampling. Then [IW05] notes that
$(1+\varepsilon)$-approximations to the contributions of the surviving heavy-
hitters can then be rescaled inversely by the sampling rate to obtain good
approximations of the contributions of each significant level set. The same
procedure also achieves crude approximations for the contributions of
insignificant level sets, which overall suffices for a
$(1+\varepsilon)$-approximation to the $F_{p}$ moment.

The key advantage in adapting this framework over other $F_{p}$ estimation
algorithms, e.g., [AMS99, Ind06, Li08, GW18] is that we can then use our heavy
hitter algorithm FullSampleAndHold to provide $(1+\varepsilon)$-approximations
to the heavy hitters in each substream while guaranteeing a small number of
internal state changes.

###  1.4 Additional Intuition and Comparison with Previous Algorithms

There are a number of differences between our algorithm and the sample-and-
hold approach of [EV02]. Firstly, once [EV02] samples an item, a counter will
be initialized and maintained indefinitely for that item. By comparison, our
algorithm will sample more items than the total space allocated to the
algorithm, so we must carefully delete a number of sampled items. In
particular, it is NOT correct to delete the sampled items with the largest
counter. Secondly, [EV02] updates a counter each time a subsequent instance of
the sample arrives. Because our paper is focused on a small number of internal
state changes, our algorithm cannot afford such a large number of updates.
Instead, we maintain approximate counters that sacrifice accuracy in exchange
for a smaller number of internal state changes. We show that the loss in
accuracy can be tolerated in choosing which samples to delete.

Another possible point of comparison is the precision sampling technique of
[AKO11], which is a linear sketch, so although it has an advantage of being
able to handle insertion-deletion streams, unfortunately it must also be
updated for each stream element arrival, resulting in a linear number of
internal state changes. Similarly, a number of popular heavy-hitter algorithms
such as Misra-Gries [MG82], CountMin [CM05], CountSketch [CCF04], and
SpaceSaving [MAA05] can only achieve a linear number of internal state
changes. By comparison, our sample-and-hold approach results in a sublinear
number of internal state changes.

Finally, several previous algorithms are also based on sampling a number of
items throughout the stream, temporarily maintaining counters for those items,
and then only keeping the items that are globally heavy, e.g., [BO13, BKSV14].
It is known that these algorithms suffer a bottleneck at $p=3$, i.e., they
cannot identify the $L_{p}$ heavy-hitters for $p<3$. The following
counterexample shows why these algorithms cannot identify the $L_{2}$ heavy-
hitters and illustrates a fundamental difference between our algorithms.

Suppose the stream consists of $\sqrt{n}$ blocks of $\sqrt{n}$ updates. Among
these updates, there are $\sqrt{n}$ items with frequency $n^{1/4}$, which we
call pseudo-heavy. There is a single item with frequency $\sqrt{n}$, which is
the heavy-hitter. Then the remaining items each have frequency $1$ and are
called light. Note that the second moment of the stream is $\Theta(n)$, so
that only the item with frequency $\sqrt{n}$ is the heavy-hitter, for constant
$\varepsilon<1$.

Let $S=\\{1,2,\ldots,n^{1/4}\\}$ and suppose for each $w\in S$, block $w$ is a
special block that consists of $n^{1/4}$ different pseudo-heavy items, each
with frequency $n^{1/4}$. Let $T=x+S$, for $x=\\{1,2,\ldots,n^{1/8}\\}$, so
that $T$ consists of the $n^{1/8}$ blocks after each special block. Each block
in $T$ consists of $n^{1/8}$ instances of the heavy-hitter, along with
$\sqrt{n}-n^{1/8}$ light items. The remaining blocks all consist of light
items.

Observe that without dynamic maintenance of counters for different scales, in
each special block, we will sample $\operatorname*{polylog}(n)$ pseudo-heavy
items whose counters each reach about
$\tilde{\mathcal{O}}\left(n^{1/4}\right)$. But then each time a heavy-hitter
is sampled, its count will not exceed the pseudo-heavy item before the number
of counters before it is deleted, because it only has $n^{1/8}$ instances in
its block. Thus with high probability, the heavy-hitter will never be found,
and this is an issue with previously existing sampling-based algorithms, e.g.,
[BO13, BKSV14].

Our algorithm overcomes this challenge by only performing maintenance on
counters that have been initialized for a similar amount of time. Thus in the
previous example, the counters for the heavy-hitters will not be deleted
because they are not compared to the counters for the pseudo-heavy items until
the heavy-hitters have sufficiently high frequency. By comparison, existing
algorithms will retain counters for the pseudo-heavy items, because they
locally look “larger”, at the expense of the true heavy-hitter.

Reference | State Changes | Setting
---|---|---
[MG82] | $\mathcal{O}\left(m\right)$ |  $L_{1}$-Heavy Hitters Only
[CM05] | $\mathcal{O}\left(m\right)$ |  $L_{1}$-Heavy Hitters Only
[MAA05] | $\mathcal{O}\left(m\right)$ |  $L_{1}$-Heavy Hitters Only
[CCF04] | $\mathcal{O}\left(m\right)$ |  $L_{2}$-Heavy Hitters
Our Work | $\tilde{\mathcal{O}}\left(n^{1-1/p}\right)$ |  $L_{2}$-Heavy Hitters
Table 1: Summary of our results compared to existing results for a stream of
length $m$ on a universe of size $n$. We emphasize that reporting $L_{2}$
heavy-hitters includes the $L_{1}$ heavy-hitters. All algorithms use near-
optimal space.

###  1.5 Preliminaries

We use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$ for an integer $n>0$. We
write $\operatorname*{poly}(n)$ to denote a fixed univariate polynomial in $n$
and similarly, $\operatorname*{poly}(n_{1},\ldots,n_{k})$ to denote a fixed
multivariate polynomial in $n_{1},\ldots,n_{k}$. We use
$\tilde{\mathcal{O}}\left(f(n_{1},\ldots,n_{k})\right)$ for a function
$f(n_{1},\ldots,n_{k})$ to denote
$f(n_{1},\ldots,n_{k})\cdot\operatorname*{poly}(\log f(n_{1},\ldots,n_{k}))$.
For a vector $f\in\mathbb{R}^{n}$, we use $f_{i}$ for $i\in[n]$ to denote the
$i$-th coordinate of $f$.

#### Model.

In our setting, an insertion-only stream $S$ consists of a sequence of updates
$u_{1},\ldots,u_{m}$. In general, we do not require $m$ to be known in
advance, though in some cases, we achieve algorithmic improvements when a
constant-factor upper bound on $m$ is known in advance; we explicitly clarify
the setting in these cases. For each $t\in[m]$, we have $u_{t}\in[n]$, where
without loss of generality, we use $[n]$ to represent an upper bound on the
universe, which we assume to be known in advance. The stream $S$ defines a
frequency vector $f\in\mathbb{R}^{n}$ by $f_{i}=|\\{t\,\mid\,u_{t}=i\\}|$, so
that for each $i\in[n]$, the $i$-th value of the frequency vector $S$ is how
often $i$ appears in the data stream $S$. Observe that through a simple
reduction, this model suffices to capture the more general case where some
coordinate is increased by some amount in $\\{1,\ldots,M\\}$ for some integer
$M>0$ in each update.

For a fixed algorithm ${\mathcal{A}}$, suppose that at each time $t\in[m]$,
the algorithm ${\mathcal{A}}$ maintains a memory state $\sigma_{t}$. Let
$|\sigma_{t}|$ denote the size of the memory state, in words of space, where
each word of space is assumed to used $\mathcal{O}\left(\log n+\log m\right)$
bits of space. We say the algorithm ${\mathcal{A}}$ uses $s$ words of space or
equivalently, $\mathcal{O}\left(s\log n+\log m\right)$ bits of space, if
$\max_{t\in[m]}|\sigma_{t}|\leq s$. For each $t\in[m]$, let $X_{t}$ be the
indicator random variable for whether the algorithm ${\mathcal{A}}$ changed
its memory state at time $t$. That is, $X_{t}=1$ if
$\sigma_{t}\neq\sigma_{t-1}$ and $X_{t}=0$ if $\sigma_{t}=\sigma_{t-1}$, where
we use the convention $\sigma_{0}=\emptyset$. Then we say the total number of
internal changes by the algorithm ${\mathcal{A}}$ is $\sum_{t=1}^{m}x_{t}$.

We also require the following definition of Morris counters to provide
approximate counting.

######  Theorem 1.5 (Morris counters).

[Mor78, NY22] There exists an insertion-only streaming algorithm (Morris
counter) that uses space (in bits) $\mathcal{O}\left(\log\log
n+\log\frac{1}{\varepsilon}+\log\log\frac{1}{\delta}\right)$ and outputs a
$(1+\varepsilon)$-approximation to the frequency of an item $i$, with
probability at least $1-\delta$. Moreover, the algorithm is updated at most
$\operatorname*{poly}\left(\log
n,\frac{1}{\varepsilon},\log\frac{1}{\delta}\right)$ times over the course of
the stream.

##  2 Heavy Hitters

In this section, we first describe our algorithm for identifying and
accurately approximating the frequencies of the $L_{p}$-heavy hitters.

###  2.1 Sample and Hold

A crucial subroutine for our $F_{p}$ estimation algorithm is the accurate
estimation of heavy hitters. In this section, we first describe such a
subroutine SampleAndHold for approximating the frequencies of the
$L_{p}$-heavy hitters under the assumption that $F_{p}$ is not too large.

We now describe our algorithm for the case $p\geq 2$. Our algorithm creates a
reservoir $Q$ of size
$\kappa=\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$ and samples each
item of the stream into the reservoir $Q$ with probability roughly
$\widetilde{\Theta}_{\varepsilon}\left(\frac{1}{n^{1/p}}\right)$. If the
reservoir $Q$ is full when an item of the stream is sampled, then a uniformly
random item of $Q$ is replaced with the stream update. Thus if the stream has
length $n$, then we will incur
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$ internal state changes
due to the sampling. For stream length $m$, we set the sampling probability to
be roughly $\frac{\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-1/p})}{m}$.

Our algorithm also checks each stream update to see if it matches an item in
the reservoir and creates a counter for the item if there is a match. In other
words, if $j\in[n]$ arrives as a stream update and $j\in Q$ is in the
reservoir, then our algorithm SampleAndHold creates a separate counter for $j$
to count the number of subsequent instances of $j$. In addition, each time the
number of counters becomes too large, i.e., exceeds
$\widetilde{{\mathcal{O}}}_{\varepsilon}(n^{1-2/p})$, we remove half of the
counters that have been maintained for a time between $2^{z}$ and $2^{z+1}$,
for each integer $z>0$. In particular, we remove the counters with the
smallest tracked frequencies for each of the groups. To reduce the number of
internal state changes, we use Morris counters rather than exact counters for
each item.

For $p\in[1,2]$, we set $\kappa=\operatorname*{poly}_{\varepsilon}(\log n)$ to
be the size of the reservoir $Q$, so that the total space is
$\operatorname*{poly}_{\varepsilon}(\log n)$ while the total number of
internal state changes remains $\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$.
Our algorithm SampleAndHold appears in Algorithm 1.

Algorithm 1 SampleAndHold

1:Stream $s_{1},\ldots,s_{m}$ of items from $[n]$, accuracy parameter
$\varepsilon\in(0,1)$, $p\geq 1$

2:Accurate estimation of an $L_{p}$ heavy hitter frequency

3:$\kappa_{1}\leftarrow\Theta\left(\frac{\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$,
$\gamma\leftarrow 2^{20}p$

4:if $m\geq n$ then

5:
$\varrho\leftarrow\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$,
$\kappa_{2}\leftarrow\Theta\left(\frac{n^{1-2/p}\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$

6:else if $m<n$ then

7:
$\varrho\leftarrow\frac{\gamma^{2}m^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$,
$\kappa_{2}\leftarrow\Theta\left(\frac{m^{1-2/p}\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$

8:$\kappa\leftarrow\kappa_{1}$ if $p\in[1,2)$, $\kappa\leftarrow\kappa_{2}$ if
$p\geq 2$

9:$k\sim\operatorname*{Uni}([200p\kappa\log^{2}(nm),202p\kappa\log^{2}(nm)])$

10:$q_{i}\leftarrow\emptyset$ for $i\in[k]$

11:for $t=1$ to $t=m$ do

12: if there is a Morris counter for $s_{t}$ then

13: Update the Morris counter

14: else if there exists $i\in[k]$ with $q_{i}=s_{t}$ then $\triangleright$
item is in the reservoir

15: Start a Morris counter for $s_{t}$ $\triangleright$ hold a counter for the
item

16: else

17: Pick $\mu_{t}\in[0,1]$ uniformly at random

18: if $\mu_{t}<\varrho$ then $\triangleright$ with probability $\varrho$

19: Pick $i\in[k]$ uniformly at random

20: $q_{i}\leftarrow s_{t}$

21: if there exist $k$ active Morris counters initialized between time
$t-2^{z}$ and $t-2^{z+1}$ for integer $z>0$ then $\triangleright$ too many
counters

22:
$k\leftarrow\operatorname*{Uni}([200p\kappa\log^{2}(nm),202p\kappa\log^{2}(nm)])$

23: Retain the $\frac{k}{2}$ counters initialized between time $t-2^{z}$ and
$t-2^{z+1}$ for integer $z>0$ with largest approximate frequency

24:return the estimated frequencies by the Morris counters

We first analyze how many additional counters are available at a time when a
heavy hitter $j$ is sampled.

######  Lemma 2.1.

Let $j\in[n]$ be an item with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$ and let $J=\\{t\in[m]\,\mid\,s_{t}=j\\}$.
Let $k\in[200p\kappa\log^{2}(nm),202p\kappa\log^{2}(nm)]$ be chosen uniformly
at random. Let $v$ be the last time that $j$ is sampled by the algorithm. Then
with probability at least $1-\frac{1}{50p\log^{2}(nm)}$, there are at most
$k-\kappa$ counters at time $v$.

###### Proof.

Consider any fixing of the random samples of the algorithm and the random
choices of $k$, before time $v$. Let $T_{1}<T_{2}<\ldots$ be the sequence of
times when the counters are reset. Note that since
$k\in[200p\kappa\log^{2}(nm),202p\kappa\log^{2}(nm)]$, then each time the
counters are reset, between $[100p\kappa^{2}(nm),101p\kappa\log^{2}(nm)]$
counters are newly allocated. Note that the sequence could be empty, in which
case our claim is vacuously true. For each $T_{i}$, consider the times
${\mathcal{T}}_{i}$ at which additional counters would be created after
$T_{i}$ is fixed if there were no limit to the number of counters. Moreover,
let $u_{i}$ be the choice of $k$ at time $T_{i}$. Note that the first
$100p\kappa\log^{2}(nm)$ of the times in ${\mathcal{T}}_{i}$ are independent
of the choice of $u_{i}$, while latter times in ${\mathcal{T}}_{i}$ may not
actually be sampled due to the choice of $u_{i}$. Let $T_{w}$ be the first
time for which which $v$ appears in the first $101p\kappa\log^{2}(nm)$ terms
of the ${\mathcal{T}}_{w}$. Then with probability at most
$\frac{1}{100p\log^{2}(mn)}$, the choice of $u_{w}$ will be within $\kappa$
indices after $v$ in the sequence ${\mathcal{T}}_{i}$. On the other hand, the
choice of $u_{w}$ could cause $T_{w+1}$ to be before $v$, e.g., if $v$ is the
$(101p\kappa\log^{2}(nm))$-th term and $u_{w}=100\kappa\log^{2}(nm)$, in which
case the same argument shows that with probability at most
$\frac{1}{100p\log^{2}(mn)}$, the choice of $u_{w+1}$ will be within $\kappa$
indices after $v$ in the sequence ${\mathcal{T}}_{w+1}$. Note that since
$u_{w}+u_{w+1}\geq 200p\kappa^{2}(nm)$, then $v$ must appear before $T_{w+2}$.
Therefore by a union bound, with probability at least
$1-\frac{1}{50p\log^{2}(nm)}$, there are at most $k-\kappa$ counters at time
$v$. ∎

We next upper bound how many additional counters are created between the time
a heavy hitter $j$ is sampled until it becomes too large to delete.

######  Lemma 2.2.

Suppose $m\geq n$ and
$F_{p}=\mathcal{O}\left(\frac{n\log^{3}(nm)}{\varepsilon^{4p}}\right)$. Let
$j\in[n]$ be an item with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$. Let $J=\\{t\in[m]\,\mid\,s_{t}=j\\}$ and
let $u\in J$ be chosen uniformly at random and suppose that the algorithm
samples $j$ at time $u$. Then for $p\in[1,2)$, over the choice of $u$ and the
internal randomness of the algorithm, the probability that fewer than
$\kappa_{1}=\mathcal{O}\left(\frac{\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$
new counters are generated after $u$ and before $\frac{\varepsilon^{4}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$ additional instances of $j$ arrive is at
most $1-\frac{1}{100p\log(nm)}$.

Similarly for $p\geq 2$, over the choice of $u$ and the internal randomness of
the algorithm, the probability that fewer than
$\kappa_{2}=\mathcal{O}\left(\frac{n^{1-2/p}\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$
new counters are generated after $u$ and before $\frac{\varepsilon^{4}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$ additional instances of $j$ arrive is at
most $1-\frac{1}{100p\log(nm)}$.

###### Proof.

Let $L=\mathcal{O}\left(p\log(nm)\right)$ and let $\ell\in[L]$ be fixed. Let
$W_{\ell}$ be the items with frequency in $[2^{\ell-1},2^{\ell})$ so that

$W_{\ell}=\\{i\in[n]\,\mid\,f_{i}\in[2^{\ell-1},2^{\ell})\\}.$

and observe that $|W_{\ell}|\leq\frac{F_{p}}{2^{p\ell}}$. Let
$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$ and
$X=\frac{\varepsilon^{2}F_{p}^{1/p}}{2^{14}\gamma^{2}\log^{4}(nm)}$.

We define $B_{1},\ldots,B_{\alpha}$ to be blocks that partition the stream, so
that the $i$-th block includes the items of the stream after the $(i-1)$-th
instance of $f_{j}$, up to and including the $i$-th instance of $f_{j}$. We
therefore have $\alpha=f_{j}+1$.

Observe that since $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$, then we have $f_{j}=\beta X$ for some
$\beta>1$. Since $|W_{\ell}|\leq\frac{F_{p}}{2^{p\ell}}$, then the expected
number of unique items in $W_{\ell}$ contained in a block is at most
$\frac{F_{p}}{2^{p\ell}\alpha}$, conditioned on any fixing of indices that are
sampled. Thus in a block, the conditional expectation of the number of stream
updates that correspond to items in $W_{\ell}$ is at most
$\frac{F_{p}}{2^{(p-1)\ell}\alpha}$, and so the expected number of items in
$W_{\ell}$ that are sampled in a block is at most $\frac{\varrho
F_{p}}{2^{(p-1)\ell}\alpha}$. Therefore, the expected number of retained items
in the previous and following $2^{i}$ blocks for $i\leq\ell$ is at most

$\frac{\varrho
F_{p}}{2^{(p-1)\ell}\alpha}\cdot\min(2^{i},2^{\ell})\leq\frac{\varrho
F_{p}}{2^{(p-2)\ell}\alpha}\leq\frac{2\varrho F_{p}}{2^{(p-2)\ell}X},$

since $\alpha=f_{j}+1$ and by assumption
$(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot F_{p}}{2^{10}\gamma\log^{2}(nm)}$,
but $X=\frac{\varepsilon^{2}F_{p}^{1/p}}{2^{14}\gamma^{2}\log^{4}(nm)}$. For
$i>\ell$, note that since $W_{\ell}$ only contains elements of frequency
$2^{\ell}$, then no elements of $W_{\ell}$ will be retained over $j$ once the
consideration is for $2^{i}>2^{\ell}$ blocks.

For $p\in[1,2)$, note that $2^{\ell}\leq F_{p}^{1/p}$, so that
$\frac{1}{2^{(p-2)\ell}}=2^{(2-p)\ell}\leq F_{p}^{2/p-1}$. Therefore, after
$2^{i}$ blocks, the expected number of items in $W_{\ell}$ is at most
$\frac{2\varrho F_{p}}{2^{(p-2)\ell}X}\leq\frac{2\varrho F_{p}^{2/p}}{X}$. For
$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$ and
$X=\frac{\varepsilon^{2}F_{p}^{1/p}}{2^{14}\gamma^{2}\log^{4}(nm)}$, we have
that the expected number of retained items in the previous and following
$2^{i}$ blocks is at most

$\mathcal{O}\left(\frac{2\gamma^{4}n^{1-1/p}F_{p}^{1/p}\log^{8}(nm)}{\varepsilon^{4}m}\right)=\mathcal{O}\left(\frac{\log^{8+3p}(nm)}{\varepsilon^{4+4p}}\right),$

for $m\geq n$ and
$F_{p}=\mathcal{O}\left(\frac{n\log^{3p}(nm)}{\varepsilon^{4p}}\right)$. By
Markov’s inequality, we have that with probability
$1-\frac{1}{100p\log^{3}(nm)}$ over a random time $u$, the number of counters
for the items with frequency in $[2^{\ell-1},2^{\ell})$ is at most
$\kappa_{1}=\mathcal{O}\left(\frac{\log^{11+3p}(nm)}{\varepsilon^{4+4p}}\right)$
across $2^{i}$ blocks before and after $u$. Thus, by a union bound over all
$i=\mathcal{O}\left(\log m\right)$ and $L=\mathcal{O}\left(p\log(nm)\right)$
choices of $\ell$, we have that with probability at least
$1-\frac{1}{100p\log(nm)}$, $\kappa_{1}$ new counters are generated after $u$.

For $p\geq 2$, we have that the expected number of retained items across
$2^{i}$ blocks is at most $\frac{2\varrho
F_{p}}{2^{(p-2)\ell}X}\leq\frac{2\varrho F_{p}}{X}$. For
$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$ and
$X=\frac{\varepsilon^{2}F_{p}^{1/p}}{2^{14}\gamma^{2}\log^{4}(nm)}$, we have
that the expected number of retained items across $2^{i}$ blocks is at most

$\mathcal{O}\left(\frac{2\gamma^{4}(nF_{p})^{1-1/p}\log^{8}(nm)}{\varepsilon^{4}m}\right)=\mathcal{O}\left(\frac{n^{1-2/p}\log^{8+3p}(mn)}{\varepsilon^{4+4p}}\right),$

for $m\geq n$ and
$F_{p}=\mathcal{O}\left(\frac{n\log^{3p}(nm)}{\varepsilon^{4p}}\right)$. By
Markov’s inequality, we have that with probability
$1-\frac{1}{100p\log^{3}(nm)}$ over a random time $u$, the number of counters
for the items with frequency in $[2^{\ell-1},2^{\ell})$ is at most
$\kappa_{2}=\mathcal{O}\left(\frac{n^{1-2/p}\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$
across $2^{i}$ blocks after $u$. Moreover, observe that the number of counters
generated within $2^{z}$ timesteps is certainly at most the number of counters
generated within $2^{z}$ blocks. Thus, by a union bound over all
$z=\mathcal{O}\left(\log m\right)$ and $L=\mathcal{O}\left(p\log(nm)\right)$
choices of $\ell$, we have that with probability at least
$1-\frac{1}{100p\log(nm)}$, $\kappa_{2}$ new counters are generated after $u$.
∎

By Lemma 2.1 and Lemma 2.2, we have:

######  Lemma 2.3.

Suppose $m\geq n$ and
$F_{p}=\mathcal{O}\left(\frac{n\log^{3}(nm)}{\varepsilon^{4p}}\right)$. Let
$j\in[n]$ be an item with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$. Then with probability at least
$1-\frac{1}{100p\log(nm)}$, the counters are not reset between the times at
which $j$ is sampled and $\frac{\varepsilon^{4}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$ occurrences of $j$ arrive after it is
sampled.

We now claim that a heavy hitter $j$ will be sampled early enough to obtain a
good approximation to its overall frequency.

######  Lemma 2.4.

Suppose
$F_{p}=\mathcal{O}\left(\frac{n\log^{3}(nm)}{\varepsilon^{4p}}\right)$. Let
$j\in[n]$ be an item with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$. Then with probability at least $0.99$,
SampleAndHold outputs $\widehat{f_{j}}$ such that

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

###### Proof.

Note that for the purposes of analysis, we can assume $m\geq n$, since
otherwise if $m<n$, then SampleAndHold essentially redefines $n$ to be the
number of unique items in the induced stream by setting $\varrho$ and $\kappa$
appropriately, even though the overall universe can be larger. Note that
$m\leq 2\left(F_{p}\right)^{1/p}\cdot n^{1-1/p}$.

By assumption, we have $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{7}\gamma\log^{2}(nm)}$ and thus, we certainly have
$f_{j}\geq\frac{\varepsilon\cdot\left(F_{p}\right)^{1/p}}{2^{7}\gamma\log^{2}(nm)}$
for $p\geq 2$ and $\varepsilon\in(0,1)$. Let $T$ be the set of the first
$\frac{\varepsilon}{16\log(nm)}$ fraction of occurrences of $j$, so that

$|T|\geq\frac{\varepsilon^{2}\cdot\left(F_{p}\right)^{1/p}}{2^{11}\gamma\log^{3}(nm)}.$

We claim that with probability at least $\frac{2}{3}$, a Morris counter for
$j$ will be created by the stream as it passes through $T$. Indeed, observe
that since each item of the stream is sampled with probability

$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}\geq\frac{\gamma^{2}\log^{4}(nm)}{2\varepsilon^{2}\left(F_{p}\right)^{1/p}},$

then we have with high probability, an index in $T$ is sampled. By Lemma 2.3,
the index will not be removed by the counters resetting.

Since $T$ is the set of the first $\frac{\varepsilon}{16\log(nm)}$ fraction of
occurrences of $j$, then the Morris counter is used for at least
$\left(1-\frac{\varepsilon}{16\log(nm)}\right)f_{j}$ occurrences of $j$. We
use Morris counters with multiplicative accuracy
$\left(1+\mathcal{O}\left(\frac{\varepsilon}{\log(nm)}\right)\right)$. Hence
by Theorem 1.5, we obtain an output $\widehat{f_{j}}$ such that

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

∎

Finally, for the purposes of completeness, we remark that an item that is not
a heavy-hitter cannot be reported by our algorithm because our algorithm only
counts the number of instances of tracked items and thus it always reports
underestimates of each item. Underestimates of items that are not heavy-
hitters will be far from the threshold for heavy-hitters and thus, those items
will not be reported.

###  2.2 Full Sample and Hold

We now address certain shortcomings of Lemma 2.4 – namely, the assumption that
$F_{p}=\mathcal{O}\left(\frac{n\log^{3}(nm)}{\varepsilon^{4p}}\right)$ and the
fact that Lemma 2.4 only provides constant success probability for each heavy
hitter $j\in[n]$, but there can be many of these heavy-hitters.

Algorithm 2 FullSampleAndHold

1:Stream $s_{1},\ldots,s_{m}$ of items from $[n]$, accuracy parameter
$\varepsilon\in(0,1)$, $p\geq 1$

2:Accurate estimations of $L_{p}$ heavy hitter frequencies

3:$R\leftarrow\mathcal{O}\left(\log n\right)$, $Y=\mathcal{O}\left(\log
m\right)$

4:for $r\in[R],x\in[Y]$ do

5: Let $J^{(r)}_{x}$ be a (nested) subset of $[m]$ subsampled at rate
$p_{x}:=\min(1,2^{1-x})$

6: Let $m^{(r)}_{x}$ be the length of the stream $J^{(r)}_{x}$

7: Run ${\textsc{SampleAndHold}}^{(r)}_{x}$ on $J^{(r)}_{x}$

8:Let $\widehat{f_{j}^{(r,x)}}$ be the estimated frequency for $j$ by
${\textsc{SampleAndHold}}^{(r)}_{x}$

9:$\widehat{f_{j}^{x}}\leftarrow\operatorname*{median}_{r\in[R]}\widehat{f_{j}^{(r,x)}}$

10:Let $\ell=\min\\{x\in[X]\,\mid\,m_{x}\geq(\widehat{f_{j}^{x}})^{p}\\}$

11:return $\widehat{f_{j}^{\ell}}$

We first show subsampling allows us to find a substream that satisfies the
required assumptions. We can then boost the probability of success for
estimating the frequency of each heavy hitter using a standard median-of-means
argument.

######  Lemma 2.5.

Let $j\in[n]$ be an item with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$. Then with probability
$1-\frac{1}{\operatorname*{poly}(n)}$, FullSampleAndHold outputs
$\widehat{f_{j}}$ such that

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

###### Proof.

Consider a fixed $j\in[n]$ with $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$. Let $q>0$ be the integer such that
$\frac{f_{j}}{2^{q}}\in\left[\frac{400}{\varepsilon^{2}},\frac{800}{\varepsilon^{2}}\right]$.
Let $A_{j}$ be the random variable denoting the number of occurrences of $j$
in $J_{q}$ and note that over the randomness of the sampling, we have
$\mathbb{E}\left[A_{j}\right]=\frac{f_{j}}{2^{q}}\leq\frac{400}{\varepsilon^{2}}$.
We also have
$\mathbb{E}\left[A_{j}^{2}\right]\leq\frac{f_{j}}{2^{q}}+\frac{(f_{j})^{2}}{2^{2q}}$,
so that $\mathbb{V}\left[A_{j}\right]\leq\frac{400}{\varepsilon^{2}}$. By
Chebyshev’s inequality, we have that the number of occurrences of $j$ in
$J_{q}^{(r)}$ is a $(1+\varepsilon)$-approximation of $\frac{f_{j}}{2^{q}}$
with probability at least $0.9$. We similarly have that with probability at
least $0.9$,
$m_{x}\in\left[\frac{(1-\varepsilon)m}{2^{q}},\frac{(1+\varepsilon)m}{2^{q}}\right]$
and thus $(A_{j})^{p}\leq\frac{800^{p}}{\varepsilon^{2p}}\cdot m_{q}$.

Since $(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}}{2^{10}\gamma\log^{2}(nm)}$, then by a Chernoff bound, we have that for
any $y\in[n]$, the number of occurrences of $y$ in $J_{q}^{(r)}$ is at most
$\frac{\xi\log^{3}(nm)}{\varepsilon^{4}}$ for some constant $\xi>1$, with high
probability. Thus by a union bound, we have that with high probability,

$F_{p}(J_{q}^{(r)})\leq\frac{\xi^{\prime}n\log^{3p}(nm)}{\varepsilon^{4p}},$

for some sufficiently large constant $\xi^{\prime}>1$, which satisfies the
assumptions of Lemma 2.4. Hence we have with probability at least $0.99$,
$\widehat{f_{j}^{(r,q)}}$ is a $(1+\varepsilon)$-approximation to the number
of occurrences of $j$ in $J_{q}^{(r)}$. Thus,
$\widehat{f_{j}^{(r,q)}}\leq\frac{2\cdot 800^{p}}{\varepsilon^{2p}}\cdot
m_{q}$ with probability at least $0.7$. Observe that since
$(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot F_{p}}{2^{10}\gamma\log^{2}(nm)}$,
then for any $y\in[n]$, we have that the expected number of occurrences of $y$
in $J_{q}^{(r)}$ is at most $\frac{\xi\log^{2}(nm)}{\varepsilon^{4}}$, for
some sufficiently large constant $\xi>1$. Hence by standard Chernoff bounds,
we have that the median satisfies

$\widehat{f_{j}^{(q)}}=\operatorname*{median}_{r\in[R]}\widehat{f_{j}^{(r,q)}}\leq\frac{2\cdot
800^{p}}{\varepsilon^{2p}}\cdot m_{q},$

with high probability.

Moreover, observe that (1) for any stream with subsampling rate
$\frac{1}{2^{x}}>\frac{1}{2^{q}}$, we similarly have that the number of
occurrences of $j$ in $J_{x}$ is a $(1+\varepsilon)$-approximation of
$\frac{f_{j}}{2^{x}}$ with high probability and (2) SampleAndHold cannot
overestimate the frequency of $j$. Thus, $\widehat{f_{j}^{(\ell)}}$ output by
FullSampleAndHold satisfies

$\left(1-\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p}\leq(\widetilde{f_{j}})^{p}\leq\left(1+\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p}$

with high probability. ∎

Putting things together, we obtain Theorem 1.1. See 1.1

###### Proof.

Correctness of the algorithm for the heavy-hitters follows from Lemma 2.5. For
the items that are not heavy-hitters, observe that by a standard concentration
argument, it follows that with high probability across the independent
instances, the median of the number of sampled items after rescaling will not
surpass the threshold.

We next analyze the space complexity. For $p\in[1,2]$, only
$\mathcal{O}\left(\frac{\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$ counters
are stored, while for $p>2$, only
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4+4p}}n^{1-2/p}\right)$
counters are stored. Hence, the space complexity follows.

It remains to analyze the number of internal state changes. The internal state
can change each time an item is sampled. Since each item of the stream is
sampled with probability
$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$, then with
high probability, the total number of internal state changes is
$\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}}$. ∎

##  3 $F_{p}$ Estimation

In this section, we present insertion-only streaming algorithms for $F_{p}$
estimation with a small number of internal state changes. We first observe
that an $F_{p}$ estimation algorithm by [JW19] achieves a small number of
internal state changes for $p<1$. We then build upon our $L_{p}$-heavy hitter
algorithm to achieve an $F_{p}$ estimation algorithm that achieves a small
number of internal state changes for $p>1$.

###  3.1 $F_{p}$ Estimation, $p<1$

As a warm-up, we first show that the $F_{p}$ estimation streaming algorithm of
[JW19] uses a small number of internal state changes for $p<1$. We first
recall the following definition of the $p$-stable distribution:

######  Definition 3.1 ($p$-stable distribution).

[Zol89] For $0<p\leq 2$, the $p$-stable distribution ${\mathcal{D}}_{p}$
exists and satisfies $\sum_{i=1}^{n}Z_{i}x_{i}\sim\|x\|_{p}\cdot Z$ for
$Z,Z_{1},\ldots,Z_{n}\sim{\mathcal{D}}_{p}$ and any vector
$x\in\mathbb{R}^{n}$.

A standard method [Nol03] for generating $p$-stable random variables is to
first generate
$\theta\sim\operatorname*{Uni}\left(\left[-\frac{\pi}{2},\frac{\pi}{2}\right]\right)$
and $r\sim\operatorname*{Uni}([0,1])$ and then set

$X=f(r,\theta)=\frac{\sin(p\theta)}{\cos^{1/p}(\theta)}\cdot\left(\frac{\cos(\theta(1-p))}{\log\frac{1}{r}}\right)^{\frac{1}{p}-1}.$

The $F_{p}$ estimation streaming algorithm of [JW19] first generates a sketch
matrix $D\in\mathbb{R}^{k\times n}$, where
$k=\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\right)$ and each entry of $D$ is
generated from the $p$-stable distribution. Observe that $D$ can be viewed as
$k$ vectors $D^{(1)},\ldots,D^{(k)}\in\mathbb{R}^{n}$ of $p$-stable random
variables. For $i\in[k]$, suppose we maintained $\langle D^{(i)},x\rangle$,
where $x$ is the frequency vector induced by the stream. Then it is known
[Ind06] that with constant probability, the median of these inner products is
a $(1+\varepsilon)$-approximation to $F_{p}$.

[JW19] notes that each vector $D^{(i)}$ can be further decomposed into a
vector $D^{(i,+)}$ containing the positive entries of $D^{(i)}$ and a vector
$D^{(i,-)}$ containing the negative entries of $D^{(i)}$. Since
$D^{(i)}=D^{(i,+)}+D^{(i,-)}$, then it suffices to maintain $\langle
D^{(i,+)},x\rangle$ and $\langle D^{(i,-)},x\rangle$ for each $i\in[k]$. For
insertion-only streams, all entries of $x$ are non-negative, and so the inner
products $\langle D^{(i,+)},x\rangle$ and $\langle D^{(i,-)},x\rangle$ are
both monotonic over the course of the stream, which permits the application of
Morris counters. Thus the algorithm of [JW19] instead uses Morris counters to
approximately compute $\langle D^{(i,+)},x\rangle$ and $\langle
D^{(i,-)},x\rangle$ to within a
$(1+\mathcal{O}\left(\varepsilon\right))$-multiplicative factor. The key
technical point is that [JW19] shows that

$\left\lvert\langle D^{(i,-)},x\rangle\right\rvert+\left\lvert\langle
D^{(i,-)},x\rangle\right\rvert=\mathcal{O}\left(\|x\|_{p}\right)$

for $p<1$ and so $(1+\mathcal{O}\left(\varepsilon\right))$-multiplicative
factor approximations to $\langle D^{(i,+)},x\rangle$ and $\langle
D^{(i,-)},x\rangle$ are enough to achieve a $(1+\varepsilon)$-approximation to
$\langle D^{(i)},x\rangle$. Now the main gain is that using Morris counters to
approximate $\langle D^{(i,+)},x\rangle$ and $\langle D^{(i,-)},x\rangle$, not
only is the overall space usage improved for the purposes of [JW19], but also
for our purposes, the number of internal state updates is much smaller.

As an additional technical caveat, [JW19] notes that the sketching matrix $D$
cannot be stored in the allotted memory. Instead, [JW19] notes that by using
the log-cosine estimator [KNW10] instead of the median estimator, the entries
of $D$ can be generated using
$\mathcal{O}\left(\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\right)$-wise
independence, so that storing the randomness used to generate $D$ only
requires
$\mathcal{O}\left(\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\log
n\right)$ bits of space.

######  Theorem 3.2.

For $p\in(0,1]$, there exists a one-pass insertion-only streaming algorithm
that uses $\operatorname*{poly}\left(\log
n,\frac{1}{\varepsilon},\log\frac{1}{\delta}\right)$ internal state changes,
$\mathcal{O}\left(\frac{1}{\varepsilon^{2}}\left(\log\log
n+\log\frac{1}{\varepsilon}\right)+\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\log
n\right)$ bits of space, and outputs a $(1+\varepsilon)$-approximation to
$F_{p}$ with high probability.

###  3.2 $F_{p}$ Estimation, $p>1$

In this section, we present our $F_{p}$ approximation algorithm for insertion-
only streams that only have $\widetilde{\Omega}_{\varepsilon}(n^{1-1/p})$
internal state updates for $p>1$.

We first define the level sets of the $F_{p}$ moment, as well as the
contribution of each level set.

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

Let $\widetilde{F_{p}}$ be the power of two such that
$F_{p}\leq\widetilde{F_{p}}<2F_{p}$. Given a uniformly random
$\lambda\in\left[\frac{1}{2},1\right]$, for each $\ell\in[L]$, we define the
level set

$\Gamma_{\ell}:=\left\\{i\in[n]\,\mid\,f_{i}\in\left[\frac{\lambda\cdot\widetilde{F_{p}}}{2^{\ell}},\frac{2\lambda\widetilde{F_{p}}}{2^{\ell}}\right)\right\\}.$

We define the contribution $C_{\ell}$ and the fractional contribution
$\phi_{\ell}$ of level set $\Gamma_{\ell}$ to be
$C_{\ell}:=\sum_{i\in\Gamma_{\ell}}(f_{i})^{p}$ and
$\phi_{\ell}:=\frac{C_{\ell}}{F_{p}}$.

For an accuracy parameter $\varepsilon$ and a stream of length $m$, we say
that a level set $\Gamma_{\ell}$ is significant if its fractional contribution
$\phi_{\ell}$ is at least $\frac{\varepsilon}{2p\log(nm)}$. Otherwise, we say
the level set is insignificant.

Our algorithm follows from the framework introduced by [IW05] and subsequently
used in a number of different applications, e.g., [WZ12, BBC+17, LSW18, BWZ21,
WZ21a, MWZ22, BMWZ23] and has the following intuition. We estimate the
contributions of the significant level sets by approximating the frequencies
of the heavy hitters for substreams induced by subsampling the universe at
exponentially smaller rates. Specifically, we create $L=\mathcal{O}\left(\log
n\right)$ substreams where for each $\ell\in[L]$, we subsample each element of
the universe $[n]$ into the substream with probability $\frac{1}{2^{\ell-1}}$.
We rescale $(1+\varepsilon)$-approximations to the contributions of the
surviving heavy hitters by the inverse of the sampling rate to obtain good
approximations of the contributions of each significant level set.

To guarantee a small number of internal state changes, we use our heavy hitter
algorithm FullSampleAndHold to provide $(1+\varepsilon)$-approximations to the
heavy hitters in each substream, thereby obtaining good approximations to the
contributions of each significant level set. Our algorithm appears in full in
Algorithm 3.

Algorithm 3 $F_{p}$ approximation algorithm, $p\geq 1$

1:Stream $s_{1},\ldots,s_{m}$ of items from $[n]$, accuracy parameter
$\varepsilon\in(0,1)$, $p\geq 1$

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

3:$L=\mathcal{O}\left(p\log(nm)\right)$, $R=\mathcal{O}\left(\log\log
n\right)$, $\gamma=2^{20}p$

4:for $t=1$ to $t=m$ do

5: for $(\ell,r)\in[L]\times[R]$ do

6: Let $m_{\ell}^{(r)}$ be a $2$-approximation to the length of the induced
stream $\triangleright$ Morris counter

7: Let $I_{\ell}^{(r)}$ be a (nested) subset of $[n]$ subsampled at rate
$p_{\ell}:=\min(1,2^{1-\ell})$

8: if $s_{t}\in I_{\ell}^{(r)}$ then

9: Send $s_{t}$ to ${\textsc{FullSampleAndHold}}_{\ell}^{(r)}$

10:Let $H_{i}^{(r)}$ be the outputs of the Morris counters at level $i$

11:Let $\widetilde{M}$ be the power of two such that
$m^{p}\leq\widetilde{M}<2m^{p}$

12:Let $S_{i}^{(r)}$ be the set of ordered pairs $(j,\widehat{f_{j}})$ of
$H_{i}^{(r)}$ with
$\left(\widehat{f_{j}}\right)^{p}\in\left[\frac{\lambda\cdot\widetilde{M}}{2^{i}},\frac{2\lambda\cdot\widetilde{M}}{2^{i}}\right]$

13:for $i=1$ to $i=L$ do

14:
$\ell\leftarrow\max\left(1,i-{\left\lfloor\log\frac{\gamma^{2}\log(nm)}{\varepsilon^{2}}\right\rfloor}\right)$

15:
$\widehat{C_{i}}\leftarrow\frac{1}{p_{\ell}}\operatorname*{median}_{r\in[R]}\left(\sum_{(j,\widehat{f_{j}})\in
S_{\ell}^{(r)}}\left(\widehat{f_{j}}\right)^{p}\right)$

16:return $\widehat{F_{p}}=\sum_{\ell\in[L]}\widehat{C_{\ell}}$

We note the following corollary of Lemma 2.5.

######  Lemma 3.4.

Let $r\in[R]$ be fixed. Suppose $j\in I_{\ell}^{(r)}$ and
$(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot
F_{p}(I_{\ell}^{(r)})}{2^{7}\gamma\log^{2}(nm)}$. Then with probability at
least $\frac{9}{10}$, $H_{\ell}^{(r)}$ outputs $\widehat{f_{j}}$ with

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

###### Proof.

The proof follows from Lemma 2.5 and the fact that FullSampleAndHold is only
run on the substream induced by $I_{\ell}^{(r)}$. ∎

######  Lemma 3.5.

Let $\varepsilon\in(0,1)$, $\Gamma_{i}$ be a fixed level set and let
$\ell:=\max\left(1,i-{\left\lfloor\log\frac{\gamma\log(nm)}{\varepsilon^{2}}\right\rfloor}\right)$.
For a fixed $r\in[R]$, let ${\mathcal{E}}_{1}$ be the event that
$|I_{\ell}^{(r)}|\leq\frac{32n}{2^{\ell}}$ and let ${\mathcal{E}}_{2}$ be the
event that $F_{p}(I_{\ell}^{(r)})\leq\frac{32F_{p}}{2^{\ell}}$. Then
conditioned on ${\mathcal{E}}_{1}$ and ${\mathcal{E}}_{2}$, for each
$j\in\Gamma_{i}\cap I_{\ell}^{(r)}$, there exists $(j,\widetilde{f_{j}})$ in
$S_{i}^{(r)}$ such that with probability at least $\frac{9}{10}$,

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

###### Proof.

We consider casework on whether
$i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}\leq
1$ or
$i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}>1$.
This corresponds to whether the frequencies $\left(\widehat{f_{j}}\right)^{p}$
in a significant level set are large or not large, informally speaking. If the
frequencies are large, then it suffices to estimate them using our sampling-
based algorithm. However, if the frequencies are not large, then subsampling
must first be performed before we can estimate the frequencies using our
sampling-based algorithm.

Suppose
$i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}\leq
1$, so that $\frac{1}{2^{i}}\geq\frac{\varepsilon^{2}}{\gamma\log^{2}(nm)}$.
Since $j\in\Gamma_{i}$, we have
$(f_{j})^{p}\in\left[\frac{\lambda\cdot\widetilde{F_{p}}}{2^{i}},\frac{2\lambda\widetilde{F_{p}}}{2^{i}}\right]$
and thus

$(f_{j})^{p}\geq\frac{\varepsilon^{2}\cdot\widetilde{F_{p}}}{\gamma\log^{2}(nm)},\qquad
f_{j}\geq\frac{\varepsilon^{2/p}\cdot\left(\widetilde{F_{p}}\right)^{2/p}}{\gamma^{1/p}\log^{1/p}(nm)}$

Moreover, for
$\ell=\max\left(1,i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}\right)$,
we have $\ell=1$, so we consider the outputs by the Morris counters
$H_{1}^{(r)}$. By Lemma 3.4, we have that with probability at least
$\frac{9}{10}$, $H_{\ell}^{(r)}$ outputs $\widehat{f_{j}}$ such that

$\left(1-\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p}\leq(\widetilde{f_{j}})^{p}\leq\left(1+\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p},$

as desired.

For the other case, suppose
$i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}>1$,
so that
$\ell=i-{\left\lfloor\log\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\right\rfloor}$
and $p_{\ell}=2^{1-\ell}$. Therefore,

$\frac{1}{2^{\ell}}=\frac{\gamma\log^{2}(nm)}{\varepsilon^{2}}\frac{1}{2^{i}}.$

Since $j\in\Gamma_{i}$, we have again
$(f_{j})^{p}\in\left[\frac{\lambda\cdot\widetilde{F_{p}}}{2^{i}},\frac{2\lambda\widetilde{F_{p}}}{2^{i}}\right]$
and therefore,

$(f_{j})^{p}\geq\frac{F_{p}}{4\cdot
2^{i}}\geq\frac{\varepsilon^{2}}{4\gamma\log^{2}(nm)}\frac{F_{p}}{2^{\ell}}.$

Conditioning on the event ${\mathcal{E}}_{2}$, we have
$F_{p}(I_{\ell}^{(r)})\leq\frac{32F_{p}}{2^{\ell}}$ and thus

$(f_{j})^{p}\geq\frac{F_{p}}{4\cdot
2^{i}}\geq\frac{\varepsilon^{2}}{128\gamma\log^{2}n}\cdot
F_{p}(I_{\ell}^{(r)}).$

Therefore by Lemma 3.4, we have that with probability at least $\frac{9}{10}$,
$H_{\ell}^{(r)}$ outputs $\widehat{f_{j}}$ such that

$\left(1-\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p}\leq(\widetilde{f_{j}})^{p}\leq\left(1+\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p},$

as desired. ∎

We now justify the approximation guarantees of our algorithm.

######  Lemma 3.6.

$\mathbf{Pr}\left[\left\lvert\widehat{F_{p}}-F_{p}\right\rvert\leq\varepsilon\cdot
F_{p}\right]\geq\frac{2}{3}$.

###### Proof.

We would like to show that for each level set $i$, we accurately estimate its
contribution $C_{i}$, i.e., we would like to show
$|\widehat{C_{i}}-C_{i}\rvert\leq\frac{\varepsilon}{8\log(nm)}\cdot F_{p}$ for
all $i$. For a fixed $i$, recall that $C_{i}=\sum_{j\in\Gamma i}(f_{j})^{p}$,
where $j\in\Gamma_{i}$ if
$(f_{j})^{p}\in\left[\frac{\lambda\cdot\widetilde{F_{p}}}{2^{i}},\frac{2\lambda\widetilde{F_{p}}}{2^{i}}\right)$.
On the other hand, $\widehat{C_{i}}$ is a scaled sum of items $j$ whose
estimated frequency satisfies
$\left(\widehat{f_{j}}\right)^{p}\in\left[\frac{\lambda\cdot\widetilde{M}}{2^{i}},\frac{2\lambda\cdot\widetilde{M}}{2^{i}}\right]$.
Then $j$ could be classified into contributing to $\widehat{C_{i}}$ even if
$j\notin\Gamma_{i}$. Thus we first consider an idealized process where $j$ is
correctly classified across all level sets and show that in this idealized
process, we achieve a $(1+\mathcal{O}\left(\varepsilon\right))$-approximation
to $F_{p}$. We then argue that because we choose $\lambda$ uniformly at
random, then only a small number of coordinates will be misclassified and so
our approximation guarantee will only slightly degrade, but remain a
$(1+\varepsilon)$-approximation to $F_{p}$.

Idealized process. We first show that in a setting where
$(\widehat{f_{j}})^{p}$ is correctly classified for all $j$, then for a fixed
level set $i$, we have
$|\widehat{C_{i}}-C_{i}\rvert\leq\frac{\varepsilon}{8\log(nm)}\cdot F_{p}$
with probability $1-\frac{1}{\operatorname*{poly}(nm)}$.

For a fixed $r\in[R]$, let ${\mathcal{E}}_{1}$ be the event that
$|I_{i}^{(r)}|\leq\frac{32n}{2^{i}}$ and let ${\mathcal{E}}_{2}$ be the event
that $F_{p}(I_{i}^{(r)})\leq\frac{32F_{p}}{2^{i}}$. Let ${\mathcal{E}}_{3}$ be
the event that

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

Conditioned on ${\mathcal{E}}_{1}$, ${\mathcal{E}}_{2}$, and $j\in
I_{i}^{(r)}$, then we have that
$\mathbf{Pr}\left[{\mathcal{E}}_{3}\right]\geq\frac{9}{10}$, by Lemma 3.5.

We define
$\widehat{C_{i}^{(r)}}:=\frac{1}{p_{\ell}}\sum_{(j,\widehat{f_{j}})}\in
S_{i}^{(r)}\left(\widehat{f_{j}}\right)^{p}$. Therefore, we have that
$\widehat{C_{i}}=\operatorname*{median}_{r\in[R]}\widehat{C_{i}^{(r)}}$,
recalling
$\ell=\max\left(1,i-{\left\lfloor\log\frac{\gamma\log(nm)}{\varepsilon^{2}}\right\rfloor}\right)$.

Conditioned on ${\mathcal{E}}_{3}$, we have

$\left(1-\frac{\varepsilon}{8\log(nm)}\right)D_{i}^{(r)}\leq\widehat{C_{i}^{(r)}}\leq\left(1+\frac{\varepsilon}{8\log(nm)}\right)D_{i}^{(r)},$

where we define

$D_{i}^{(r)}=\frac{1}{p_{\ell}}\sum_{j\in
S_{i}^{(r)}\cap\Gamma_{i}}(f_{j})^{p}.$

Note that

$\mathbb{E}\left[D_{i}^{(r)}\right]=\frac{1}{p_{\ell}}\sum_{j\in\Gamma_{i}}p_{\ell}\cdot(f_{j})^{p}=C_{i},$

where we recall that $C_{i}$ denotes the contribution of level set
$\Gamma_{i}$. We also have

$\mathbb{V}\left[D_{i}^{(r)}\right]\leq\frac{1}{(p_{\ell})^{2}}\sum_{j\in\Gamma_{i}}p_{\ell}\cdot(f_{j})^{2p}\leq\frac{\varepsilon^{2}}{2^{i-1}\cdot(\gamma^{2}\log(nm))}\sum_{j\in
C_{i}}(f_{j})^{2p}.$

For $j\in\Gamma_{i}$, we have
$(f_{j})^{2p}\leq\frac{4\lambda^{2}(\widetilde{F_{p}})^{2}}{2^{2i}}\leq\frac{16(F_{p})^{2}}{2^{2i}}$,
since $\lambda\leq 1$ and $\widetilde{F_{p}}\leq 2F_{p}$. Therefore for
sufficiently large $\gamma$,

$\mathbb{V}\left[D_{i}^{(r)}\right]\leq\frac{\varepsilon^{2}|\Gamma_{i}|}{100p^{2}\cdot
2^{i}\cdot\log^{2}(nm)}(F_{p})^{2}.$

Since $\frac{|\Gamma_{i}|}{2^{i}}\leq\phi_{i}\leq 1$, then

$\mathbb{V}\left[D_{i}^{(r)}\right]\leq\frac{\varepsilon^{2}}{10000p\log(nm)}\cdot(F_{p})^{2}.$

Thus by Chebyshev’s inequality, we have

$\mathbf{Pr}\left[\left\lvert
D_{i}^{(r)}-C_{i}\right\rvert\geq\frac{\varepsilon}{10p\log(nm)}\cdot
F_{p}\right]\leq\frac{1}{10}.$

Therefore,

$\mathbf{Pr}\left[\left\lvert\widehat{C_{i}^{(r)}}-C_{i}\right\rvert\leq\frac{\varepsilon}{10p\log(nm)}\cdot
F_{p}\,\mid\,{\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}\right]\geq\frac{4}{5}.$

To analyze the probability of the events ${\mathcal{E}}_{1}$ and
${\mathcal{E}}_{2}$ occurring, note that in level $\ell$, each item is sampled
with probability $2^{-\ell+1}$. Hence,

$\mathbb{E}\left[|I_{\ell}^{(r)}|\right]\leq\frac{n}{2^{\ell-1}},\qquad\mathbb{E}\left[F_{p}(I_{\ell}^{(r)})\right]\leq\frac{F_{p}}{2^{\ell-1}}.$

Since ${\mathcal{E}}_{1}$ is the event that
$|I_{\ell}^{(r)}|\leq\frac{32n}{2^{\ell}}$ and ${\mathcal{E}}_{2}$ is the
event that $F_{p}(I_{\ell}^{(r)})\leq\frac{32F_{p}}{2^{\ell}}$, then by
Markov’s inequality, we have

$\mathbf{Pr}\left[E_{1}\right]\geq\frac{15}{16},\qquad\mathbf{Pr}\left[E_{2}\right]\geq\frac{15}{16}.$

By a union bound,

$\mathbf{Pr}\left[\left\lvert\widehat{C_{i}^{(r)}}-C_{i}\right\rvert\leq\frac{\varepsilon}{10p\log(nm)}\cdot
F_{p}\right]\geq 0.676.$

Since $\widehat{C_{i}}=\operatorname*{median}_{r\in[R]}\widehat{C_{i}^{(r)}}$
over $R=\mathcal{O}\left(\log\log n\right)$ independent instances, then we
have

$\mathbf{Pr}\left[\left\lvert\widehat{C_{i}}-C_{i}\right\rvert\leq\frac{\varepsilon}{10p\log(nm)}\cdot
F_{p}\right]\geq 1-\frac{1}{\operatorname*{polylog}(n)}.$

Hence by a union bound over the $p\log(nm)$ level sets,

$\displaystyle\left\lvert\widehat{F_{p}}-F_{p}\right\rvert$
$\displaystyle=\left\lvert\sum_{i=1}^{p\log(nm)}\widehat{C_{i}}-\sum_{i=1}^{p\log(nm)}C_{i}|\right\rvert\leq\sum_{i=1}^{p\log(nm)}\left\lvert\widehat{C_{i}}-C_{i}|\right\rvert$
$\displaystyle\leq\sum_{i=1}^{p\log(nm)}\frac{\varepsilon}{10p\log(nm)}\cdot
F_{p}\leq\frac{\varepsilon}{10}\cdot F_{p}.$

Randomized boundaries. Given a fixed $r\in[R]$, we say that an item $j\in[n]$
is misclassified if there exists a level set $\Gamma_{i}$ such that

$(f_{j})^{p}\in\left[\frac{\lambda\cdot\widetilde{F_{p}}}{2^{i}},\frac{2\lambda\cdot\widetilde{F_{p}}}{2^{i}}\right],$

but for the estimate $\widetilde{f_{j}}$, we have either

$(\widetilde{f_{j}})^{p}<\frac{\lambda\cdot\widetilde{F_{p}}}{2^{i}}\qquad\text{or}\qquad(\widetilde{f_{j}})^{p}\geq\frac{2\lambda\cdot\widetilde{F_{p}}}{2^{i}}.$

By Lemma 3.4, we have that conditioned on ${\mathcal{E}}_{3}$,

$\left(1-\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p}\leq(\widetilde{f_{j}})^{p}\leq\left(1+\frac{\varepsilon}{8\log(nm)}\right)\cdot(f_{j})^{p},$

independently of the choice of $\lambda$. Since
$\lambda\in\left[\frac{1}{2},1\right]$ is chosen uniformly at random, then the
probability that $j\in[n]$ is misclassified is at most
$\frac{\varepsilon}{2\log(nm)}$.

Furthermore, if $j\in[n]$ is misclassified, then it can only be classified
into either level set $\Gamma_{i+1}$ or level set $\Gamma_{i-1}$, because
$\left(\widehat{f_{j}}^{p}\right)$ is a
$\left(1+\frac{\varepsilon}{8\log(nm)}\right)$-approximation to $(f_{j})^{p}$.
Thus, a misclassified index induces at most $2(f_{j})^{p}$ additive error to
the contribution of level set $\Gamma_{i}$. In expectation across all
$j\in[n]$, the total additive error due to misclassification is at most
$F_{p}\cdot\frac{\varepsilon}{2\log(nm)}$. Therefore by Markov’s inequality
for sufficiently large $n$ and $m$, the total additive error due to
misclassification is at most $\frac{\varepsilon}{2}\cdot F_{p}$ with
probability at least $0.999$. Hence in total,

$\mathbf{Pr}\left[\left\lvert\widehat{F_{p}}-F_{p}\right\rvert\leq\varepsilon\cdot
F_{p}\right]\geq\frac{2}{3}.$

∎

Putting things together, we give the full guarantees of our $F_{p}$ estimation
algorithm in Theorem 1.3.

See 1.3

###### Proof.

The space bound follows from the fact that for $p\in[1,2]$, only
$\mathcal{O}\left(\frac{\log^{11+3p}(mn)}{\varepsilon^{4+4p}}\right)$ counters
are stored, while for $p>2$, only
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{4+4p}}n^{1-2/p}\right)$
counters are stored. The internal state can change each time an item is
sampled. Since each item of the stream is sampled with probability
$\varrho=\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}m}$, then with
high probability, the total number of internal state changes is
$\frac{\gamma^{2}n^{1-1/p}\log^{4}(nm)}{\varepsilon^{2}}$.

Finally for correctness, we have by Lemma 3.6, that

$\mathbf{Pr}\left[\left\lvert\widehat{F_{p}}-F_{p}\right\rvert\leq\varepsilon\cdot
F_{p}\right]\geq\frac{2}{3}.$

∎

###  3.3 Entropy Estimation

In this section, we describe how to estimate the entropy of a stream using a
small number of internal state changes. Recall that for a frequency vector
$f\in\mathbb{R}^{n}$, the Shannon entropy of $f$ is defined by
$H(f)=-\sum_{i=1}^{n}f_{i}\log f_{i}$. Observe that any algorithm that obtains
a $(1+\mathcal{O}\left(\varepsilon\right))$-multiplicative approximation to
the function $h(f)=2^{H(f)}$ also obtains an
$\mathcal{O}\left(\varepsilon\right)$-additive approximation of the Shannon
entropy $H(f)$, and vice versa. Hence to obtain an additive
$\varepsilon$-approximation to the Shannon entropy, we describe how to obtain
a multiplicative $(1+\varepsilon)$-approximation to $h(f)=2^{H(f)}$.

######  Lemma 3.7 ([HNO08]).

Given an accuracy parameter $\varepsilon>0$, let
$k=\log\frac{1}{\varepsilon}+\log\log m$ and
$\varepsilon^{\prime}=\frac{\varepsilon}{12(k+1)^{3}\log m}$. Then there
exists an efficiently computable set $\\{p_{0},\ldots,p_{k}\\}$ such that
$p_{i}\in(0,2)$ for all $i$, as well as an efficiently computable
deterministic function that uses $(1+\varepsilon^{\prime})$-approximations to
$F_{p_{i}}(f)$ to compute a $(1+\varepsilon)$-approximation to
$h(f)=2^{H(f)}$.

Section 3.3 in [HNO08] describes how to compute the set
$\\{p_{0},\ldots,p_{k}\\}$ in Lemma 3.7 as follows. We define
$\ell=\frac{1}{2(k+1)\log m}$ and the function
$g(z)=\frac{\ell(k^{2}(z-1)+1))}{2k^{2}+1}$. For each $p_{i}$, we set
$p_{i}=1+g(\cos(i\pi/k))$, which can be efficiently computed. Thus, the set
$\\{p_{0},\ldots,p_{k}\\}$ in Lemma 3.7 can be efficiently computed as pre-
processing, assuming that $n$ and $m$ are known a priori. Let $P(x)$ be the
degree $k$ polynomial interpolated at the points $p_{0},\ldots,p_{k}$, so that
$P(p_{i})=F_{p_{i}}(f)$ for each $i\in[k]$, where $F_{p_{i}}(f)$ is the
$(p_{i})$-th moment of the frequency vector $f$. [HNO08] then showed that a
multiplicative $(1+\mathcal{O}\left(\varepsilon\right))$-approximation to
$h(f)=2^{H(f)}$ can then be computed from $2^{P(0)}$, and moreover a
$(1+\mathcal{O}\left(\varepsilon\right))$-approximation to $2^{P(0)}$ can be
computed from $(1+\mathcal{O}\left(\varepsilon\right))$-approximations to
$F_{p_{i}}(f)$, for each $i\in[k]$.

Thus by Lemma 3.7 and Theorem 1.3, we have:

######  Theorem 3.8.

Given an accuracy parameter $\varepsilon\in(0,1)$, as well as the universe
size $n$, and the stream length $m=\operatorname*{poly}(n)$, there exists a
one-pass insertion-only streaming algorithm that has
$\tilde{\mathcal{O}}\left(\frac{1}{\varepsilon^{\mathcal{O}\left(1\right)}}\sqrt{n}\right)$
internal state changes, uses
$\mathcal{O}\left(\frac{\log^{\mathcal{O}\left(1\right)}(mn)}{\varepsilon^{\mathcal{O}\left(1\right)}}\right)$
bits of space, and outputs $\widehat{H}$ such that
$\mathbf{Pr}\left[\left\lvert\widehat{H}-H\right\rvert\leq\varepsilon\right]\geq\frac{2}{3}$,
where $H$ is the Shannon entropy of the stream.

##  4 Lower Bound

In this section, we describe our lower bound showing that any streaming
algorithm achieving a $(2-\Omega(1))$-approximation to $F_{p}$ requires at
least $\frac{1}{2}n^{1-1/p}$ state updates, regardless of the memory allocated
to the algorithm. The proof of Theorem 1.2 is similar. The main idea is that
we create two streams ${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$ of length
$\mathcal{O}\left(n\right)$ that look similar everywhere except for a random
contiguous block $B$ of $n^{1/p}$. In $B$, the first stream
${\mathcal{S}}_{1}$ has the same item repeated $n^{1/p}$ times, while the
second stream ${\mathcal{S}}_{2}$ has $n^{1/p}$ distinct items each appear
once. The remaining $n-n^{1/p}$ stream updates of ${\mathcal{S}}_{1}$ and
${\mathcal{S}}_{2}$ are additional distinct items that each appear once, so
that $F_{p}({\mathcal{S}}_{1})\geq(2-o(1))\cdot F_{p}({\mathcal{S}}_{2})$ and
$F_{p}({\mathcal{S}}_{2})=\Omega(n)$. Any algorithm ${\mathcal{A}}$ that
achieves a $(2-\Omega(1))$-approximation to $F_{p}$ must distinguish between
${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$ and thus ${\mathcal{A}}$ must
perform some action on $B$. However, $B$ has size $n^{1/p}$ and has random
location throughout the stream, so ${\mathcal{A}}$ must perform
$\Omega(n^{1-1/p})$ state updates. See 1.4

###### Proof.

Consider the two following possible input streams. For the stream
${\mathcal{S}}_{1}$ of length $n$ on universe $n$, we choose a random
contiguous block $B$ of $n^{1/p}$ stream updates and set them all equal to the
same random universe item $i\in[n]$. We randomly choose the remaining
$n-n^{1/p}$ updates in the stream so that they are all distinct and none of
them are equal to $i$. Note that by construction, we have
$F_{p}({\mathcal{S}}_{1})=(n-n^{1/p})+(n^{1/p})^{p}=2n-n^{1/p}$. For the
stream ${\mathcal{S}}_{2}$ of length $n$ on universe $n$, we choose
${\mathcal{S}}_{2}$ to be a random permutation of $[n]$, so that
$F_{p}({\mathcal{S}}_{2})=n$.

For fixed $\varepsilon\in(0,1)$, let ${\mathcal{A}}$ be an algorithm that
achieves a $2-\varepsilon$ approximation to $F_{p}$ with probability at least
$\frac{2}{3}$, while using fewer than $\frac{1}{2}n^{1-1/p}$ state updates. We
claim that with probability $\frac{1}{2}$, ${\mathcal{A}}$ must have the same
internal state before and after $B$ in the stream ${\mathcal{S}}_{1}$. Note
that we can view each stream update as $(i,j)$ where $i\in[n]$ is the index of
the stream update and $j\in[n]$ is the identity of the universe item. Observe
that for a random stream update $i\in[n]$, a random universe update $j\in[n]$
alters the state of ${\mathcal{A}}$ with probability at most
$\frac{1}{2n^{1/p}}$, since otherwise for a random stream, the expected number
of state changes would be larger than $\frac{n^{1-1/p}}{2}$, which would be a
contradiction. Since both the choice of $B$ and the element $j\in[n]$ that is
repeated $n^{1/p}$ times are chosen uniformly at random, then the expected
number of changes of the streaming algorithm on the block $B$ is at most
$\frac{n^{1/p}}{2n^{1/p}}=\frac{1}{2}$. Therefore, with probability at least
$\frac{1}{2}$, the streaming algorithm’s state is the same before and after
the block $B$.

Moreover, the same argument applies to ${\mathcal{S}}_{2}$, and so therefore
with probability at least $\frac{1}{2}$, the streaming algorithm cannot
distinguish between ${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$ if its
internal state only changes fewer than $\frac{n^{1-1/p}}{2}$ times. ∎

We now prove Theorem 1.2 using a similar approach. See 1.2

###### Proof.

Consider the two input streams ${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$
defined as follows. We define the stream ${\mathcal{S}}_{1}$ to have length
$n$ on a universe of size $n$. Similar to before, we choose a random
contiguous block $B$ of $\varepsilon\cdot n^{1/p}$ stream updates and set them
all equal to the same random universe item $i\in[n]$. We randomly choose the
remaining $n-n^{1/p}$ updates in the stream so that they are all distinct and
none of them are equal to $i$. Note that by construction, we have

$F_{p}({\mathcal{S}}_{1})=(n-n^{1/p})+(n^{1/p})^{p}=2n-n^{1/p}.$

Therefore, the item replicated $\varepsilon\cdot n^{1/p}$ times in block $B$
is an $\frac{\varepsilon}{2}$-heavy hitter with respect to $L_{p}$.

We also define the stream ${\mathcal{S}}_{2}$ to have length $n$ on universe
$n$. As before, we choose ${\mathcal{S}}_{2}$ to be a random permutation of
$[n]$, so that $F_{p}({\mathcal{S}}_{2})=n$.

For fixed $\varepsilon\in(0,1)$, let ${\mathcal{A}}$ be an algorithm that
solves the $\varepsilon$-heavy hitter problem with respect to $L_{p}$, with
probability at least $\frac{2}{3}$, while using fewer than
$\frac{1}{2\varepsilon}n^{1-1/p}$ state updates. We claim that with
probability $\frac{1}{2}$, ${\mathcal{A}}$ must have the same internal state
before and after $B$ in the stream ${\mathcal{S}}_{1}$.

Observe that each stream update can be viewed as $(i,j)$ where $i\in[n]$ is
the index of the stream update and $j\in[n]$ is the identity of the universe
item. For a random universe item $i\in[n]$, the probability that a random
stream update $j\in[n]$ alters the state of ${\mathcal{A}}$ is at most
$\frac{1}{2\varepsilon\cdot n^{1/p}}$, since otherwise for a random stream,
the expected number of state changes would be larger than
$\frac{n^{1-1/p}}{2\varepsilon}$, which would be a contradiction. Because both
the choice of $B$ is uniformly and the element $j\in[n]$ that is repeated
$\varepsilon\cdot n^{1/p}$ times are chosen uniformly at random, then the
expected number of changes of the streaming algorithm on the block $B$ is at
most $\frac{\varepsilon\cdot n^{1/p}}{2\varepsilon\cdot n^{1/p}}=\frac{1}{2}$.
Hence, the streaming algorithm’s state is the same before and after the block
$B$, with probability at least $\frac{1}{2}$.

However, the same argument applies to ${\mathcal{S}}_{2}$. Thus with
probability at least $\frac{1}{2}$, the streaming algorithm cannot distinguish
between ${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$ if its internal state only
changes fewer than $\frac{n^{1-1/p}}{2\varepsilon}$ times. Therefore, any
algorithm that solves the $L_{p}$-heavy hitter problem with threshold
$\varepsilon$ with probability at least $\frac{2}{3}$ requires at least
$\frac{1}{2\varepsilon}n^{1-1/p}$ state updates. ∎

## Acknowledgements

We would like to thank Mark Braverman for asking questions related to the ones
we studied in this work. David P. Woodruff would like to thank Google Research
and the Simons Institute for the Theory of Computing, where part of this work
was done, as well as a Simons Investigator Award. David P. Woodruff and Samson
Zhou are supported in part by NSF CCF-2335411. Part of this work was done
while Samson Zhou was a postdoctoral researcher at UC Berkeley.

## References

  * [ABCR12] Manos Athanassoulis, Bishwaranjan Bhattacharjee, Mustafa Canim, and Kenneth A. Ross.  Path processing using solid state storage.  In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS, pages 23–32, 2012.
  * [ABJ+22] Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou.  The white-box adversarial data stream model.  In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 15–27, 2022.
  * [ACM+11] Ameen Akel, Adrian M. Caulfield, Todor I. Mollov, Rajesh K. Gupta, and Steven Swanson.  Onyx: A prototype phase change memory storage array.  In 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage1, 2011.
  * [AG09] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP Proceedings, Part II, pages 328–338, 2009.
  * [AGMS02] Noga Alon, Phillip B. Gibbons, Yossi Matias, and Mario Szegedy.  Tracking join and self-join sizes in limited storage.  J. Comput. Syst. Sci., 64(3):719–747, 2002.
  * [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.
  * [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.
  * [App23] Apple, 2023.
  * [BBC+17] Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang.  Streaming symmetric norms via measure concentration.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 716–729, 2017.
  * [BBD+02] Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom.  Models and issues in data stream systems.  In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 1–16, 2002.
  * [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.
  * [BCIW16] Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff.  Beating countsketch for heavy hitters in insertion streams.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 740–753, 2016.
  * [BDM+20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou.  Near optimal linear algebra in the online and sliding window models.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 517–528, 2020.
  * [BDN17] Jaroslaw Blasiok, Jian Ding, and Jelani Nelson.  Continuous monitoring of l_p norms in data streams.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 32:1–32:13, 2017.
  * [BEFK17] Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner.  Optimal elephant flow detection.  In 2017 IEEE Conference on Computer Communications, INFOCOM, pages 1–9, 2017.
  * [BFG+15] Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun.  Sorting with asymmetric read and write costs.  In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 1–12, 2015.
  * [BFL+21] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou.  Efficient coreset constructions via sensitivity sampling.  In Asian Conference on Machine Learning, ACML, pages 948–963, 2021.
  * [BFL+23] Vladimir Braverman, Dan Feldman, Harry Lang, Daniela Rus, and Adiel Statman.  Least-mean-squares coresets for infinite streams.  IEEE Trans. Knowl. Data Eng., 35(9):8699–8712, 2023.
  * [BFLR19] Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus.  Streaming coreset constructions for m-estimators.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 62:1–62:15, 2019.
  * [BGL+18] Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou.  Nearly optimal distinct elements and heavy hitters on sliding windows.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 7:1–7:22, 2018.
  * [BHK+91] Mary Baker, John H. Hartman, Michael D. Kupfer, Ken Shirriff, and John K. Ousterhout.  Measurements of a distributed file system.  In Proceedings of the Thirteenth ACM Symposium on Operating System Principles, SOSP, pages 198–212, 1991.
  * [BHM+21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou.  Adversarial robustness of streaming algorithms through importance sampling.  In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPSl, pages 3544–3557, 2021.
  * [BIPW10] Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff.  Lower bounds for sparse recovery.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1190–1197, 2010.
  * [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.
  * [BJWY22] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev.  A framework for adversarially robust streaming algorithms.  J. ACM, 69(2):17:1–17:33, 2022.
  * [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.
  * [BLMZ23] Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou.  Differentially private $l_{2}$-heavy hitters model.  In The Eleventh International Conference on Learning Representations, ICLR, 2023.
  * [BM91] Robert S. Boyer and J. Strother Moore.  MJRTY: A fast majority vote algorithm.  In Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, pages 105–118, 1991.
  * [BMWZ23] Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou.  Private data stream analysis for universal symmetric norm estimation.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 45:1–45:24, 2023.
  * [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 2013, and 17th International Workshop, RANDOM. Proceedings, pages 42–57, 2013.
  * [BT11] Avraham Ben-Aroya and Sivan Toledo.  Competitive analysis of flash memory algorithms.  ACM Trans. Algorithms, 7(2):23:1–23:37, 2011.
  * [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.
  * [BWZ21] Vladimir Braverman, Viska Wei, and Samson Zhou.  Symmetric norm estimation and regression on sliding windows.  In Computing and Combinatorics - 27th International Conference, COCOON, Proceedings, pages 528–539, 2021.
  * [CAWZ23] Vincent Cohen-Addad, David P. Woodruff, and Samson Zhou.  Streaming euclidean $k$-median and $k$-means with $o(\log n)$ space.  In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2023.
  * [CCF04] Moses Charikar, Kevin C. Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  Theor. Comput. Sci., 312(1):3–15, 2004.
  * [CGN11] Shimin Chen, Phillip B. Gibbons, and Suman Nath.  Rethinking database algorithms for phase change memory.  In Fifth Biennial Conference on Innovative Data Systems Research, CIDR, pages 21–31, 2011.
  * [Cha07] Li-Pin Chang.  On efficient wear leveling for large-scale flash-memory storage systems.  In Proceedings of the 2007 ACM Symposium on Applied Computing (SAC), pages 1126–1130, 2007.
  * [CHK07] Yuan-Hao Chang, Jen-Wei Hsieh, and Tei-Wei Kuo.  Endurance enhancement of flash-memory storage, systems: An efficient static wear leveling design.  In Proceedings of the 44th Design Automation Conference, DAC, pages 212–217, 2007.
  * [CIKM02] Graham Cormode, Piotr Indyk, Nick Koudas, and S. Muthukrishnan.  Fast mining of massive tabular data via approximate distance computations.  In Proceedings of the 18th International Conference on Data Engineering, pages 605–614, 2002.
  * [CL09] Sangyeun Cho and Hyunjin Lee.  Flip-n-write: a simple deterministic technique to improve PRAM write performance, energy and endurance.  In 42st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-42), pages 347–357, 2009.
  * [CM05] Graham Cormode and S. Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  J. Algorithms, 55(1):58–75, 2005.
  * [CMP20] Michael B. Cohen, Cameron Musco, and Jakub Pachocki.  Online row sampling.  Theory Comput., 16:1–25, 2020.
  * [CYW+12] Tseng-Yi Chen, Tsung Tai Yeh, Hsin-Wen Wei, Yu-Xun Fang, Wei-Kuan Shih, and Tsan-sheng Hsu.  Cacheraid: An efficient adaptive write cache policy to conserve RAID disk array energy.  In IEEE Fifth International Conference on Utility and Cloud Computing, UCC, pages 117–124, 2012.
  * [DJX09] Xiangyu Dong, Norman P. Jouppi, and Yuan Xie.  Pcramsim: System-level performance, energy, and area modeling for phase-change RAM.  In 2009 International Conference on Computer-Aided Design, ICCAD, pages 269–275, 2009.
  * [DWS+08] Xiangyu Dong, Xiaoxia Wu, Guangyu Sun, Yuan Xie, Hai Li, and Yiran Chen.  Circuit and microarchitecture evaluation of 3d stacking magnetic RAM (MRAM) as a universal memory replacement.  In Proceedings of the 45th Design Automation Conference, DAC, pages 554–559, 2008.
  * [EGMP14] David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Pawel Pszona.  Wear minimization for cuckoo hashing: How not to throw a lot of eggs into one basket.  In Experimental Algorithms - 13th International Symposium, SEA. Proceedings, pages 162–173, 2014.
  * [EV02] Cristian Estan and George Varghese.  New directions in traffic measurement and accounting.  In Proceedings of the ACM SIGCOMM 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 323–336, 2002.
  * [FKSV02] Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan.  An approximate l1-difference algorithm for massive data streams.  SIAM J. Comput., 32(1):131–151, 2002.
  * [FSG+98] Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman.  Computing iceberg queries efficiently.  In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, pages 299–310, 1998.
  * [GLPW16] Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff.  Frequent directions: Simple and deterministic matrix sketching.  SIAM J. Comput., 45(5):1762–1792, 2016.
  * [Gro09] André Gronemeier.  Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness.  In 26th International Symposium on Theoretical Aspects of Computer Science, STACS Proceedings, pages 505–516, 2009.
  * [GW18] Sumit Ganguly and David P. Woodruff.  High probability frequency moment sketches.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pages 58:1–58:15, 2018.
  * [HNO08] Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak.  Sketching and streaming entropy via approximation theory.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 489–498, 2008.
  * [Ind04] Piotr Indyk.  Algorithms for dynamic geometric problems over data streams.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 373–380, 2004.
  * [Ind06] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  J. ACM, 53(3):307–323, 2006.
  * [Ind13] Piotr Indyk.  Sketching via hashing: from heavy hitters to compressed sensing to sparse fourier transform.  In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 87–90, 2013.
  * [INR92] Sandy Irani, Moni Naor, and Ronitt Rubinfeld.  On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?  Math. Syst. Theory, 25(2):141–159, 1992.
  * [INW22] Piotr Indyk, Shyam Narayanan, and David P. Woodruff.  Frequency estimation with one-sided error.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 695–707, 2022.
  * [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, 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 2009, and 13th International Workshop, RANDOM. Proceedings, 2009.
  * [JLL+20] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff.  Learning-augmented data stream algorithms.  In 8th International Conference on Learning Representations, ICLR, 2020.
  * [JST11] Hossein Jowhari, Mert Saglam, and Gábor Tardos.  Tight bounds for lp samplers, finding duplicates in streams, and related problems.  In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 49–58, 2011.
  * [JW09] T. S. Jayram and David P. Woodruff.  The data stream space complexity of cascaded norms.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 765–774, 2009.
  * [JW18a] Rajesh Jayaram and David P. Woodruff.  Data streams with bounded deletions.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 341–354, 2018.
  * [JW18b] Rajesh Jayaram and David P. Woodruff.  Perfect lp sampling in a data stream.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 544–555, 2018.
  * [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 2019, pages 29:1–29:21, 2019.
  * [JWZ22] Rajesh Jayaram, David P. Woodruff, and Samson Zhou.  Truly perfect samplers for data streams and sliding windows.  In PODS ’22: International Conference on Management of Data, Philadelphia, pages 29–40, 2022.
  * [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.
  * [KSDC14] Hyojun Kim, Sangeetha Seshadri, Clement L. Dickey, and Lawrence Chiu.  Evaluating phase change memory for enterprise storage systems: A study of caching and tiering approaches.  ACM Trans. Storage, 10(4):15:1–15:21, 2014.
  * [Li08] Ping Li.  Estimators and tail bounds for dimension reduction in $l_{\alpha}$ $(0<\alpha\leq 2)$ using stable random projections.  In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 10–19, 2008\.
  * [LIMB09] Benjamin C. Lee, Engin Ipek, Onur Mutlu, and Doug Burger.  Architecting phase change memory as a scalable dram alternative.  In 36th International Symposium on Computer Architecture (ISCA),, pages 2–13, 2009.
  * [LNNT16] Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, and Mikkel Thorup.  Heavy hitters via cluster-preserving clustering.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 61–70, 2016.
  * [LNW18] Yi Li, Vasileios Nakos, and David P. Woodruff.  On low-risk heavy hitters and sparse recovery schemes.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 19:1–19:13, 2018.
  * [LSW18] Roie Levin, Anish Prasad Sevekari, and David P. Woodruff.  Robust subspace approximation in a stream.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS, 2018.
  * [LT23] Christian Janos Lebeda and Jakub Tetek.  Better differentially private approximate histograms and heavy hitters using the misra-gries sketch.  In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 79–88, 2023.
  * [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 2013, and 17th International Workshop, RANDOM. Proceedings, pages 623–638, 2013.
  * [M+05] Shanmugavelayutham Muthukrishnan et al.  Data streams: Algorithms and applications.  Foundations and Trends® in Theoretical Computer Science, 1(2):117–236, 2005.
  * [MAA05] Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi.  Efficient computation of frequent and top-k elements in data streams.  In Database Theory - ICDT 2005, 10th International Conference, Proceedings, pages 398–412, 2005.
  * [MG82] Jayadev Misra and David Gries.  Finding repeated elements.  Sci. Comput. Program., 2(2):143–152, 1982.
  * [MM12] Gurmeet Singh Manku and Rajeev Motwani.  Approximate frequency counts over data streams.  Proc. VLDB Endow., 5(12):1699, 2012.
  * [Mor78] Robert H. Morris Sr.  Counting large numbers of events in small registers.  Commun. ACM, 21(10):840–842, 1978.
  * [MSCT14] Jagan Singh Meena, Simon Min Sze, Umesh Chand, and Tseung-Yuen Tseng.  Overview of emerging nonvolatile memory technologies.  Nanoscale research letters, 9:1–33, 2014.
  * [MWZ22] Sepideh Mahabadi, David P. Woodruff, and Samson Zhou.  Adaptive sketches for robust regression with importance sampling.  In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM), pages 31:1–31:21, 2022.
  * [NDR08] Dushyanth Narayanan, Austin Donnelly, and Antony I. T. Rowstron.  Write off-loading: Practical power management for enterprise storage.  ACM Trans. Storage, 4(3):10:1–10:23, 2008.
  * [Nol03] John Nolan.  Stable distributions: models for heavy-tailed data.  Birkhauser New York, 2003.
  * [NY22] Jelani Nelson and Huacheng Yu.  Optimal bounds for approximate counting.  In PODS ’22: International Conference on Management of Data, pages 119–127. ACM, 2022.
  * [QGR11] Moinuddin K. Qureshi, Sudhanva Gurumurthi, and Bipin Rajendran.  Phase Change Memory: From Devices to Systems.  Synthesis Lectures on Computer Architecture. Morgan & Claypool Publishers, 2011.
  * [TDN11] Eno Thereska, Austin Donnelly, and Dushyanth Narayanan.  Sierra: practical power-proportionality for data center storage.  In European Conference on Computer Systems, Proceedings of the Sixth European conference on Computer systems, EuroSys, pages 169–182, 2011\.
  * [TZ04] Mikkel Thorup and Yin Zhang.  Tabulation based 4-universal hashing with applications to second moment estimation.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 615–624, 2004.
  * [Vig12] Stratis Viglas.  Adapting the B + -tree for asymmetric I/O.  In Advances in Databases and Information Systems - 16th East European Conference, ADBIS. Proceedings, pages 399–412, 2012.
  * [Vig14] Stratis Viglas.  Write-limited sorts and joins for persistent memory.  Proc. VLDB Endow., 7(5):413–424, 2014.
  * [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.
  * [WY23] David P. Woodruff and Taisuke Yasuda.  Online lewis weight sampling.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 4622–4666, 2023.
  * [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.
  * [WZ21a] David P. Woodruff and Samson Zhou.  Separations for estimating large frequency moments on data streams.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP, pages 112:1–112:21, 2021.
  * [WZ21b] David P. Woodruff and Samson Zhou.  Tight bounds for adversarially robust streams and sliding windows via difference estimators.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1183–1196, 2021.
  * [XDJX11] Cong Xu, Xiangyu Dong, Norman P. Jouppi, and Yuan Xie.  Design implications of memristor-based RRAM cross-point structures.  In Design, Automation and Test in Europe, DATE, pages 734–739, 2011.
  * [YLK+07] Byung-Do Yang, Jae-Eun Lee, Jang-Su Kim, Junghyun Cho, Seung-Yun Lee, and Byoung-Gon Yu.  A low power phase-change random access memory using a data-comparison write scheme.  In International Symposium on Circuits and Systems (ISCAS 2007), pages 3014–3017, 2007.
  * [ZCT+05] Qingbo Zhu, Zhifeng Chen, Lin Tan, Yuanyuan Zhou, Kimberly Keeton, and John Wilkes.  Hibernator: helping disk arrays sleep through the winter.  In Proceedings of the 20th ACM Symposium on Operating Systems Principles, SOSP, pages 177–190, 2005.
  * [Zol89] Vladimir M. Zolotarev.  One-dimensional stable distributions.  Bull. Amer. Math. Soc, 20:270–277, 1989.
  * [ZZYZ09] Ping Zhou, Bo Zhao, Jun Yang, and Youtao Zhang.  A durable and energy efficient main memory using phase change memory technology.  In 36th International Symposium on Computer Architecture (ISCA 2009), pages 14–23, 2009.