# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
```
Data:\((s,v)\), stream pair to be processed Result: filter or sketch updated with new pair \((s,v)\) \(W\gets W+v\); lookup \(s\) in filter; ifitem found then  let \(i\) be the index of the counter monitoring \(s\); \(count[i]\gets count[i]+v\); elseiffilter not fullthen  let \(i\) be the index of a free counter in the filter; \(item[i]\gets s\); \(count[i]\gets v\); else \(\hat{f}(s)\leftarrow\textsc{SketchPointEstimate}(s)\); \(r\leftarrow\textsc{Updatesketch}((s,v),\hat{f}(s))\); if\(r=1\)then \(\hat{f}(s)\leftarrow\hat{f}(s)+v\);  let \(i_{m}\) be the index of the item with minimum estimated frequency in filter; if\(\hat{f}(s)>count[i_{m}]\)then \(\hat{f}(item[i_{m}])\leftarrow\textsc{SketchPointEstimate}(item[i_{m}])\); if\(count[i_{m}]-\hat{f}(item[i_{m}])>0\)then \(\textsc{Updatesketch}((item[i_{m}],count[i_{m}]-\hat{f}(item[i_{m}])),\hat{f}( item[i_{m}]))\);  end if \(item[i_{m}]\gets s\); \(count[i_{m}]\leftarrow\hat{f}(s)\);  end if  end for  end while
```  
**Algorithm 5**Update  
```
Data:\((s,v)\), stream pair to be processed; \(\hat{f}(s)\), estimated frequency of \(s\) Result: sketch updated with new pair \((s,v)\); \(r\), boolean variable worth 1 if \(s\) is monitored in at least one bucket \(r\gets 0\); for\(i=1\)to\(d\)do \(j\gets h_{i}(s)\); if\(item[i][j]=s\)then \(count[i][j]\leftarrow\textsc{max}(count[i][j],\hat{f}(s)+v)\); \(r\gets 1\); else if\(\hat{f}(s)+v>residue[i][j]\)then  if\(\hat{f}(s)+v>count[i][j]\)then \(item[i][j]\gets s\); \(residue[i][j]\gets count[i][j]\); \(count[i][j]\leftarrow\hat{f}(s)+v\); \(r\gets 1\); else \(residue[i][j]\leftarrow\hat{f}(s)+v\);  end end if  end for return\(r\). ```  
**Algorithm 6**UpdateSketch  
```
Data:\((s,v)\), stream pair to be processed Result: filter or sketch updated with new pair \((s,v)\) Result: sketch updated with new pair \((s,v)\); \(r\), boolean variable worth 1 if \(s\) is monitored in at least one bucket \(r\gets 0\); for\(i=1\)to\(d\)do \(j\gets h_{i}(s)\); if\(item[i][j]=s\)then \(count[i][j]\leftarrow\textsc{max}(count[i][j],\hat{f}(s)+v)\); \



The update in question is conservative [12; 13] since before executing UpdateSketch, the frequency of the item \(x\) must be estimated using SketchPointEstimate (shown as Algorithm 7). ```
Data:\(s\), an item Result: estimated frequency of item \(s\) from sketch answer \(\leftarrow\infty\); for\(i=1\) to \(d\)do \(j\gets h_{i}(s)\); if\(item[i][j]=s\)then  answer \(\leftarrow\) min\((answer,count[i][j])\); else  answer \(\leftarrow\) min\((answer,residue[i][j])\);  end if end returnanswer. ```
**Algorithm 7**SketchPointEstimate

As in ASketch, we evaluate if it is appropriate to pass the management of \(s\) to the filter, but, for this to happen, two conditions must be fulfilled: (i) \(s\) must be a majority item in at least one bucket of the sketch, i.e., at least one value \(item[i][h_{i}(s)]\) for \(i=1,2,\ldots,d\) must be equal to the item \(s\); (ii) the estimated frequency of \(s\) in the sketch, indicated with \(\hat{f}(s)\), must be strictly greater than the minimum frequency in the filter. Assuming that both conditions occur and the minimum frequency item in the filter is monitored by the counter with index \(i_{m}\), we update the sketch using the item \(item[i_{m}]\), with weight given by the difference between the value \(count[i_{m}]\) and the output of SketchPointEstimate\((item[i_{m}])\), when this difference is positive. Then, we assign \(s\) to \(item[i_{m}]\) and \(\hat{f}(s)\) to \(count[i_{m}]\). The UpdateSketch procedure called on the pair \(((s,v),\hat{f}(s))\) performs the conservative update of the sketch for the item \(s\) and the weight \(v\), taking into account that the current estimated frequency for \(s\) is \(\hat{f}(s)\). Let \(1\leq i\leq d\) be the row index, and \(j\) the column index of the bucket where \(s\) is mapped.