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: 12632
Venue: VLDB
Year: 2022
Pagerank: 4.5552628e-05
Overall Rank: 8,203 | 42.99%
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.3997447e-05
9,230	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3650857e-05
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1905499e-05
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1905499e-05
13,190	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.00044753012
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
398	Mergeable Summaries	2012	PODS	0.00024383201
598	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019431661
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
1,117	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001386123
1,744	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010694459
3,273	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2899198e-05
3,401	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.1343786e-05
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05
5,636	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.3985928e-05
6,347	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.0969206e-05
6,415	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.064828e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1905499e-05
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
7,495	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS	4.7135369e-05
2,766	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1559016e-05
5,636	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.3985928e-05
11,986	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD	4.1905499e-05
7,503	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	4.7135369e-05
1,744	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010694459
13,190	Errata for "SpaceSaving+-: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"	2024	VLDB	-