SpaceSaving${}^{\pm }$: An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model

Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi +1

In this paper, we propose the first deterministic algorithms to solve the frequency estimation and frequent item problems in the bounded deletion model. We establish the space lowe…