How to Summarize the Universe: Dynamic Maintenance of Quantiles

Summary: Dynamic maintenance of quantiles via RSS-based compact summaries for insert/delete workloads. Delivers fast, data-independent quantile estimates to user-specified precision, with deletions supported without rescanning, unlike prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8866
Venue: VLDB
Year: 2002
Pagerank: 0.00015066967
Overall Rank: 956 | 93.36%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
402	Mergeable Summaries	2012	PODS	0.00024196343
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
1,554	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011400581
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
1,941	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	0.00010017745
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
3,102	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5586568e-05
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05
3,543	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9917053e-05
3,544	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	6.9898874e-05
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
4,447	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.1791516e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
5,673	Distributed Set-Expression Cardinality Estimation	2004	VLDB	5.3780919e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05
7,358	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7529363e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
7,699	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	4.6746076e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
9,038	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	4.4039656e-05
9,628	Approximate Sketches	2024	SIGMOD	4.3143499e-05
9,663	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	4.3089103e-05
12,498	PADS: An End-to-end System for Processing Ad Hoc Data	2006	SIGMOD	4.1945683e-05
12,531	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026702512
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021044221
599	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00019394214

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05