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: 9057
Venue: VLDB
Year: 2002
Pagerank: 0.00013671191
Overall Rank: 842 | 94.23%
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
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
451	Mergeable Summaries	2012	PODS	0.00018151445
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,263	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011425419
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
2,698	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.2450522e-05
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.6439415e-05
3,703	Approximation Techniques for Spatial Data	2004	SIGMOD	7.1829776e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
5,516	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.1895841e-05
5,604	Approximate Quantiles and the Order of the Stream	2006	PODS	6.1533846e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.5521918e-05
7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.5181056e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
9,188	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.3058708e-05
9,724	Approximate Sketches	2024	SIGMOD	5.2308295e-05
9,825	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.2143223e-05
12,691	PADS: An End-to-end System for Processing Ad Hoc Data	2006	SIGMOD	5.093636e-05
12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	5.093636e-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.00036378991
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
606	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015804851
783	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00014076306

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,472	Relative Error Streaming Quantiles	2021	PODS
2	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
3	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
4	5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
5	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
6	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
7	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
8	7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
9	443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD
10	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD