Competitive analysis of maintaining frequent items of a stream - Giannakopoulos, Yiannis; Koutsoupias, Elias (Theoretical Computer Science, 2015)
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.
CRIS-Team Scopus Importer:2021-06-11
Keywords: Competitive analysis; Data streams; Frequent items; Online algorithms