Database Paper Browser

Back to papers

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
3105
Venue
SIGMOD
Year
1999
Pagerank
0.00023002059
Overall Rank
446 | 96.91%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank Citing Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044753012
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026698826
589 Estimating PageRank on Graph Streams 2008 PODS 0.00019569121
617 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00019048986
783 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00016648503
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
2,636 PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce 2009 VLDB 8.401513e-05
2,952 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8230109e-05
4,024 Approximate Quantiles and the Order of the Stream 2006 PODS 6.5177066e-05
4,080 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4619407e-05
4,170 The Adversarial Robustness of Sampling 2020 PODS 6.381766e-05
4,347 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2588401e-05
4,969 Relative Error Streaming Quantiles 2021 PODS 5.790405e-05
5,465 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.491937e-05
5,636 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.3985928e-05
5,954 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2542261e-05
7,514 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7135369e-05
8,066 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 4.5899218e-05
8,376 Adaptive Sampling for Geometric Problems over Data Streams 2004 PODS 4.5277777e-05
9,162 Estimating Quantiles from the Union of Historical and Streaming Data 2017 VLDB 4.380727e-05
9,244 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3648789e-05
9,301 Controlled Intentional Degradation in Analytical Video Systems 2022 SIGMOD 4.3558097e-05
10,113 SplineSketch: Even More Accurate Quantiles with Error Guarantees 2026 SIGMOD 4.1905499e-05
10,198 Quantile Estimation with Duplicates 2026 SIGMOD 4.1905499e-05
10,399 Randomized Sketches for Quantile in LSM-tree based Store 2025 SIGMOD 4.1905499e-05
11,373 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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.0040465394
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021046587
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00071588702
2,952 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8230109e-05
4,080 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4619407e-05
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021046587
7,514 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7135369e-05
955 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015069776
4,969 Relative Error Streaming Quantiles 2021 PODS 5.790405e-05
9,244 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3648789e-05
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044753012
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266