# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameters** & **Values** & **Default Value** \\ \hline w & 250, 500, 750, 1000, 1250 & 500 \\ \(\rho\) & 1.0, 1.1, 1.3, 1.7, 2.5 & 1.3 \\ \(\phi\) & 0.0005, 0.001, 0.002, 0.004, 0.008 & 0.002 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Parameter values. Figure 1: Efficiency of the algorithms: Stream processing throughput. the strategy of allocating a Space-Saving mini-summary in each bucket of the sketch produces an increase in the accuracy of the estimate compared to the competitor. The remarks made for the Absolute Error apply similarly to the Relative Error, as shown in Figure 3 and Table 4. As shown in Figure 4 and Table 5, the ACMSS recall is always equal to 100% unless the \(\phi\) threshold is very small; however, even with a \(\phi\) threshold = 0. 0005 ACMSS obtains a recall of 99.34%, so there is almost no chance that this algorithm produces false negatives. The excellent results of ACMSS stem from the possibility of continuing the search for heavy hitters in the sketch, and not just in the filter. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Space (KB)** & **8.44** & **16.25** & **24.06** & **31.87** & **39.69** \\ \hline Relative Error: Average (ASKetch) & 4841.65 & 1993.86 & 1175.07 & 807.61 & 606.38 \\ Relative Error: Average (ACMSS) & 4558.88 & 1964.95 & 1147.28 & 806.20 & 601.94 \\ Relative Error: Maximum (ASKetch) & 31,554.00 & 20,760.00 & 16,175.00 & 10,787.00 & 12,337.00 \\ Relative Error: Maximum (ACMSS) & 11,028.00 & 6974.00 & 4864.00 & 3465.00 & 3082.00 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Relative Error: Average and maximum, zipfian distribution with skew \(\rho=1.3\) and support threshold \(\phi=0.002\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Space (KB)** & **8.44** & **16.25** & **24.06** & **31.87** & **39.69** \\ \hline Absolute Error: Average (ASKetch) & 6059.87 & 2497.51 & 1470.74 & 1011.89 & 759.34 \\ Absolute Error: Average (ACMSS) & 5710.35 & 2461.90 & 1437.89 & 1010.71 & 754.91 \\ Absolute Error: Maximum (ASKetch) & 36,061 & 30,228 & 21,596 & 15,824 & 17,234 \\ Absolute Error: Maximum (ACMSS) & 17,606 & 11,018 & 6346 & 6031 & 4913 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Absolute Error (average and maximum), zipfian distribution with skew \(\rho=1.3\) and support threshold \(\phi=0.002\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Space (KB)** & **8.44** & **16.25** & **24.06** & **31.87** & **39.69** \\ \hline Relative Error: Average (ASKetch) & 4841.65 & 1993.86 & 1175.07 & 807.61 & 606.38 \\ Relative Error: Average (ACMSS) & 4558.88 & 1964.95 & 1147.28 & 806.20 & 601.94 \\ Relative Error: Maximum (ASKetch) & 31,554.00 & 20,760.00 & 16,175.00 & 10,787.00 & 12,337.00 \\ Relative Error: Maximum (ACMSS) & 11,028.00 & 6974.00 & 4864.00 & 3465.00 & 3082.00 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Relative Error: Average and maximum, zipfian distribution with skew \(\rho=1.3\) and support threshold \(\phi=0.002\). Figure 2: Accuracy of the algorithms: Average Absolute Error. In Figure 5 it can be finally observed that our algorithm, when all the parameters considered vary, obtains 100% of precision, so each item detected as frequent actually is a frequent item. Figure 4: Accuracy of the algorithms: Recall. Figure 5: Accuracy of the algorithms: Precision. Figure 3: Accuracy of the algorithms: Average Relative Error. ## 7 Conclusions

We designed and analyzed ACMSS, an algorithm for frequency estimation and heavy hitter detection, and compared it against the state of the art ASketch algorithm. Through extensive experimental results we have shown that, given the same budgeted amount of memory, for the task of frequency estimation our algorithm outperforms ASketch with regard to accuracy.