# On Frequency Estimation and Detection of Heavy Hitters in Data Streams
## 3 Related Work  
The first algorithm for mining frequent items dates back to 1982, and is due to [PERSON] [18]. Many years later, the Lossy Counting and Sticky Sampling algorithms by [PERSON] et al. [19], were published in 2002. Interestingly, in 2003, the Misra and Gries algorithm was independently rediscovered and its computational complexity improved by [PERSON] et al. [7] and [PERSON] et al. [20]. This algorithm is known in the literature as Frequent. [PERSON] et al. presented a few years later the Space-Saving algorithm [21], which significantly improves the accuracy. These algorithms keep track of frequent items through the use of counters, i.e., data structures managing pair (item, estimated frequency).  
Another group of algorithms is based on a sketch data structure, usually a bi-dimensional array hosting a counter in each cell. Pairwise independent hash functions are used to map stream's items to corresponding cells in the sketch. Sketch-based algorithms include CountSketch by [PERSON] et al. [5], Group Test[22] and Count-Min[23] by [PERSON] and [PERSON], hCount[24] by [PERSON] et al. and CMS[11] by [PERSON] et al.  
Algorithms for Correlated Heavy Hitters (CHHs) have been recently proposed by [PERSON] et al. [25] and by [PERSON] et al [26] in which a fast and more accurate algorithm for mining CHHs is presented.  
All of the previous algorithms give identical importance to each item. However, in many applications is necessary to discount the effect of old data. Indeed, in some situations recent datais more useful and valuable than older data; such cases may be handled using the _sliding window_ model [27; 28] or the time-fading model [29]. The key idea in sliding window is the use of a temporal window to capture fresh, recent items. This window periodically slides forward, allowing detection of only those frequent items falling in the window. In the time-fading model recent items are considered more important than older ones by _fading_ the frequency count of older items. Among the algorithms for mining time-faded frequent items we recall \(\lambda\)-HCount[30] by [PERSON] and [PERSON], FSSQ (Filtered Space-Saving with Quasi-heap) [31] by [PERSON] et al. and the FDCMSS algorithm [32; 33] by [PERSON] et al.  
Regarding parallel algorithms, [PERSON] et al. [34; 35; 36] provide parallel versions of the Frequent and Space-Saving algorithms for message-passing architectures. Shared-memory versions of Lossy Counting and Frequent have been designed by [PERSON] et al. [37; 38], and parallel versions of Space-Saving have been proposed by [PERSON] et al. [39], [PERSON] et al. [40], and [PERSON] et al. [41]. Accelerator based algorithms include [PERSON] et al. [42], [PERSON] and [PERSON] [43] and [PERSON] et al. [41; 44]. [PERSON] et al. [45] present a message-passing based version of the CHHs algorithm [26]; a parallel message-passing based version of [32] is presented in [46].  
Distributed mining of heavy hitters include algorithms such as [47; 48; 49; 50; 51]. In the context of unstructured P2P networks, gossip-based algorithms have been proposed for mining frequent items including [52; 53; 54; 55].