Competitive analysis of maintaining frequent items of a stream
Giannakopoulos Y, Koutsoupias E (2012)
Publication Type: Conference contribution
Publication year: 2012
Journal
Publisher: Springer Berlin Heidelberg
Book Volume: 7357 LNCS
Pages Range: 340-351
Conference Proceedings Title: Algorithm Theory -- SWAT 2012
ISBN: 9783642311543
DOI: 10.1007/978-3-642-31155-0_30
Open Access Link: https://yiannisgiannakopoulos.com/files/papers/FrequentItemsJournal.pdf
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 and 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 ≥ 1. © 2012 Springer-Verlag.
Authors with CRIS profile
Involved external institutions
Greece (GR)How to cite
APA:
Giannakopoulos, Y., & Koutsoupias, E. (2012). Competitive analysis of maintaining frequent items of a stream. In Fomin FV, Kaski P (Eds.), Algorithm Theory -- SWAT 2012 (pp. 340-351). Springer Berlin Heidelberg.
MLA:
Giannakopoulos, Yiannis, and Elias Koutsoupias. "Competitive analysis of maintaining frequent items of a stream." Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 Ed. Fomin FV, Kaski P, Springer Berlin Heidelberg, 2012. 340-351.
BibTeX: Download