# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
 \tag{15}\]

Moreover, from the inequality \(2\phi W>2\phi W^{s}\) it follows:

\[\mathbb{P}[2\phi W<S_{i,h_{i}(l)}]\leq\mathbb{P}[2\phi W^{s}\leq S_{i,h_{i}(l )}]\leq\frac{1}{2w\phi}, \tag{16}\]

hence

\[\mathbb{P}\big{[}\hat{f}_{i,l}=residue[i][h_{i}(l)]\big{]}\leq\mathbb{P}\big{[} 2\phi W<S_{i,h_{i}(l)}\big{]}\leq\frac{1}{2w\phi}. \tag{17}\]

Therefore, the probability that \(l\), a \(\phi\)-frequent item, is not monitored in the bucket corresponding to row \(i\), and column \(h_{i}(l)\) is at most \(1/2w\phi\). The item \(l\) is not a candidate to be moved in the filter if it is not monitored in any bucket, and the probability of this happening is:

\[\mathbb{P}\Big{[}\bigcap_{i=1}^{d}\big{(}\hat{f}_{i,l}=residue[i][h_{i}(l)] \big{)}\Big{]}\leq\Big{(}\frac{1}{2w\phi}\Big{)}^{d}, \tag{18}\]

being the rows of the sketch independent. As a final remark, the following Lemma holds, the proof of which follows straight from the algorithm's operations. Lemma 1: _Let \(l\) be a \(\phi\)-frequent item; \(l\) is not reported by the_ Query _procedure of_ ACMSS _and therefore it is a_ false negative _if and only if it is not monitored in the filter and it is not a majority item in any bucket of the sketch._

For what stated by Theorem 2 and Lemma 1 we can be confident that the probability of a \(\phi\)-frequent item being a false negative for ACMSS is indeed very low. Furthermore, Theorem 1 provides assurances on the error in frequency estimation committed by the algorithm. Therefore, we can state that, with a high probability which depends on the size of the data structures used, ACMSS also solves the \(\epsilon\)-approximate frequent items problem (Definition 5). ## 6 Experimental Results

We shall compare the experimental results, obtained on synthetic datasets, of the ACMSS and ASketch algorithms. The hash functions used to manage the data structures are the same for all the algorithms. In particular, for the rows of the sketch the \(xxHash\) function has been chosen; instead, the filter hasbeen implemented through a Space-Saving Stream-Summary and the _hash3_1 function has been used to arrange the items in the hash table. The algorithms have been implemented in C++; the source code was compiled using the Intel c++ v19.0.4 compiler on linux CentOS 7 with the following flags: -O3 -std=c++14. The tests were performed on a workstation with 64 GB RAM and two 2.0 GHz Intel Xeon exa-core E5-2620 CPUs with 15 MB cache level 3. The metric used to evaluate the efficiency of the algorithms is stream processing throughput, corresponding to the average number of pairs (items, weight) processed per time unit and measured in items per millisecond. In order to evaluate the accuracy of the algorithms with regard to the frequency estimation problem, the following metrics have been used:

* average absolute error, given by the sum, obtained on all the items of the whole universe \([m]\), of the difference between estimated frequency and real frequency of the item, divided by the cardinality of the whole \([m]\): \(AverageAbsoluteError=\frac{\sum\limits_{i\in[m]}|\hat{f}(i)-f(i)|}{m}\);
* absolute maximum error, i.e., the maximum variation between estimated and real frequency, recorded on all items in the universe as a whole;
* average relative error which is given by the ratio between the sum of relative errors on items with positive frequency and the number of items that satisfy the latter condition. The relative error of an item is the difference between the estimated and the actual frequency, divided by its exact frequency: \(AverageRelativeError=\frac{\sum\limits_{i\in[m]:\,\hat{f}(i)>0}|\hat{f}(i)-f(i )|/f(i)}{|\hat{v}|\in[m]:\,f(i)>0|}\);
* maximum relative error, i.e., the maximum relative error obtained on items whose frequency is positive. The precision and recall metrics instead allow evaluating the accuracy with regard to the problem of determining the heavy hitters.