KLL± Approximate Quantile Sketches over Dynamic Datasets

Summary: Introduces KLL±, the first quantile sketch for dynamic data under a bounded deletion model, supporting inserts and deletes with small overhead. Space O((α^(1/5)/ε) log^2 log(1/(εδ))); experiments show accuracy comparable to KLL with minimal space. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12312
Venue: VLDB
Year: 2021
Pagerank: 5.403782e-05
Overall Rank: 5,627 | 60.86%
DOI: 10.14778/3450980.3450990

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,567	Optimizing Data Pipelines for Machine Learning in Feature Stores	2023	VLDB	5.4305348e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
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,388	Randomized Sketches for Quantile in LSM-tree based Store	2025	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
11,250	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1945683e-05
11,371	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
402	Mergeable Summaries	2012	PODS	0.00024196343
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6584217e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
10,388	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1945683e-05
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
8,130	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	4.5784634e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05