Competitive analysis of maintaining frequent items of a stream

Giannakopoulos Y, Koutsoupias E (2015)

Publication Type: Journal article

Publication year: 2015

Journal

Theoretical Computer Science Elsevier

Book Volume: 562

Pages Range: 23-32

Journal Issue: C

DOI: 10.1016/j.tcs.2014.09.011

Open Access Link: https://yiannisgiannakopoulos.com/files/papers/FrequentItemsJournal.pdf

Abstract

We study the classic frequent items problem in data streams, but 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 Θ√N and Θ3√ 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.

Authors with CRIS profile

Ioannis Giannakopoulos

Involved external institutions

University of Oxford GB United Kingdom (GB)

How to cite

APA:

Giannakopoulos, Y., & Koutsoupias, E. (2015). Competitive analysis of maintaining frequent items of a stream. Theoretical Computer Science, 562(C), 23-32. https://dx.doi.org/10.1016/j.tcs.2014.09.011

MLA:

Giannakopoulos, Yiannis, and Elias Koutsoupias. "Competitive analysis of maintaining frequent items of a stream." Theoretical Computer Science 562.C (2015): 23-32.

BibTeX: Download