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: 4781
Venue: SIGMOD
Year: 2013
Pagerank: 7.1442477e-05
Overall Rank: 3,765 | 74.17%
DOI: 10.1145/2463676.2465312

Incoming Non-self Citations Over Time

Authors

1. Lu Wang (Hong Kong University of Science and Technology)
2. Ge Luo (Hong Kong University of Science and Technology)
3. Ke Yi (Hong Kong University of Science and Technology; Tsinghua University)
4. Graham Cormode (AT&T)

BibTeX Citation

@inproceedings{wang_sigmod13,
        title = {{Quantiles over Data Streams: An Experimental Study}},
        author = {Wang, Lu and Luo, Ge and Yi, Ke and Cormode, Graham},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465312},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465312},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,747	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	8.1711208e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB	5.6072422e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
8,918	Pontus: Finding Waves in Data Streams	2023	SIGMOD	5.3483178e-05
9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	5.289545e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
451	Mergeable Summaries	2012	PODS	0.00018151445
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
5,216	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.3121293e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS
2	5,604	Approximate Quantiles and the Order of the Stream	2006	PODS
3	7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
4	842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB
5	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
6	783	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB
7	4,472	Relative Error Streaming Quantiles	2021	PODS
8	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
9	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
10	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB