The SpaceSaving± Family of Algorithms for Data Streams with Bounded Deletions

There is a large body of algorithms proposed to solve frequency estimation and heavy hitters problems (Misra and Gries, 1982; Metwally et al., 2005; Charikar et al., 2002; Cormode and Muthukrishnan, 2005; Karp et al., 2003; Demaine et al., 2002; Braverman et al., 2017; Jayaram and Woodruff, 2018; Zhao et al., 2021a, 2022; Manku and Motwani, 2002). The existing algorithms can be classified into three models: insertion-only, turnstile, and bounded-deletion. In the insertion-only model, all arriving stream items are insertions and the frequency $f(x)$ of $x$ is the number of times $x$ has been inserted. SpaceSaving (Metwally et al., 2005) and MG (Misra and Gries, 1982) are two popular algorithms that operate in the insertion-only model; they provide strong deterministic guarantees with minimal space. Moreover, since these algorithms are deterministic, they are inherently adversarial robust (Hasidim et al., 2020; Ben-Eliezer et al., 2022; Cohen et al., 2022). In the turnstile model, arriving stream items can be either insertions or deletions and the (net) frequency $f(x)$ of $x$ is the difference between the number of times $x$ has been inserted and deleted, with the proviso that no item’s frequency is negative. Count-Min (Cormode and Muthukrishnan, 2005) and CountSketch (Charikar et al., 2002) are two popular algorithms that operate in the turnstile model. Supporting deletions is a harder task and as a result Count-Min and Count-Sketch require more space with poly-log dependence on the input domain size to offer strong error bounds with high probability (Alon et al., 1996). The bounded deletion model (Jayaram and Woodruff, 2018; Zhao et al., 2021b, a) assumes the number of deletions are bounded by a fraction of the number of insertions. For instance, in standard testings, if students are only allowed to submit one regrade request on their tests, then the number of deletions is at most half of the number of insertions in which updating a student’s grade is a deletion followed by an insertion.

Recently, SpaceSaving$\pm$ (Zhao et al., 2021a) proposed an algorithm extending the original SpaceSaving (Metwally et al., 2005) to handle bounded deletions efficiently, (implicitly) assuming (Zhao et al., 2021a) that the data stream has no interleaving between insertions and deletions: all insertions precede all deletions (Metwally et al., 2005) (Zhao et al., 2023a). In addition, Berinde et al. (Berinde et al., 2010) showcased that data summaries in the insertion-only model can achieve an even stronger error bound using residual error analysis. The difference among these algorithms and their corresponding error guarantees is listed in Table 1. As a result, in this work, we aim to investigate the SpaceSaving$\pm$ family of algorithms to support interleavings between insertions and deletions and provide a tighter error bound analysis.

In this paper, we present a detailed analysis of the SpaceSaving$\pm$ family of algorithms with bounded deletions. In particular, we propose three new algorithms: Double SpaceSaving$\pm$, Unbiased Double SpaceSaving$\pm$, and Integrated SpaceSaving$\pm$, which operate in the general bounded deletion model (with interleavings of insertions and deletions) and provide strong theoretical guarantees with small space, while having distinct characteristics. In addition, we introduce the residual error bound guarantee in the bounded deletion model and prove that the proposed algorithms satisfy the stronger residual error guarantee. Moreover, we demonstrate that the proposed algorithms also achieve the relative error bound (Mathieu and de Rougemont, 2023; Cormode et al., 2021) under mild assumptions, assuming skewness in the data stream. Finally, we provide a merge algorithm for our proposed algorithms and prove that all proposed algorithms are mergeable in the bounded deletion model. The mergeability is critical for distributed applications (Agarwal et al., 2012).

Consider a data stream consisting of a sequence of $N$ operations (insertions or deletions) on items drawn from a universe $U$ of size $|U|=n$. We denote the stream by $\sigma=\{(item_{t},op_{t})\}_{t=\{1,2...N\}}$ where $item_{t}\in U$ is an element of the universe and $op_{t}\in\{insertion,deletion\}$. Let $I$ denote the total number of insertions and $D$ denote the total number of deletions in the stream, so that $I+D=N$. In the bounded deletion model (Jayaram and Woodruff, 2018; Zhao et al., 2021b), it is assumed that, for some parameter $\alpha\geq 1$, the stream is constrained to satisfy $D\leq(1-1/\alpha)I$. Observe that when $\alpha=1$, there can be no deletions, and so the model includes the insertion-only model as a special case. Let $f$ denote the frequency function: the frequency of an item $x$ is $f(x)=I(x)-D(x)$ where $I(x)$ denotes the number of insertions of $x$ in the stream and $D(x)$ denotes the number of deletions of $x$ in the stream. In this paper, we use a summary data structure from which we infer an estimation of the frequency function. We use $\hat{f}(x)$ to denote the estimated frequency of $x$.

Let $\{f_{i}\}_{1}^{n}$ denote the frequencies of the $n$ items, sorted in non-increasing order, so that $f_{1}\geq f_{2},...\geq f_{n}$. Similarly, sorting $\{I(x):x\in U\}$ in non-increasing order leads to $\{I_{i}\}_{1}^{n}$ where $I_{1}\geq I_{2},...\geq I_{n}$, and sorting $\{D(x):x\in U\}$ in non-increasing order leads to $\{D_{i}\}_{1}^{n}$ where $D_{1}\geq D_{2},...\geq D_{n}$. Notice that, for the same $i$, the item corresponding to $f_{i}$ may differ from the item corresponding to $I_{i}$ and from the item corresponding to $D_{i}$. For the special case of the insertion-only model, the frequency vector and insertion vector are identical. Moreover, we use $F_{1}$ to denote the total number of items resulting from the stream operations, such that $F_{1}=I-D=\sum_{i=1}^{n}f_{i}$. In this paper, we focus on the unit updates model (an operation only inserts or deletes one count of an item) and assume that at any point of time, no item frequency is below zero (i.e, items cannot be deleted if they were not previously inserted).

All of our streaming algorithms use a summary of the information seen in the stream so far, consisting of a collection of items and some counts for each of them. The size of the summary is much smaller than $|U|$ (equivalent to $n$), and we say that an item is monitored if it is present in the summary.

The SpaceSaving$\pm$ family of algorithms are data summaries that build on top of the original SpaceSaving (Metwally et al., 2005) algorithm. In 2005, Metwally, Agrawal, and El Abbadi (Metwally et al., 2005) proposed the popular SpaceSaving algorithm that provides highly accurate estimates on item frequency and heavy hitters among many competitors (Cormode and Hadjieleftheriou, 2008). The SpaceSaving algorithm operates in the insertion-only model (so that the stream is simply a sequence of items from $U$) and uses the optimal space (Berinde et al., 2010). The update algorithm, as shown in Algorithm 1 (Metwally et al., 2005), uses $m$ counters to store a monitored item’s identity and its estimated frequency. When a new $item$ arrives: if $item$ is monitored, then increment its counter; if $item$ is not monitored and the summary has unused counters, then start to monitor $item$, and set $count_{item}$ to 1; otherwise, i) find $minItem$, the item with minimum counter ($minCount$), ii) evicts this $minItem$ from the summary, and iii) monitor the new $item$ and set $count_{item}$ to $minCount+1$. See Algorithm 1.

After the stream has been read, the SpaceSaving Update algorithm has produced a summary. To solve the Frequency Estimation Problem, the algorithm then needs to estimate the frequency $f(e)$ of an item $e$ being queried: the SpaceSaving Query algorithm returns $\hat{f}(e)=count_{e}$ if $e$ is monitored and $\hat{f}(e)=0$ otherwise, as shown in Algorithm 2. (To solve the heavy hitters problem, the algorithm outputs all items in the summary whose count is greater than or equal to $\epsilon$ times the sum of the counts.)

When the number of counters (size of the summary) $m=\frac{1}{\epsilon}$, SpaceSaving solves both frequency estimation and heavy hitters problems in the insertion-only model, as shown in Lemma 2.3. Moreover, SpaceSaving satisfies a more refined residual error bound as shown in Lemma 2.4 in which ”hot” items do not contribute error and the error bound only depends on the ”cold” and ”warm” items (Berinde et al., 2010).

The $\epsilon$ error guarantee is shown in Lemma 2.3. When $m=\frac{1}{\epsilon}$, SpaceSaving ensures $\forall x\in U,|f(x)-\hat{f}(x)|\leq\epsilon F_{1}$.

The residual error guarantee is shown in Lemma 2.4.

The relative error guarantee is shown in Lemma 2.6.

In 2021, Zhao et al. (Zhao et al., 2021a) proposed SpaceSaving$\pm$ to extend the SpaceSaving algorithm from the insertion-only model to the bounded deletion model. In that model, they established a space lower-bound of at least $\frac{\alpha}{\epsilon}$ counters required to solve the frequency estimation and heavy hitters problems, and proposed an algorithm, SpaceSaving$\pm$ (see Algorithm 3), that used space matching the lower bound. The update algorithm is shown in Algorithm 3 in which insertions are dealt with as in Algorithm 1, deletions of monitored items decrement the corresponding counters, and deletions of unmonitored items are ignored. The query algorithm is identical to Algorithm 2¹¹1There are a couple of variants of Algorithm 2. We adopt the most commonly used approach..

However, the SpaceSaving$\pm$ algorithm is only correct if an implicit assumption holds (Zhao et al., 2023a), namely, that deletions can only happen after all the insertions, so that interleaving insertions and deletions are not allowed, as shown in Lemma 2.7. In this paper, we present new algorithms in the general bounded deletions model, that allow interleavings between insertions and deletions while still using only $O(\frac{\alpha}{\epsilon})$ space.

This Lemma correspond to Theorem 2 in (Zhao et al., 2021a). Consider the bounded deletions model and assume, in addition, that the stream consists of an insertion phase with $I$ insertions followed by a deletion phase with $D$ deletions (no interleaving).

In Double SpaceSaving$\pm$, we employ two SpaceSaving summaries to track insertions ($S_{insert}$) and deletions ($S_{delete}$) separately, using $m_{I}$ and $m_{D}$ counters respectively (the algorithms is parameterized by the choice of $m_{I}$ and $m_{D}$). As shown in Algorithm 4, Double SpaceSaving$\pm$ completely partitions the update operations to two independent summaries. To query for the frequency of an item $e$, both summaries need to be queried to estimate the frequency of item $e$ as shown in Algorithm 5.

Being more careful and using variants of Algorithm 2 would lead to improvements but would not change the theoretical bound of Theorem 3.2.

Unlike Double SpaceSaving$\pm$ which uses two independent summaries, Integrated SpaceSaving$\pm$ completely integrates deletions and insertions in one data structure as shown in Algorithm 6. The main difference between Integrated SpaceSaving$\pm$ and SpaceSaving$\pm$ is that Integrated SpaceSaving$\pm$ tracks the insert and delete count separately. This ensures that the minimum insert count monotonically increases and never decrease; however, the original SpaceSaving$\pm$ uses one single count to track inserts and deletes together. When insertions and deletions are interleaved, then the minimum count in SpaceSaving$\pm$ may decreases. This can lead to severe underestimation of a frequent item (Zhao et al., 2023a).

More specifically, the Integrated SpaceSaving$\pm$ data structure maintains a record estimating the number of insertions and deletions for each monitored item. When a new item arrives, if it is already being monitored, then depending on the type of operation, either the insertion or the deletion count of that item is incremented. If the summary is not full, then no item could have every been evicted from the summary, and since no delete operation arrives before the corresponding item is inserted, then any new item in the stream must be an insertion. Hence, when a new item arrives, and if the summary is not full, the new item is added to the summary and initialized with one insertions and 0 deletions. If a delete arrives and the summary is full, the delete is simply ignored. The interesting case is when an insert arrives and the summary is full. In this case, Integrated SpaceSaving$\pm$ mimics the behaviour of the original SpaceSaving$\pm$ by evicting the element with the least number of inserts and replacing it with the new element. The insertion count for the new element is overestimated by initializing it to the insertion count for the evicted element. However, the deletion count is underestimated by initializing the deletion count to zero.

To estimate an item’s frequency, if the item is monitored, it subtracts the item’s delete count from the item’s insert count, otherwise the estimated frequency is 0, as shown in Algorithm 7.

We now establish the correctness of Integrated SpaceSaving$\pm$. First, we establish three lemmas about Integrated SpaceSaving$\pm$ to help us prove the correctness of the algorithm.

Integrated SpaceSaving$\pm$ also solves the heavy hitters problem. Since Integrated SpaceSaving$\pm$ never underestimates monitored items (Lemma 3.6), then if we report all the items with frequency estimations greater than or equal to $\epsilon F_{1}$, then all heavy hitters will be identified as shown in Theorem 3.10.

We assume each field uses the same number of bits (32-bit in the implementation). Following the proofs of Theorem 3.9 and that each entry in the summary has three fields $(i,insert_{i},delete_{i})$, IntegratedSpaceSaving$\pm$ uses $3\frac{\alpha}{\epsilon}$. On the other hand, following the proofs of Theorem 3.1 and that each entry in the summary uses two fields, Double SpaceSaving$\pm$ uses $2\frac{2\alpha}{\epsilon}+2\frac{2(\alpha-1)}{\epsilon}=\frac{8\alpha-2}{\epsilon}$. Integrated SpaceSaving$\pm$ requires less memory footprint. Double SpaceSaving$\pm$ also has its own advantage and it can be extended supporting unbiased estimations (Unbiased Double SpaceSaving$\pm$).

We define $F_{1,\alpha}^{res(k)}=F_{1}-\frac{1}{\alpha}\sum_{i=1}^{k}f_{i}$. Observe that $F_{1,\alpha}^{res(k)}$ is equivalent to the residual error bound shown in Lemma 2.4, $F_{1}^{res(k)}$, for the insertion-only model, as $\alpha$ is set to 1. The residual error bound ($F_{1,\alpha}^{res(k)}$) is much tighter than the original error bound ($F_{1}$), since the residual error depends less on the heavy hitters.

First, we derive the residual error bound for Double SpaceSaving$\pm$.

We present the residual error bound for Integrated SpaceSaving$\pm$. Before presenting the proof, we first construct a helpful Lemma.

The $\epsilon$ relative error guarantee is defined such that $\forall x\in U,|f(x)-\hat{f}(x)|\leq\epsilon f(x)$. The relative error has been shown to be much harder to achieve, but with practical importance (Gupta and Zane, 2003; Cormode et al., 2021). In a recent work, Mathieu and de Rougemont (Mathieu and de Rougemont, 2023) showcased that the original SpaceSaving algorithm achieves relative error guarantees under mild assumptions. As a result, we demonstrate that the proposed algorithms in the bounded deletion model also achieve relative error guarantees under similar assumptions.

By the definition of Zipf distribution, we know that $\xi(\beta)$ converges to a small constant when $\beta>1$ and $f_{1}=F_{1}/\xi(\beta)$.