# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
The expectation of \(S_{i,j}\), considering the uniformity of \(h_{i}\) and the independence of the variables \(I_{i,j,k}\) and \(C_{k}\) is:

\[\mathbb{E}[S_{i,j}]=\sum_{k\in[m]}f(k)\mathbb{E}[I_{i,j,k}C_{k}]=\frac{1}{w} \frac{W^{s}}{W}\sum_{k\in[m]}f(k)=\frac{1}{w}\frac{W^{s}}{W}W=\frac{1}{w}W^{s}. \tag{6}\]

From (3) it follows:

\[\mathbb{E}[X_{i}]=\mathbb{E}[\hat{f}_{i,a}-f(a)]\leq\frac{1}{2}\mathbb{E}[S_{ i,j}]=\frac{1}{2w}W^{s}. \tag{7}\]

Applying [PERSON]'s inequality to the positive variable \(X_{i}\) we get: \(\forall c>0\quad\mathbb{P}\Big{[}X_{i}\geq c\frac{1}{2w}W^{s}\Big{]}\leq\frac {1}{c}\). Recalling that the algorithm computes the frequency as the minimum estimate obtained on the \(d\) rows and exploiting the independence of the variables \(X_{i}\) it holds that:

\[\mathbb{P}\Big{[}\hat{f}(a)-f(a)\geq\frac{c}{2w}W^{s}\Big{]} =\mathbb{P}\Big{[}\min_{1\leq i\leq d}\hat{f}_{i,a}-f(a)\geq\frac {c}{2w}W^{s}\Big{]} \tag{8}\] \[=\mathbb{P}\Big{[}\min_{1\leq i\leq d}X_{i}\geq\frac{c}{2w}W^{s} \Big{]}\] \[=\mathbb{P}\Big{[}\bigcap_{i=1}^{d}\Big{(}X_{i}\geq\frac{c}{2w}W^ {s}\Big{)}\Big{]}\] \[=\prod_{i=1}^{d}\mathbb{P}\Big{[}X_{i}\geq\frac{c}{2w}W^{s}\Big{]} \leq\frac{1}{c^{d}}\,.\]

By choosing \(c=e\) and observing that \(W^{s}\ll W\):

\[\mathbb{P}\Big{[}\hat{f}(a)-f(a)<\frac{e}{2w}W\Big{]}\geq\mathbb{P}\Big{[}\hat {f}(a)-f(a)<\frac{e}{2w}W^{s}\Big{]}\geq 1-e^{-d}. \tag{9}\]

If \(\delta=e^{-d}\) and \(\epsilon=e/2w\) we obtain the formula (2) that allow computing the size of the sketch from the required approximation parameters. It should be noted that in the previous proof we did not use the conservative update, therefore, taking this into account, the error should be further reduced. Theorem 2: _If \(l\) is a \(\phi\)-frequent item and is monitored by the sketch, then \(l\) is the majority item in at least one of the \(d\) buckets where it is handled with probability greater than or equal to_

\[1-\Big{(}\frac{1}{2w\phi}\Big{)}^{d}. \tag{10}\]

Proof: Let \(l\) be a \(\phi\)-frequent item mapped in the sketch, \(l\) is not recognized as a candidate item to be moved in the filter if, in all \(d\) buckets in which \(l\) is mapped, the monitored item is different from \(l\). The probability of this happening coincides with the probability of the event:

\[\forall\,1\leq i\leq d\quad\hat{f}_{i,l}=residue[i][h_{i}(l)]\leq\frac{1}{2}S_{i,h _{i}(l)}, \tag{11}\]

where \(\hat{f}_{i,l}\) indicates the estimated frequency of \(l\) on the \(i\)-th row, while \(S_{i,h_{i}(l)}\) represents the sum of the frequencies of all the items falling into the bucket in row \(i\) and column \(h_{i}(l))\). However, \(l\) is a \(\phi\)-frequent item and the ACMSS algorithm cannot underestimate the frequency of the items, so the above condition is equivalent to:

\[\mathbb{E}[S_{i,j}]=\sum_{k\in[m]}f(k)\mathbb{E}[I_{i,j,k}C_{k}]=\frac{1}{w} \frac{W^{s}}{W}\sum_{k\in[m]}f(k)=\frac{1}{w}\frac{W^{s}}{W}W=\frac{1}{w}W^{s}. \tag{6}\]0where \(W\) is the total weight of the stream and \(f(l)\) the actual frequency of \(l\). Therefore, setting a row index \(i\), if \(\hat{f}_{i,l}=residue[i][h_{i}(l)]\) then \(\phi W<\frac{1}{2}S_{i,h_{i}(l)}\) and

\[\mathbb{E}[S_{i,j}]=\sum_{k\in[m]}f(k)\mathbb{E}[I_{i,j,k}C_{k}]=\frac{1}{w} \frac{W^{s}}{W}\sum_{k\in[m]}f(k)=\frac{1}{w}\frac{W^{s}}{W}W=\frac{1}{w}W^{s}. \tag{6}\]1

Similarly to what we already saw in the previous proof:

\[\mathbb{E}[S_{i,j}]=\sum_{k\in[m]}f(k)\mathbb{E}[I_{i,j,k}C_{k}]=\frac{1}{w} \frac{W^{s}}{W}\sum_{k\in[m]}f(k)=\frac{1}{w}\frac{W^{s}}{W}W=\frac{1}{w}W^{s}. \tag{6}\]2

with \(W^{s}\) the total weight in the sketch. Applying [PERSON]'s inequality with \(c=2w\phi\) we get:

\[ \begin{split}\mathbb{P}\Big{[}S_{i,h_{i}(l)}\geq 2w\phi \cdot\mathbb{E}[S_{i,h_{i}(l)}]\Big{]}&=\mathbb{P}\Big{[}S_{i,h _{i}(l)}\geq 2w\phi\frac{1}{w}W^{s}\Big{]}\\ &=\mathbb{P}\Big{[}S_{i,h_{i}(l)}\geq 2\phi W^{s}\Big{]}\leq \frac{1}{2w\phi}.\end{split}