# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 5 The ACMSS Algorithm  
Augmented CMSS, or briefly ACMSS, is our randomized algorithm designed to solve the frequency estimation and the heavy hitter detection problems. Like ASketch, its operations are based on the use of two data structures: A filter and a sketch. The filter is able to correctly monitor the frequency of the elements it manages, for this reason the frequent items are inserted in this structure after being identified as such in the sketch; the two structures therefore communicate dynamically and exchange the management of the items. A bucket of the sketch keeps track of three variables: Two frequencies and the identity of the candidate as majority item in the bucket. Let \(S\) be the sum of the frequencies of all of the items mapped to the bucket by the corresponding hash function; then, the majority item, if it exists, is the item whose frequency exceeds \(\lfloor S/2\rfloor+1\). The ACMSS filter consists of \((item[i],count[i])\)-shaped counters, with \(i=1,2,\ldots,k\); \(item[i]\) denotes the item monitored by the \(i\)-th counter and \(count[i]\) is its estimated frequency. The sketch, on the other hand, substantially differs from the ASketch data structure: Each bucket consists of a tuple of values \((item[i,j],count[i,j],residue[i,j])\) for \(i=1,2,\ldots,d\) and \(j=1,2,\ldots,w\), where \(d\) and \(w\) are respectively the number of rows and columns of the sketch. Through \(item[i][j]\) the bucket at row \(i\) and column \(j\) keeps track of the majority item of its stream, i.e., all of the items falling in that bucket; \(count[i][j]\) is an estimation of the frequency of \(item[i][j]\), whilst \(residue[i][j]\) represents an estimation of the frequency of the other items falling in the bucket. Therefore, by construction, \(residue[i][j]\) handles a frequency that is less than or equal to that in \(count[i][j]\). Let \(k\) be the number of filter counters, and \(\phi\) a fixed support threshold. The size of the sketch is computed, using the approximation parameters \(\epsilon\) and \(\delta\) and the Formula (2). Each line of the sketch is associated with a hash function \(h_{i}:[m]\rightarrow[w]\), for \(i=1,2,\ldots,d\), randomly extracted from a pairwise independent family, where \([m]\) denotes the universe set of the stream. The initialization procedure, shown as Algorithm 4, sets to zero all the counters of both the filter and the sketch. The \(W\) value, initialized at zero, is used to keep track of the total weight of the stream that has already been processed. ```
Data:\(k\), filter size; \(d\), sketch rows; \(w\), sketch columns; \(\phi\), support threshold Result: filter and sketch initialized filter is empty; for\(i=1\) to \(k\)do \(count[i]=0\); end for\(i=1\) to \(d\)do for\(j=1\) to \(w\)do \(item[i][j]=0\); \(count[i][j]=0\); \(residue[i][j]=0\);  end for end choose \(d\) random hash functions \(h_{1},h_{2},\ldots,h_{d}\colon[m]\rightarrow[w]\);  set support threshold to \(\phi\); \(W\gets 0\). ```  
**Algorithm 4**Initialize  
As shown in Algorithm 5, in order to process the \((s,v)\) stream pair, where \(s\) is an incoming item and \(v\) is its weight, the first data structure to be checked is the filter; if \(s\) is already monitored, its estimated frequency is increased by the weight \(v\); otherwise, if there is a free counter, the item \(s\) is inserted in this structure and the value of the associated frequency counter is equal to \(v\). If none of the above conditions occur, the pair is processed by the sketch using the UpdateSketch procedure, shown as Algorithm 6.