# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
In order to obtain a fair comparison, exactly the same amount of memory was used for the two algorithms; in particular the number of rows \(d\) of all sketches was set to 4, as this value corresponds to a very small \(\delta\) probability of failure. The number of filter counters, denoted by \(k\), has also been set to 32 for both algorithms. The authors of ASketch have in fact observed that this value represents a threshold: A further increase of the filter size would lead to a reduction of \(filter_{selecttivity}\), that is the ratio between the weight processed by the sketch and the total weight of the stream, really negligible, while it would continue to increase the error in the sketch due to the collisions. Considering finally \(w\), which is the number of columns used in ASketch, the value of the corresponding parameter for ACMSS, denoted by \(w^{\prime}\), has been obtained using the formula \(w^{\prime}=2w/5+2k/5d\). The values of \(w\) and \(w^{\prime}\) used in the tests are listed in Table 1. The ASketch Query procedure used to detect heavy hitters has been slightly modified with regard to the corresponding pseudo-code reported in [10]. In fact, the function has been implemented in order to return only the items contained in the filter with estimated frequency strictly higher than \(\phi W\), where \(W\) represents the total weight of the stream. In this way Query works similarly to the corresponding function of the other algorithm. \begin{table}
\begin{tabular}{c c c c c c} \hline \(w\) (ASketch) & 250 & 500 & 750 & 1000 & 1250 \\ \hline \(w^{\prime}\) (ACMSS) & 103 & 203 & 303 & 403 & 503 \\ \hline \end{tabular}
\end{table} 
Table 1: Number of columns used. The synthetic datasets, on which the tests were conducted, have a zipfian distribution; the items are represented by unsigned int variables requiring 32 bits, while the associated weights have all been fixed, without loss of generality, to 1. The seed, used for the pseudo-random number generator associated to the distribution, has been varied between 10 possible values, taking care to use in each experiment the same identical value for both the algorithms to test. The comparison between the algorithms was conducted by varying the number \(w\) of columns of ASketch and then the amount of memory occupied (budgeted memory), the skew \(\rho\) parameter of the distribution and the support threshold \(\phi\), as reported in Table 2. So, for each different value of \(\rho\) and \(\phi\), the tests were performed 10 times as the seed varied and the results were derived from the test average. The length of the streams and the number of possible distinct items were fixed at \(10^{7}\). The total space occupied by the algorithms has been varied between 8640 (in case \(w=250\)) and 40,640 bytes (in case \(w=1250\)). The default value of \(w\) has been set to 500 and consequently the default space is 16,640 bytes. As shown in Figure 1 the ASketch algorithm is more efficient than the ACMSS algorithm. In fact if an item \(i\) is processed in the sketch and if, after the update, this item must be evicted from the sketch and moved to the filter, ACMSS performs more work than ASketch. If \(x\) is the item to be removed from the filter, ACMSS must call SketchPointEstimate\((x)\) to know how much to increase the buckets counters associated with \(x\); on the contrary ASketch avoids the call, since this information is contained in \(old\_count[x]\). It should be noted that the gap between ASketch and ACMSS processing speed, remains constant as the amount of memory available to the algorithms varies. On the other hand, Figure 2 and Table 3 make it clear that the Average Absolute Error committed by ACMSS, especially on a small memory space, is lower than that committed by ASketch. Even wider is the gap between the Absolute Maximum Error of these algorithms; therefore, although the columns of the ACMSS sketch are less than half of those of ASketch (see Table 1),