  In this paper, we present an advanced analysis of near optimal deterministic
algorithms using a small space budget to solve the frequency estimation, heavy
hitters, frequent items, and top-k approximation in the bounded deletion model.
We define the family of SpaceSaving$\pm$ algorithms and explain why the
original SpaceSaving$\pm$ algorithm only works when insertions and deletions
are not interleaved. Next, we introduce the new DoubleSpaceSaving$\pm$ and the
IntegratedSpaceSaving$\pm$ and prove their correctness. They show similar
characteristics and both extend the popular space-efficient SpaceSaving
algorithm. However, these two algorithms represent different trade-offs, in
which DoubleSpaceSaving$\pm$ distributes the operations to two independent
summaries while Integrated-SpaceSaving$\pm$ fully synchronizes deletions with
insertions. Since data streams are often skewed, we present an improved
analysis of these two algorithms and show that errors do not depend on the hot
items and are only dependent on the cold and warm items. We also demonstrate
how to achieve the relative error guarantee under mild assumptions. Moreover,
we establish that the important mergeability property exists on these two
algorithms which is desirable in distributed settings.
