Approximate Quantiles and the Order of the Stream

Summary: Analyzes i.i.d. samples from an unknown distribution arriving in partially non‑adversarial order and shows that exploiting order yields provably stronger streaming quantile algorithms. Constructs sublinear‑space, consistent quantile estimators that improve accuracy as sample size grows, resolving open questions on order's impact. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1399
Venue: PODS
Year: 2006
Pagerank: 6.5121141e-05
Overall Rank: 4,031 | 71.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sudipto Guha
2. Andrew McGregor

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
595	Estimating PageRank on Graph Streams	2008	PODS	0.00019507721
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
115	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046221215
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
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022221803
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
3,330	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.2150831e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05