# On Frequency Estimation and Detection of Heavy Hitters in Data Streams  
[PERSON]  
Department of Engineering for Innovation, University of Salento, 73100 Lecce, Italy; [EMAIL_ADDRESS] (F.V.); [EMAIL_ADDRESS] (M.P.)  
[PERSON]  
Correspondence: [EMAIL_ADDRESS] (M.C.); [EMAIL_ADDRESS] (I.E.)  
[PERSON]  
The  
the stream. Similarly, frequent items can be informally defined as those items in the stream whose frequency exceeds a user's defined support threshold.  
Mining frequent items is also referred to in the literature as market basket analysis [1], hot list analysis [2] and iceberg query [3; 4].  
Determining frequent items in a stream is a problem important both from a theoretical perspective and for its many practical applications; a few examples follows: (i) Popular products--the stream may be the page views of products on the web site of an online retailer; frequent items are then the most frequently viewed products; (ii) popular search queries--the stream may consist of all of the searches on a search engine; frequent items are then the searches made most often; (iii) TCP flows--the stream may consist of the data packets passing through a network switch, each annotated with a source-destination pair of IP addresses, and the frequent items are then the flows that are sending the most traffic.  
Additional applications include, for instance, analysis of web logs [5], Computational and theoretical Linguistics [6] and the analysis of network traffic [7; 8; 9].  
In this paper we are concerned with the problems of frequency estimation and frequent item detection in data streams. In particular, we tackle these problems designing and analyzing ACMSS, a novel algorithm solving both problems. We compare our algorithm to ASketch[10], the state of the art algorithm for these problems and, through extensive experimental results, we show that ACMSS achieves better accuracy than ASketch for the problem of frequency estimation.  
The design features leading to the improved accuracy are (i) the use of a sketch based on a space optimized version of the CMSS sketch [11], (ii) a different sketch update policy called conservative update [12; 13] which is not used neither in CMSS nor in ASketch and (iii) a different swap policy to determine which items must be moved from the filter data structure to the sketch. Moreover, we prove that our algorithm is able to retrieve with high probability all of the frequent items, owing to the specific design of our sketch data structure, whilst ASketch may not be able in all of the cases to retrieve all of the frequent items.  
Our ACMSS algorithm exhibits a tradeoff between accuracy and speed. Indeed, the experimental results show that ACMSS provides better accuracy than ASketch but at the expense of being slightly slower. However, in different application fields it is preferable being more accurate (albeit a little slower) rather than being faster. Here we recall two different application fields in which accuracy is a strict requirement: Healthcare and security. In healthcare applications [14] accuracy is of paramount importance; in mission critical applications the human life may be at risk. Regarding security, anomaly detection [15; 16] is one of the most studied topics. Accurately determining the so-called outliers is crucial for many applications e.g., DDoS (Distributed Denial of Service) [17].  
The rest of this paper is organized as follows. Section 2 introduces preliminary definition and notation, and formally defines the problems of frequency estimation and frequent item detection in data streams. Section 3 recalls related work. ASketch is introduced in Section 4. We present ACMSS in Section 5. Experimental results are discussed in Section 6. We draw our conclusions in Section 7.