DBScholar

Back to papers

Space-Efficient Online Computation of Quantile Summaries

Summary: Online algorithm for epsilon-approximate quantile summaries on streaming data, with worst-case space O((1/epsilon) log(epsilon N)). Improves upon O((1/epsilon) log^2(epsilon N); requires no a priori knowledge of N; experiments show space tighter than both worst-case and prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
he58d6882a0656c1b
Venue
SIGMOD
Year
2001
Pagerank
0.00035962466
Overall Rank
83 | 99.45%
DOI
10.1145/375663.375670

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{greenwald_sigmod01,
        title = {{Space-Efficient Online Computation of Quantile Summaries}},
        author = {Greenwald, Michael and Khanna, Sanjeev},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375670},
        url = {https://dl.acm.org/doi/10.1145/375663.375670},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 86 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030586757
312 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.0002130211
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
456 Mergeable Summaries 2012 PODS 0.00017904764
541 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00016663833
679 StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time 2002 VLDB 0.00014831743
710 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00014603777
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
843 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00013534623
863 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013390792
911 Finding Frequent Items in Data Streams 2008 VLDB 0.0001312057
1,067 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012187242
1,285 SQL/MapReduce: A practical approach to self-describing, polymorphic, and parallelizable user-defined functions 2009 VLDB 0.0001119616
1,308 Automating Large-Scale Data Quality Verification 2018 VLDB 0.00011073863
1,415 Estimating PageRank on Graph Streams 2008 PODS 0.00010732327
1,431 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010676907
1,533 On Multi-Column Foreign Key Discovery 2010 VLDB 0.00010328081
2,010 VF2Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning 2021 SIGMOD 9.1945893e-05
2,210 Multi-Dimensional Regression Analysis of Time-Series Data Streams 2002 VLDB 8.8340718e-05
2,221 Optimal Sampling From Distributed Streams 2010 PODS 8.8114999e-05
2,434 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.4726771e-05
2,465 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.4213787e-05
2,690 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.1226926e-05
2,738 Sketching Probabilistic Data Streams 2007 SIGMOD 8.0692701e-05
2,750 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 8.0569441e-05
2,799 Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries 2018 VLDB 7.9895512e-05
3,039 Estimating Statistical Aggregates on Probabilistic Data Streams 2007 PODS 7.723493e-05
3,096 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6497893e-05
3,286 Camel: Managing Data for Efficient Stream Learning 2022 SIGMOD 7.4524975e-05
3,514 Sketching Linear Classifiers over Data Streams 2018 SIGMOD 7.2395322e-05
3,607 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.1645803e-05
3,681 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 7.1012729e-05
3,873 SketchML: Accelerating Distributed Machine Learning with Data Sketches 2018 SIGMOD 6.9507449e-05
3,918 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.9234041e-05
3,945 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 6.9072302e-05
4,099 Fast Data Stream Algorithms using Associative Memories 2007 SIGMOD 6.8061151e-05
4,306 The Adversarial Robustness of Sampling 2020 PODS 6.6735594e-05
4,377 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6269629e-05
4,566 Relative Error Streaming Quantiles 2021 PODS 6.5286509e-05
5,047 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.2972183e-05
5,048 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.2971455e-05
5,073 Randomized Multi-pass Streaming Skyline Algorithms 2009 VLDB 6.2860705e-05
5,325 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1799938e-05
5,326 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 6.1794406e-05
5,332 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.1754712e-05
5,701 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0289493e-05
5,724 An Experimental Evaluation of Large Scale GBDT Systems 2019 VLDB 6.0150027e-05
6,192 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8540507e-05
6,222 Materialization and Reuse Optimizations for Production Data Science Pipelines 2022 SIGMOD 5.8446676e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023047482
450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018025134
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016938992
785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00013999898
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 456 Mergeable Summaries 2012 PODS
2 9,578 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD
3 2,750 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS
4 7,242 Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald 2024 PODS
5 253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD
6 710 Approximate Counts and Quantiles over Sliding Windows 2004 PODS
7 4,566 Relative Error Streaming Quantiles 2021 PODS
8 450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD
9 8,111 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD
10 5,326 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS