# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
It is worth noting that if the number of counters in the filter is at least \(1/\phi\), we never have to search in the sketch. In fact, in that case, the counter with minimum value in the filter is necessarily below the threshold \(\phi W\). The reason why is that the sum of all of the counters in the filter, \(W_{f}\), can not be greater than \(W\), the total weight of the input stream, for some occurrences are necessarily stored only by the sketch. Then, if the sum \(W_{f}\) is distributed among \(k\) counter with \(k\geq 1/\phi\) than the counter with minimum value is at most equal to \(W_{f}/k\leq\phi W_{f}\leq\phi W\). Now consider a generic item \(a\) mapped to the bucket in row \(i\) and column \(j=h_{i}(a)\); denoting by \(\hat{f}_{i,a}\) the estimate of \(a\) obtained in that bucket and with \(f(a)\) the real frequency of \(a\) it holds that:

\[0\leq\hat{f}_{i,a}-f(a)\leq residue[i][j]. \tag{1}\]

The first inequality is immediate since \(\mathrm{ACMSS}\) overestimates the frequency of all items. Moreover, if the item monitored in \(item[i][j]\) is different from \(a\), then \(\hat{f}_{i,a}=residue[i][j]\) and the second inequality holds noting that \(f(a)\geq 0\). Otherwise, if the item in \(item[i][j]\) coincides with \(a\), then \(\hat{f}_{i,a}=count[i][j]\), from which the inequality to prove is equivalent to: \(count[i][j]-f(a)\leq residue[i][j]\). Let us first suppose to make a non conservative update, that is to sum the item's weight to all of the buckets in which the item falls: The update is done, in each bucket, exactly as in a summary of the Space-Saving algorithm consisting of two counters, so the inequality is valid [21]. Now consider a conservative update: The error, that is the difference \(count[i][j]-f(a)\), decreases further, so the inequality still holds. Theorem 1: _Let \(\epsilon\) and \(\delta\) denote respectively an error tolerance and a probability of failure; moreover, denote by \(\sigma\) a stream of \((item,weight)\) pairs with total weight \(W\). Then, the \(\mathrm{ACMSS}\) algorithm making use of a sketch of \(d\) rows and \(w\) columns, where:_

\[d=\lceil\ln(1/\delta)\rceil,\qquad w=\left\lceil\frac{e}{2e}\right\rceil, \tag{2}\]

_solves the \((e,\delta)\)-approximate frequency estimation problem for the stream \(\sigma\)._

Proof: By construction, the error on the frequency estimation of an item can only increase when the item is monitored by the sketch. In fact, during its permanence into the filter, it is tracked exactly. This is the reason why only the size of the sketch affects the bound on the estimation error. Let \(a\) be an item of the universe set \([m]\) managed by the sketch of size \(d\times w\); let \(i\) be a fixed row index, \(j=h_{i}(a)\) the column index where \(a\) is mapped on the \(i\)-th row by the \(i\)-th hash function and \(X_{i}=\hat{f}_{i,a}-f(a)\) the variable representing the difference between the estimated frequency on the \(i\)-th row and the real frequency of \(a\). Moreover, let \(S_{i,j}\) denote the sum of the frequencies of all the items that fall in the bucket whose row is \(i\) and whose column is \(j\). Then, using (1), it holds that:

\[0\leq\hat{f}_{i,a}-f(a)\leq residue[i][j]\leq\frac{S_{i,j}}{2}. \tag{3}\]

Letting \(k\) be a generic \([m]\) item, and letting \(C_{k}\) be the indicator random variable associated to the event {the item \(k\) is managed by the sketch} and considering the indicator random variable

\[I_{i,j,k}= \begin{cases}1&\text{if }h_{i}(k)=j\\ 0&\text{otherwise}\end{cases} , \tag{4}\]

it holds that:

\[S_{i,j}=\sum_{k\in[m]}f(k)I_{i,j,k}C_{k}. \tag{5}\]

Denoting by \(W^{s}\) the total weight managed by the sketch, which is the sum of the weight actually processed by the sketch and the weight processed by the filter but then inserted in the sketch because of the exchange of items between the two data structures, the expectation of \(C_{k}\) can be approximated with \(W^{s}/W\).