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: 12313
Venue: VLDB
Year: 2021
Pagerank: 5.3985928e-05
Overall Rank: 5,636 | 60.84%
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,575	Optimizing Data Pipelines for Machine Learning in Feature Stores	2023	VLDB	5.4253204e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5552628e-05
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,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	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
11,252	CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited Space	2023	VLDB	4.1905499e-05
11,373	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1905499e-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
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
398	Mergeable Summaries	2012	PODS	0.00024383201
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059
846	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00015949293
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05
3,896	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6526869e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1905499e-05
7,514	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7135369e-05
5,954	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2542261e-05
10,399	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	4.1905499e-05
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1905499e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
8,133	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	4.5740737e-05
9,244	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3648789e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05