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

arXiv: https://arxiv.org/abs/2112.03462 · HTML: https://mlsanity.com/paper/2112.03462/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2021.

## Built on by (most cited first, 2 of 2)

- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Luxical: High-Speed Lexical-Dense Text Embeddings](https://mlsanity.com/paper/2512.09015/) (2025)

## Abstract (arXiv)

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 then 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 analysis and experiments clearly demonstrate that SpaceSaving^± provides more accurate estimations using the same space as the state of the art protocols for applications with up to 93% of items deleted. Moreover, motivated by prior work, we propose Dyadic SpaceSaving^±, the first deterministic quantile approximation sketch in the bounded deletion model.