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: 1398
Venue: PODS
Year: 2006
Pagerank: 6.1533846e-05
Overall Rank: 5,604 | 61.56%
DOI: 10.1145/1142351.1142390

Incoming Non-self Citations Over Time

Authors

1. Sudipto Guha (University of Pennsylvania)
2. Andrew McGregor (University of Pennsylvania)

BibTeX Citation

@inproceedings{guha_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Approximate Quantiles and the Order of the Stream}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142390},
        doi = {10.1145/1142351.1142390},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Guha, Sudipto and McGregor, Andrew},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,396	Estimating PageRank on Graph Streams	2008	PODS	0.00010921308
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-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
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
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
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
2,997	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.8745158e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
2	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
3	443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD
4	5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS
5	1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS
6	261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD
7	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
8	6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD
9	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
10	4,472	Relative Error Streaming Quantiles	2021	PODS