SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model

Summary: First deterministic frequency-estimation and frequent-item algorithms for bounded deletions, with matching space lower bounds via Lazy SpaceSaving± and optimal SpaceSaving±. Also introduces Dyadic SpaceSaving±, the first deterministic quantile sketch for this model. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12819
Venue: VLDB
Year: 2022
Pagerank: 5.4853605e-05
Overall Rank: 8,106 | 44.39%
DOI: 10.14778/3514061.3514068

Incoming Non-self Citations Over Time

Authors

1. Fuheng Zhao (University of California Santa Barbara)
2. Divyakant Agrawal (University of California Santa Barbara)
3. Amr El Abbadi (University of California Santa Barbara)
4. Ahmed Metwally (Uber)

BibTeX Citation

@article{zhao_vldb22,
        title = {{SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model}},
        author = {Zhao, Fuheng and Agrawal, Divyakant and Abbadi, Amr El and Metwally, Ahmed},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {6},
        pages = {1215--1227},
        doi = {10.14778/3514061.3514068},
        url = {https://doi.org/10.14778/3514061.3514068},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,310	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.4556836e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05
10,487	Quantile Estimation with Duplicates	2026	SIGMOD	5.093636e-05
11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	5.093636e-05
13,379	Errata for "SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"	2024	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
451	Mergeable Summaries	2012	PODS	0.00018151445
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.0058242e-05
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
3,121	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.7357038e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05
6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.8746921e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	885	Finding Frequent Items in Data Streams	2008	VLDB
2	5,669	Data Streams with Bounded Deletions	2018	PODS
3	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
4	7,918	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS
5	2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS
6	5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
7	12,176	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
8	7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS
9	1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
10	13,379	Errata for "SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"	2024	VLDB