Quantiles over Data Streams: An Experimental Study

Summary: Taxonomy and efficient online implementations of streaming quantile algorithms for describing data distributions via quantiles. Introduces novel, previously unstudied variations that improve space–time–accuracy tradeoffs and provides thorough experimental comparisons of methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4719
Venue: SIGMOD
Year: 2013
Pagerank: 6.4680854e-05
Overall Rank: 4,076 | 71.65%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,953	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8267643e-05
4,172	The Adversarial Robustness of Sampling	2020	PODS	6.3879072e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
6,790	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	4.9251439e-05
7,401	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB	4.7397228e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
8,749	Pontus: Finding Waves in Data Streams	2023	SIGMOD	4.456315e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
9,227	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3692732e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
402	Mergeable Summaries	2012	PODS	0.00024196343
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
5,457	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	5.4970777e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021044221
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05