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.00013396995
Overall Rank: 862 | 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.00022981861
456	Mergeable Summaries	2012	PODS	0.0001791284
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,286	Resource Sharing in Continuous Sliding-Window Aggregates	2004	VLDB	0.0001119284
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
1,970	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.2902522e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
2,664	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1569551e-05
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
3,272	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.4734096e-05
3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.104636e-05
3,758	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0437238e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
4,474	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5838686e-05
5,045	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3001279e-05
5,654	Distributed Set-Expression Cardinality Estimation	2004	VLDB	6.0507163e-05
5,698	Approximate Quantiles and the Order of the Stream	2006	PODS	6.0317949e-05
6,315	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.8161255e-05
7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5418075e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
7,916	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4276156e-05
8,104	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3942942e-05
9,367	OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates	2024	VLDB	5.1868213e-05
9,893	Approximate Sketches	2024	SIGMOD	5.1134687e-05
9,992	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.099523e-05
12,981	PADS: An End-to-end System for Processing Ad Hoc Data	2006	SIGMOD	4.9793485e-05
13,014	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	4.9793485e-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.00035978046
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
620	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015502611
785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00014005637

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,678	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,045	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB
5	83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
6	7,435	Efficient Computation of Quantiles over Joins	2023	PODS
7	9,496	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
8	8,104	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,570	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD