Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets

Summary: Space-efficient online quantile estimation without input length, via non-uniform random sampling, extending the single-pass framework for approximate order statistics. Lightweight extreme-quantile estimator uses less space than general methods, showing sampling's edge for tail quantiles. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h069bbbc208c8028a
Venue: SIGMOD
Year: 1999
Pagerank: 0.00018182341
Overall Rank: 442 | 97.04%
DOI: 10.1145/304182.304204

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{manku_sigmod99,
        title = {{Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets}},
        author = {Manku, Gurmeet Singh and Rajagopalan, Sridhar and Lindsay, Bruce G.},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304204},
        url = {https://dl.acm.org/doi/10.1145/304182.304204},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016236872
682	StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time	2002	VLDB	0.00014783422
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013498392
1,418	Estimating PageRank on Graph Streams	2008	PODS	0.00010705931
2,615	PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce	2009	VLDB	8.2019215e-05
2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0599809e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
4,279	Relative Error Streaming Quantiles	2021	PODS	6.6731371e-05
4,322	The Adversarial Robustness of Sampling	2020	PODS	6.6514924e-05
4,330	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.6454689e-05
4,744	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.4278327e-05
4,975	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.3194701e-05
5,336	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1613661e-05
5,712	Approximate Quantiles and the Order of the Stream	2006	PODS	6.0096683e-05
7,415	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5160692e-05
8,129	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3739121e-05
8,603	Adaptive Sampling for Geometric Problems over Data Streams	2004	PODS	5.2904511e-05
8,837	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2523304e-05
9,481	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	5.1569355e-05
9,574	Controlled Intentional Degradation in Analytical Video Systems	2022	SIGMOD	5.1428165e-05
9,603	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	5.1376962e-05
9,839	Randomized Sketches for Quantile in LSM-tree based Store	2025	SIGMOD	5.1064323e-05
10,403	Near-Optimal Per-Key Streaming Quantile Estimation	2027	SIGMOD	4.9605343e-05
10,746	Quantile Estimation with Duplicates	2026	SIGMOD	4.9605343e-05
11,928	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023948467
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023058622
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016918797
785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.0001399349

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	175	Simple Random Sampling from Relational Databases	1986	VLDB
2	3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
3	2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
4	785	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB
5	8,129	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD
6	861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB
7	4,279	Relative Error Streaming Quantiles	2021	PODS
8	9,603	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
9	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
10	252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD