# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm
In case the value in \(item[i][j]\) coincides with \(s\) we have to update, only if necessary, the \(count[i][j]\) value, so the update happens only if the value in \(count[i][j]\) is less than the sum of the \(v\) weight and the estimated frequency \(\hat{f}(s)\). If, on the other hand, the item in \(item[i][j]\) is different from \(s\), then the \(residue[i][j]\) value should be updated to the new frequency \(\hat{f}(s)+v\), taking care of replacing the item stored in \(item[i][j]\) if necessary. So, if updating \(residue[i][j]\) is necessary and the new frequency \(\hat{f}(s)+v\) is strictly greater than the value of \(count[i][j]\), the item monitored by \(item[i][j]\) is replaced by \(s\), \(residue[i][j]\) takes the value \(count[i][j]\) and \(count[i][j]\) is updated with the frequency \(\hat{f}(s)+v\). Note that in the hypothesis just made the update of \(residue[i][j]\) is necessary, otherwise it is possible to underestimate the frequency of the items mapped in the bucket that are different from \(s\). The output is the updated sketch and the boolean variable \(r\), whose value is \(1\) if the item \(s\) is the majority item in at least one bucket of the sketch. SketchPointEstimate computes the frequency of the item \(s\) considering the minimum value of the estimate obtained scanning the \(d\) buckets in which the item is mapped to by the hash functions. Fixing \(1\leq i\leq d\), the frequency of \(s\) on the \(i\)-th row is given by \(count[i][h_{i}(x)]\) if \(item[i][h_{i}(x)]\) is equal to \(s\), otherwise it is \(residue[i][h_{i}(x)]\). The PointEstimate procedure, shown as Algorithm 8, returns the estimated frequency of the item \(s\) received as input: We first check if \(s\) is monitored in the filter and if so we return the value of \(count[i]\), where \(i\) is the index of the filter counter monitoring \(s\), otherwise SketchPointEstimate is used to estimate the frequency of \(s\) in the sketch. ```
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\(count[i]\); else return\(\textsc{SketchPointEstimate}(s)\); end
```
**Algorithm 8**PointEstimate

The Query procedure, shown as Algorithm 9, returns the \(\mathcal{R}\) set of \(\phi\)-frequent items with their estimated frequency. \(\mathcal{R}\) is, initially, the set of items monitored in the filter whose frequency counter is above the \(\phi\cdot W\) threshold. If \(c\), which is the number of pairs in \(\mathcal{R}\), is less than the filter size, the search for \(\phi\)-frequent items stops. In fact, in that case, at least one counter, the counter with minimum frequency, is below the \(\phi\cdot W\) threshold and we can be sure that all of the frequent candidates monitored by the sketch with frequency above the threshold have already been inserted in the filter. ```
Data:\(\phi\), threshold parameter for frequent items; \(k\), filter size Result: set \(\mathcal{R}\) of frequent items \(\mathcal{R}\leftarrow\emptyset\); \(c\gets 0\); forall\(i\) in filterdo if\(count[i]>\phi\cdot W\)then \(\mathcal{R}\leftarrow\mathcal{R}\cup\{(item[i],count[i])\}\); \(c\gets c+1\);  end if end if if\(c=k\)then for\(i=1\) to \(d\)do for\(j=1\) to \(w\)do if\(count[i][j]>\phi\cdot W\)then \(s\gets item[i][j]\); \(f\leftarrow\textsc{SketchPointEstimate}(s)\); if\(f>\phi\cdot W\)then \(\mathcal{R}\leftarrow\mathcal{R}\cup\{(s,f)\}\);  end if end end if end return\(\mathcal{R}\). ```

**Algorithm 9**Query

Instead, if all the monitored items in the filter are in \(\mathcal{R}\), then also the minimum counter in the filter has a value above the threshold and there may be some frequent candidates with frequency above the threshold among the items monitored by the sketch. Let \(s\) be the element monitored in \(item[i][j]\); if the frequency in \(count[i][j]\) and the value returned by \(\textsc{SketchPointEstimate}(s)\) are above the \(\phi\cdot W\) threshold, then \(s\) is inserted into \(\mathcal{R}\) with its estimated frequency.