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: h7de133317627d155
Venue: VLDB
Year: 2022
Pagerank: 5.4754508e-05
Overall Rank: 7,697 | 48.26%
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 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,477	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.3332727e-05
9,509	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1707704e-05
10,674	Quantile Estimation with Duplicates	2026	SIGMOD	4.9793485e-05
10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9793485e-05
10,909	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9793485e-05
11,538	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9793485e-05
13,693	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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023050233
456	Mergeable Summaries	2012	PODS	0.0001791284
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010016656
2,930	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8415815e-05
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
3,175	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.5673688e-05
3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.104636e-05
5,045	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3001279e-05
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7458578e-05

Semantically Similar Papers

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