@incollection{gk2012,
Abstract = {We study the well-known frequent items problem in data streams from a competitive analysis point of view. We consider the standard worst-case input model, as well as a weaker distributional adversarial setting. We are primarily interested in the single-slot memory case and for both models we give (asymptotically) tight bounds of $\varTheta(\sqrt{N})$ and $\varTheta(\sqrt[3]{N})$ respectively, achieved by very simple and natural algorithms, where N is the stream's length. We also provide lower bounds, for both models, in the more general case of arbitrary memory sizes of $k\geq 1$. },
Author = {Giannakopoulos, Yiannis and Koutsoupias, Elias},
year={2012},
isbn={978-3-642-31154-3},
booktitle={Algorithm Theory – SWAT 2012},
volume={7357},
series={Lecture Notes in Computer Science},
editor={Fomin, Fedor V. and Kaski, Petteri},
title={Competitive Analysis of Maintaining Frequent Items of a Stream},
url={http://dx.doi.org/10.1007/978-3-642-31155-0_30},
publisher={Springer Berlin Heidelberg},
doi = "10.1007/978-3-642-31155-0_30",
pages={340-351}}