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.00013390792
Overall Rank: 863 | 94.21%
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
255	The History of Histograms (abridged)	2003	VLDB	0.00022974524
456	Mergeable Summaries	2012	PODS	0.00017904764
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013420431
911	Finding Frequent Items in Data Streams	2008	VLDB	0.0001312057
1,286	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.00011188038
1,320	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011040663
1,971	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.2858543e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4213787e-05
2,664	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1532061e-05
3,096	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6497893e-05
3,273	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.469873e-05
3,681	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1012729e-05
3,761	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0403969e-05
3,918	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9234041e-05
4,476	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.580752e-05
5,048	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.2971455e-05
5,655	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0478521e-05
5,701	Approximate Quantiles and the Order of the Stream	2006	PODS	6.0289493e-05
6,318	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.8133722e-05
7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5392867e-05
7,703	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4728588e-05
7,921	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4250462e-05
8,111	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3917406e-05
9,376	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.1843659e-05
9,900	Approximate Sketches	2024	SIGMOD	5.1110481e-05
9,997	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.0971652e-05
12,987	PADS: An End-to-end System for Processing Ad Hoc Data	2006	SIGMOD	4.9769913e-05
13,020	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.9769913e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035962466
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211
620	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015495576
785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00013999898

Semantically Similar Papers

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