  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$^\pm$
and SpaceSaving$^\pm$ algorithms with optimal space bound. We then develop an
efficient implementation of the SpaceSaving$^\pm$ algorithm that minimizes the
latency of update operations using novel data structures. The experimental
evaluations testify that SpaceSaving$^\pm$ 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$^\pm$ 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$^\pm$, the first deterministic quantile approximation sketch in the
bounded deletion model.
