Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

There are several slightly different models that one can consider. By default we consider an insertion-only stream of length $m$ consisting of items $x_1,\mathrm{\dots },x_m.$ In the sliding window model, there is a window of size $W$ consisting of the $W$ most recent updates to the stream. A correct sliding window algorithm may be queried for the desired statistic at any time $t,$ and it must produce a correct estimate for the statistic on the stream $x_{m-W+1},\mathrm{\dots },x_m$ of the $W$ most recent updates. When we refer to the failure probability for such an algorithm, we mean the probability of failure for a single query (for an arbitrary value of $t$).

One could also consider the problem of tracking a stream statistic over the sliding window at all times. This could be accomplished in our framework simply by making the failure probability $1/m$.

One could also consider a more general model where there is no fixed window. Instead at a given query time $t$, the algorithm receives a positive integer $n$ and must estimate the stream statistic on the portion of the stream in $(t-n,t].$ The difference is that $n$ is now not known until runtime. Our algorithms all apply to this more general model, and our lower bounds hold in the standard sliding window model. This model may be useful if one wants to observe how the stream has changed up to the present time. For instance if we were monitoring network traffic, we might be interested in which IP addresses occurred frequently in the past hour, day, week, etc.

In the version of the $(\epsilon ,\delta ,F_p)$ moment estimation problem that we consider, we receive a series of insertion-only updates $x_1,\mathrm{\dots },x_m.$ At any point in time $t$ the algorithm may be asked to output an estimate $\widehat{F}$ of the $F_p$ moment of the window $W=[t-n+1,t]$ consisting of updates $x_{t-n+1},\mathrm{\dots },x_t.$ If $f_i^{(W)}$ is the frequency count of universe item $i$ over the window, then the $F_p$ moment over the window is defined to be $F_P(f^{(W)})={\sum }_i{(f_i^{(W)})}^p.$ In order to be correct, the algorithm must satisfy $\widehat{F}=(1\pm \epsilon )F_p(f^{(W)})$ with probability at least $1-\delta .$

We say that item $i$ is $(\epsilon ,{\mathrm{\ell }}_p)$-heavy for a frequency vector $f$ if $f_i\ge \epsilon {\Vert f\Vert }_p.$ In the $(\epsilon ,{\mathrm{\ell }}_p)$-heavy hitters problem the goal is to output a collection $\mathscr{H}$ of $O({\epsilon }^{-p})$ universe items such that all $(\epsilon ,{\mathrm{\ell }}_p)$-heavy items for $f^{(W)}$ are contained in $\mathscr{H}$ and such that all elements of $\mathscr{H}$ are at least $c\epsilon$-heavy where $c>0$ is a constant.

We give an algorithm for $F_p$ moment estimation for that achieves optimal bounds in the sliding window model, in terms of the accuracy $\epsilon$ and the window size $n$.

Note that this result is for approximating the $F_p$ on any fixed window with $2/3$ probability. To track $F_p$ at all times, and guarantee correctness at all times with good probability, one could apply our algorithm $O(\log m)$ times in parallel, and take the median estimate at each time.

As a consequence of our $F_2$ approximation scheme, we obtain an optimal heavy-hitters algorithm by combining with the results of [7].

An earlier version of [7] claimed this bound for the stronger problem of tracking the heavy-hitters on the window at all times. Unfortunately this original bound was incorrect, and their algorithm actually gives a ${\log }^{3}n$ dependence, even in our setting where we are interested in obtaining good success probability for a single window.

We also show that our $F_p$ estimation algorithms are tight in the sliding window model up to $\log \frac{1}{\epsilon }\log \log n$ factors. Specifically, we show

The first term in the lower bound is our contribution. The second term applies to general insertion-only streams, and follows from a recent work of [5]. While the lower bound only applies to $p>1$, our proof also applies to $p=1$ if the stream is allowed to contain empty insertions that do not affect the frequency counts, but that move the window. (Without empty insertions $p=1$ is trivial, since $F_1$ is always the window size.)

To motivate our approach, consider approximating $F_2$ to within a constant factor. We first recall the framework introduced by [9] for the sliding window model. The rough idea is to start a new $F_p$ estimation sketch at each point in the stream. This clearly gives a sliding window estimate, but uses far too much space. However, the observation is that if sketch $i$ and sketch $i+2$ give similar estimates for $F_p$ at a given point in the stream, then they will continue to do so for the remainder of the stream. The estimate given by sketch $i+1$ is sandwiched between the estimates from the neighboring sketches, so sketch $i+1$ is redundant, and we may safely delete it. After deleting all redundant sketches, we are left with $O(\log n)$ sketches (for constant $\epsilon$) with geometrically increasing $F_p$ estimates.

Each of these $F_2$ sketches uses $O(\log n\log \frac{1}{\delta })$ bits of space to estimate $F_2$ with probability $1-\delta$, so this approach requires $O({\log }^{2}n\log \frac{1}{\delta })$ bits. Since we only store $\log n$ sketches at a time, it might seem that we can take $\delta =O(\frac{1}{\log n}).$ This is a subtle point and has been a source of error in prior work.

In fact we cannot take $\delta =O(\frac{1}{\log n})$ if we are only guaranteed that our sketches correctly estimate $F_2$ with probability at least $1-\delta$. To see why, suppose that each sketch we create is correct with probability at least $1-\delta$ and is otherwise allowed to be adversarially incorrect with probability $\delta .$ With $\delta =O(1/\log n),$ it is likely that two consecutive sketches will eventually both be incorrect. In that case, they can conspire to in turn sandwich and wipe out all sketches in front of them, from which we will not be able to recover. While extreme, this example illustrates that an $F_p$ estimation sketch with a failure probability guarantee is not sufficient for us. This is why prior approaches for estimating the ${\mathrm{\ell }}_p$ norm or $F_p$ moment in sliding windows require $\mathrm{\Omega }({\log }^{3}n)$ bits of space, with one of the logarithmic factors arising from the need for sketches with high success rates. These high-success-rate sketches necessitate union bounds over all sketches, even though most of them are not kept by the algorithm when we make a query.

Of course we should not expect sketches to fail this way in practice. Could there be a somewhat stronger guarantee that rules out this type of adversarial behavior? In this work, we overcome this limitation by introducing a new tool: the Strong Estimator . This estimator enables a refined analysis that avoids the union-bound overhead, allowing us to achieve the first space complexity which breaks the $O({\log }^{3}n)$ bit barrier.

The intuition of Strong Estimator is for a window $[l,r]$, we do not need our estimator to be right (meaning give an $ϵ$ approximation) on any sub-interval of this window, but rather only an additive error: $ϵ$ fraction of the ${\mathrm{\ell }}_p$ norm of the window suffices for maintaining the timestamps. Thus we can avoid the union bound for all sub-intervals to be right. The intuition is similar to the weak tracking in [4].

In Section $3$, we show that Strong Estimator with the simplest algorithm in [8] suffices to give an $ϵ$ approximation to the ${\mathrm{\ell }}_p$ norm of the sliding window. However, this simple algorithm uses $\tilde{O}({ϵ}^{-3p}{\log }^{2}n)$ bits of space, which requires a high dependence on $ϵ$.

In Section $4$, we introduce Difference Estimator [21] to improve the $ϵ$ dependence. We first use our simple algorithm to give a constant factor partition on the top level. We then use a binary tree-like structure to make a more detailed partition between the top level, and use Difference Estimator estimator to exclude the contribution that is not in the window. The algorithm in [21] requires $\tilde{O}({ϵ}^{-2}{\log }^{3}n)$ space. The extra $\log n$ factor also comes from the high success probability requirement. Using the Strong Estimator and the structure of their algorithm, we can obtain an algorithm using $O({ϵ}^{-2}{\log }^{2}n)$ bits of memory. We further discover that the bottleneck of the algorithm comes from the Difference Estimator , which can be stored by rounded values using the rounding procedure in [16]. We thus improve the space to $\tilde{O}({ϵ}^{-p}{\log }^{2}n+{ϵ}^{-2}\log n)$ bits, which gives a separation between $p=2$ and . We further prove a lower bound on $F_p$ moment estimation over sliding windows, see below, showing that our algorithm is nearly optimal.

[7] showed that if one has an ${\mathrm{\ell }}_2$ estimation algorithm over a sliding window, then one can find the ${\mathrm{\ell }}_2$ heavy hitters with $\tilde{O}({ϵ}^{-2}{\log }^{2}n)$ additional bits of space. In [17], they show that an ${ϵ}^{p/2}$ - heavy hitter algorithm for ${\mathrm{\ell }}_2$ also finds $ϵ$- heavy hitters for ${\mathrm{\ell }}_p$. Thus, using our simplest algorithm to provide a constant ${\mathrm{\ell }}_2$ estimation over the window will give us an algorithm that uses $\tilde{O}({ϵ}^{-p}{\log }^{2}n)$ bits of space, and returns all the $ϵ$-${\mathrm{\ell }}_p$ heavy hitters. This matches the lower bound $\mathrm{\Omega }({ϵ}^{-p}{\log }^{2}n)$ for heavy hitters in [7].

For our lower bound for $F_p$ estimation, we construct a stream that consists of roughly $\log (n)$ blocks, where each block has half the $F_p$ value of the prior block. Within each block, we place ${\epsilon }^{-p}$ items that are each $(\epsilon ,{\mathrm{\ell }}_p)$-heavy for the block, and arrange them so that each of these heavy items occurs in a contiguous “mini-block”. Overall, there are $\frac{1}{{\epsilon }^p}\log (n)$ of these “mini-blocks”.

The main observation is that a correct streaming algorithm for $F_p$-moment estimation in the sliding window model must remember the location of each mini-block. Doing so requires $\log n$ bits of space per mini-block as long as there are at least, say, $n^{0.1}$ disjoint positions that each block can occur in, resulting in our $\mathrm{\Omega }(\frac{1}{{\epsilon }^p}{\log }^{2}n)$ lower bound.

To see why our algorithm must remember each location, consider one of the heavy items $x$ in our construction, and suppose we want to decide whether the mini-block for $x$ occurs entirely before or entirely after stream index $i.$ We first shift the sliding window so that it begins at index $i$. We would like to decide whether or not $x$ occurs in the resulting window. By the geometric decay of the blocks, $x$ remains heavy for the entire window. Then to decide if $x$ remains in the window we append $Q$ copies of $x$ to the window, where $Q$ is a rough estimate of the $F_p$ over the window. If $x$ does not occur in the window, then appending the $x$’s increases the $F_p$ by $Q^p.$ On the other hand, if $x$ does occur roughly $\epsilon Q$ times in the window then the $F_p$ increases by ${(\epsilon Q+Q)}^p-{(\epsilon Q)}^p=\mathrm{\Theta }((1+\epsilon )Q^p).$ Since $Q^p$ is approximately the $F_p$ moment of the window, a $\mathrm{\Theta }(\epsilon )$ heavy-hitters algorithm can distinguish between these two cases. A minor issue is that as stated, we would need to append the $x$’s without shifting the window past the index $i$. However we can easily fix this by appending the $x$’s before performing appending singletons to accomplish the shift. To make the above intuition precise we give a reduction from the IndexGreater communication game in Section 5.

We now describe how to apply rounding to the estimates computed by Strong Estimator to achieve space efficiency.

Throughout the algorithm, the sketch $f_{i,j,k}$ is used to estimate the ${\mathrm{\ell }}_p$ norm over the interval from timestamp $t_{i,j,k}$ to either another timestamp $t^{\prime }$ or the current time. While we maintain exact estimates for intervals ending at the current time, we observe that for estimates ending at previous timestamps $t^{\prime }$, we can round the values to save space. Specifically, we round $f_{i,j,k}^{(t_{i,j,k},t^{\prime })}$ to the nearest power of $(1+\frac{1}{16})$. The following claim shows that this rounding preserves the Strong Estimator property up to a small additive loss:

Thus, in our analysis, since we use $(\frac{1}{8},\frac{2^{-1/p}ϵ}{2^{32}},{\delta }_{\text{sub}})$-Strong Estimator , we may safely treat the rounded sketches as $(\frac{1}{4},\frac{2^{-1/p}ϵ}{2^{30}},{\delta }_{\text{sub}})$-Strong Estimator without loss of generality.

However, directly storing $O(s^2)$ rounded values (where $s=O({ϵ}^{-p}\log n)$ is the number of timestamps) would still be space-inefficient. To address this, we introduce the following compression technique: