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.6006602e-05
Overall Rank: 7,030 | 52.88%
DOI: 10.14778/3514061.3514068
PDF: Download (CC BY-NC-ND 4.0)

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 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,499	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	5.3131213e-05
8,574	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.297131e-05
10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD	4.9605343e-05
10,746	Quantile Estimation with Duplicates	2026	SIGMOD	4.9605343e-05
10,911	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9605343e-05
10,979	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9605343e-05
11,593	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9605343e-05
13,738	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.00036097627
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023058622
452	Mergeable Summaries	2012	PODS	0.00018032092
591	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015853273
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013752994
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013374869
911	Finding Frequent Items in Data Streams	2008	VLDB	0.00013093314
1,639	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	9.9845484e-05
2,938	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8224388e-05
3,091	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6394636e-05
3,181	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.5427645e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
4,744	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.4278327e-05
5,761	Data Streams with Bounded Deletions	2018	PODS	5.9847577e-05
6,399	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7818043e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7279868e-05

Semantically Similar Papers

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