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: h43600334a8835ae5
Venue: VLDB
Year: 2002
Pagerank: 0.00013374869
Overall Rank: 861 | 94.24%
DOI: 10.1016/B978-155860869-6/50047-0

Incoming Non-self Citations Over Time

Authors

1. Anna C. Gilbert (AT&T)
2. Yannis Kotidis (AT&T)
3. S. Muthukrishnan (AT&T)
4. Martin J. Strauss (AT&T)

BibTeX Citation

@article{gilbert_vldb02,
        title = {{How to Summarize the Universe: Dynamic Maintenance of Quantiles}},
        author = {Gilbert, Anna C. and Kotidis, Yannis and Muthukrishnan, S. and Strauss, Martin J.},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50047-0},
        url = {https://doi.org/10.1016/B978-155860869-6/50047-0},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
452	Mergeable Summaries	2012	PODS	0.00018032092
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
911	Finding Frequent Items in Data Streams	2008	VLDB	0.00013093314
1,290	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011151196
1,329	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011013041
1,903	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.383454e-05
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
2,667	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1324472e-05
3,091	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6394636e-05
3,284	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.4455194e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
3,765	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0178846e-05
3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.900511e-05
4,498	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5590284e-05
4,744	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.4278327e-05
5,666	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0281748e-05
5,712	Approximate Quantiles and the Order of the Stream	2006	PODS	6.0096683e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05
7,030	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.6006602e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05
7,935	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4071076e-05
8,129	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3739121e-05
9,402	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.1672232e-05
9,935	Approximate Sketches	2024	SIGMOD	5.0941477e-05
10,032	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.080531e-05
13,029	PADS: An End-to-end System for Processing Ad Hoc Data	2006	SIGMOD	4.9605343e-05
13,062	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.9605343e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
622	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015452634
785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.0001399349

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD
2	3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
3	2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
4	4,744	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
5	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
6	7,459	Efficient Computation of Quantiles over Joins	2023	PODS
7	9,481	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
8	8,129	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
9	442	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD
10	9,603	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD