SpaceSaving± An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model

Download PDF

Abstract

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 lower bound for solving the deterministic frequent items problem in the bounded deletion model, and propose the Lazy SpaceSaving± and SpaceSaving± algorithms with optimal space bound. We develop an efficient implementation of the SpaceSaving± algorithm that minimizes the latency of update operations using novel data structures. The experimental evaluations testify that SpaceSaving± has accurate frequency estimations and achieves very high recall and precision across different data distributions while using minimal space. Our experiments clearly demonstrate that, if allowed the same space, SpaceSaving± is more accurate than the state-of-the-art protocols with up to 93% of the items deleted. Moreover, motivated by prior work, we propose Dyadic SpaceSaving±, the first deterministic quantile approximation sketch in the bounded-deletion model.