# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 4 The ASketch Algorithm
```
Data:\((s,v)\), stream pair to be processed Result: filter or sketch updated with new pair \((s,v)\) lookup \(s\) in filter; ifitem foundthen  let \(i\) be the index of the counter monitoring \(s\); \(new\_count[i]\gets new\_count[i]+v\); elseiffilter not fullthen  let \(i\) be the index of a free counter in the filter; \(item[i]\gets s\); \(new\_count[i]\gets v\); \(old\_count[i]\gets 0\); else  update sketch with \((s,v)\); \(\hat{f}(s)\leftarrow\textsc{CMQuery}(s)\);  let \(i_{m}\) be the index of the item with minimum estimated frequency in filter; if\(\hat{f}(s)>new\_count[i_{m}]\)then if\(new\_count[i_{m}]-old\_count[i_{m}]>0\)then  update sketch with \((item[i_{m}],new\_count[i_{m}]-old\_count[i_{m}])\);  end if \(item[i_{m}]\gets s\); \(new\_count[i_{m}]\leftarrow\hat{f}(s)\); \(old\_count[i_{m}]\leftarrow\hat{f}(s)\);  end if  end for
```  
**Algorithm 2**Update  
In case the above conditions are not fulfilled, ASketch updates the sketch with \((s,v)\) and estimates the frequency of \(s\) using the appropriate Count-Min procedure, denoted by CMQuery. Let \(\hat{f}(s)\) be the value returned by CMQuery(s) and \(i_{m}\) be the index of the item in the filter with minimum \(\mathit{new\_count}\) value; if \(\hat{f}(s)\) is less than or equal to \(\mathit{new\_count}[i_{m}]\) no other operation is performed and the next pair is processed. If \(\hat{f}(s)\) is strictly greater than \(\mathit{new\_count}[i_{m}]\), then the item \(item[i_{m}]\) is removed from the filter and updated in the sketch with weight given by the difference between \(\mathit{new\_count}[i_{m}]\) and \(\mathit{old\_count}[i_{m}]\), if that difference is greater than zero and finally \(s\) is put into \(item[i_{m}]\) and the related \(\mathit{new\_count}[i_{m}]\) and \(\mathit{old\_count}[i_{m}]\) variables are set to the value \(\hat{f}(s)\). The frequency of an item \(s\) is given by the \(\mathit{new\_count}\) counter if it is monitored in the filter, otherwise it is computed using the sketch by the Count-Min procedure, as in Algorithm 3. ```
Data:\(s\), an item Result: estimation of item \(s\) frequency lookup \(s\) in filter; ifitem foundthen  let \(i\) be the index of the counter monitoring \(s\); return\(\mathit{new\_count}[i]\); else return\(\textsc{CMQuery}(s)\);  end if
```  
**Algorithm 3**PointEstimate  
The value stored in the \(\mathit{new\_count}\) counter is the real frequency of the item only if it has never been inserted in the sketch, i.e., if \(\mathit{old\_count}\) is equal to zero. In fact, the difference between \(\mathit{new\_count}\) and \(\mathit{old\_count}\) is the exact weight of the item relative to the period of time it remained in the filter. Therefore, as the length of time an heavy hitter item stays in this structure increases, the accuracy of its estimate increases and the possibility of collision with infrequent items decreases. At the same time, if the frequent items are correctly inserted into the filter, the time needed to process the stream is also significantly reduced, since there is no need to determine the frequent items images using the hash functions of the sketch. Asketch can solve, through the Query procedure, the problem of detecting heavy hitters, using \(k\) counters in the filter. Obviously the algorithm can generate false negatives if the filter is not sized appropriately; in fact, it can happen that a frequent item \(s\) is kept in the sketch because the estimated frequency, although higher than the threshold, does not exceed the value of the minimum \(\mathit{new\_count}\) counter. It is worth noting here that ASketch can also return false positives. In case the input is a static dataset, the problem can be easily solved with a second scan of the dataset, in which the occurrences of all the items reported in the filter at the end of the first analysis are counted.