# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 2 Preliminary Definitions  
In this Section we briefly recall preliminary definitions and the notation that shall be used throughout the paper. We begin by defining the frequency of weighted items as follows.  
**Definition 1**.: _Given a stream \(\sigma=\{(s_{i},w_{i})\}_{i=1,2,\ldots,n}\) of \(n\) pairs (item, weight) with items drawn from the universe \([m]=\{1,2,\ldots,m\}\) and weights which are positive real values, the frequency of an item \(s\) is \(f_{\sigma}(s)=\sum\limits_{\begin{subarray}{c}i\in[n]\\ s_{i}=s\end{subarray}}w_{i}\)._  
Next, we define the frequency vector.  
**Definition 2**.: _A stream \(\sigma=\{(s_{i},w_{i})\}_{i=1,2,\ldots,n}\), whose items are drawn from the universe \([m]\) and whose weights are positive real values, implicitly defines a frequency vector, \(\mathbf{f}=(f_{1},f_{2},\ldots,f_{m})\), where \(f_{i}=f_{\sigma}(i)\) is the frequency of item \(i\)._  
We can interpret a stream \(\sigma\) as a sequence of updates to the frequency vector \(\mathbf{f}\): Initially \(\mathbf{f}\) is the null vector, then, for each pair \((i,w)\) in the stream, the entry in \(\mathbf{f}\) corresponding to the frequency of the item \(i\) is incremented by the corresponding weight \(w\).  
We are now ready to define the \(\epsilon\)-approximate frequency estimation problem.  
**Definition 3**.: _Given a stream \(\sigma=\{(s_{i},w_{i})\}_{i=1,2,\ldots,n}\) of \(n\) pairs (item, weight) with items drawn from the universe \([m]\) and weights which are positive real values, the frequency vector \(\mathbf{f}\) defined by \(\sigma\), and a value \(0<\epsilon<1\), the \(\epsilon\)-approximate frequency estimation problem consists in computing a vector \(\mathbf{\hat{t}}=(\hat{f}_{1},\hat{f}_{2},\ldots,\hat{f}_{m})\), so that \(\left|\hat{f}_{i}-f_{i}\right|\leq\epsilon\|\mathbf{f}\|_{\ell}\), for each \(i\in[m]\) where \(\ell\) can be either \(1\) or \(2\)._  
Next, we define \(\phi\)-frequent weighted items.  
**Definition 4**.: _Given a stream \(\sigma=\{(s_{i},w_{i})\}_{i=1,2,\ldots,n}\) of \(n\) pairs (item, weight) with items drawn from the universe \([m]\) and weights which are positive real values, and a real value \(0<\phi<1\), the \(\phi\)-frequent items of \(\sigma\) are all those items whose frequency is above \(\phi W\), where \(W=\sum_{i=1}^{n}w_{i}\), i.e., the elements in the set \(F=\{s\in[m]:f_{\sigma}(s)>\phi W\}\)._  
We will often refer to the \(\phi\)-frequent items of a stream simply as frequent items, leaving as implicit the reference to a \(\phi\) value. Frequent items are also commonly referred to as Heavy Hitters. The \(\epsilon\)-approximate frequent items problem related to determining \(\phi\)-frequent weighted items is defined as follows.  
**Definition 5**.: _Given a stream \(\sigma=\{(s_{i},w_{i})\}_{i=1,2,\ldots,n}\) of \(n\) pairs (item, weight) with items drawn from the universe \([m]\) and weights which are positive real values, a real value \(0<\phi<1\) and a value \(0<\epsilon<\phi\), the \(\epsilon\)-approximate frequent items problem consists in finding the set \(F\), so that:_  
1. _[label=_1_., ref=_1_]_
2. \(F\) _contains all of the items_ \(s\) _with frequency_ \(f_{\sigma}(s)>\phi W\) _where_ \(W=\sum_{i=1}^{n}w_{i}\) _(_\(\phi\)_-frequent weighted items);_
3. \(F\) _does not contain any item_ \(s\) _such that_ \(f_{\sigma}(s)\leq(\phi-\epsilon)W\)_._