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
3104
Venue
SIGMOD
Year
1999
Pagerank
0.00022996573
Overall Rank
443 | 96.93%
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.00072723062
126 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00044744986
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
344 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00026702512
595 Estimating PageRank on Graph Streams 2008 PODS 0.00019507721
619 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00019066583
785 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00016664156
848 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.0001597308
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
2,630 PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce 2009 VLDB 8.4128091e-05
2,955 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8239173e-05
4,031 Approximate Quantiles and the Order of the Stream 2006 PODS 6.5121141e-05
4,076 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4680854e-05
4,172 The Adversarial Robustness of Sampling 2020 PODS 6.3879072e-05
4,350 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2645054e-05
4,966 Relative Error Streaming Quantiles 2021 PODS 5.7959749e-05
5,457 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.4970777e-05
5,627 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.403782e-05
5,956 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2566971e-05
7,515 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7180617e-05
8,062 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 4.5943269e-05
8,377 Adaptive Sampling for Geometric Problems over Data Streams 2004 PODS 4.5321044e-05
9,162 Estimating Quantiles from the Union of Historical and Streaming Data 2017 VLDB 4.3849295e-05
9,237 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3690661e-05
9,296 Controlled Intentional Degradation in Analytical Video Systems 2022 SIGMOD 4.3599613e-05
10,113 SplineSketch: Even More Accurate Quantiles with Error Guarantees 2026 SIGMOD 4.1945683e-05
10,198 Quantile Estimation with Duplicates 2026 SIGMOD 4.1945683e-05
10,388 Randomized Sketches for Quantile in LSM-tree based Store 2025 SIGMOD 4.1945683e-05
11,371 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.1945683e-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.0040449103
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
275 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029364901
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021044221
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00070894702
4,076 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4680854e-05
2,955 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8239173e-05
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021044221
7,515 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7180617e-05
956 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015066967
4,966 Relative Error Streaming Quantiles 2021 PODS 5.7959749e-05
9,237 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3690661e-05
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