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

Summary: Deterministic frequency estimation and frequent-item algorithms for bounded-deletion; space lower bound and optimal SpaceSaving±. Efficient updates yield low latency, high recall/precision; Dyadic SpaceSaving± is the first deterministic quantile sketch in this model. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12631
Venue: VLDB
Year: 2022
Pagerank: 4.5596344e-05
Overall Rank: 8,203 | 42.94%
DOI: 10.14778/3514061.3514068

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.4039656e-05
9,227	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3692732e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
13,176	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 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
402	Mergeable Summaries	2012	PODS	0.00024196343
597	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019475592
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
3,271	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2968732e-05
3,399	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.1408089e-05
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
7,496	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS	4.7180617e-05
2,759	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1636123e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
11,978	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD	4.1945683e-05
7,504	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	4.7180617e-05
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
13,176	Errata for "SpaceSaving+-: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"	2024	VLDB	-