# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 4 The ASketch Algorithm  
In most practical cases where an estimate of the frequency is required, the interesting data is represented by the items prevailing in the stream or of greater weight: In any online shopping site there is the section \"best-selling items\", on YouTube the section \"trends\", in Netflix there are three: \"The most viewed on Netflix\", \"the headlines of the moment\" and \"champions of cashiers\". Instead there are very few contexts in which the attention is focused on uncommon or lighter objects. It is for this reason that many algorithms have focused mainly on improving the estimation of frequent items: They are in fact a particular and small group of items whose error strongly affects the accuracy of the produced summaries. Given the good answers obtained by Count-Min with a smaller space than that required by the other algorithms on sketch, and given the guarantee of overestimation, the research started from this technique and studied the weak points: Collisions with frequent items. The problem is represented both by collisions between two frequent items and those between frequent and infrequent items; if in the first case it is the estimates of both items that are affected, in the second case the difficulty is mainly related to the non frequent item, and the consequent classification error that would make it a false positive. Such errors may seem insignificant if the objective of the analysis is simply to increase sales by highlighting what the public appreciates, but if the estimation of frequency is only an intermediate step, upon which procedures that control thresholds or identify particular statistics must be built, then such errors become crucial. From Count-Min study it became clear that removing the frequent items from the sketch would lead to a marked improvement in the results, because it would prevent them from colliding with the remaining items, thus eliminating some of the noise. Several approaches have been developed in an attempt to develop optimal techniques to manage and especially to recognize frequent items; among these approaches there is Augmented Sketch, known simply as ASketch[10]. ASKetch is an algorithm that dynamically identifies frequent items and moves them from the main sketch into a structure, called a filter, where no collisions occur. The space is then divided into filter and sketch; the former is made up of a set of \(k\) counters shaped as \((item[i]\), \(new\_count[i]\), \(old\_count[i])\), where \(i=1,2,\ldots,k\) and \(item[i]\) is the item monitored by the \(i\)-th counter; the sketch can take different forms depending on the frequency estimation algorithm on which ASketch rests, in the following we will assume that this is Count-Min. The algorithm is presented as able to solve the frequency estimation problem but, because of the duplicity of the structure used, it is suitable also for heavy hitter detection. Let \(d^{\prime}\) and \(w^{\prime}\) be respectively the number of rows and columns of the sketch and let \(k\) be the number of filter counters, the _new_count_ and _old_count_ components are set to zero and the sketch is initialized, as shown in Algorithm 1. ```
Data:\(k\), filter size; \(d^{\prime}\), sketch rows; \(w^{\prime}\), sketch columns Result: filter and sketch initialized filter is empty; for\(i=1\) to \(k\)do \(new\_count[i]=0\); \(old\_count[i]=0\); end  initialize the sketch;
```  
**Algorithm 1**Initialize  
As shown in Algorithm 2, in order to process the pair \((s,v)\) of the stream \(\sigma\), ASketch checks if \(s\) is monitored in one of the filter counters, if so it increases by \(v\) the value of the corresponding _new_count_ variable, leaving _old_count_ unchanged. Otherwise, if there is a free counter in the filter, the item \(s\) is stored in that counter by setting _new_count_ equal to \(v\) and _old_count_ equal to zero.