DBScholar

Back to papers

Approximate Medians and other Quantiles in One Pass and with Limited Memory

Summary: One-pass, memory footprint an order of magnitude smaller than prior work, approximate quantile algorithms with explicit guarantees for any distribution and arrival order. Integrates sampling to further shrink memory, delivering probabilistic guarantees at a user-specified confidence; theory, algorithms, and simulations across datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hdf9f1f6307994692
Venue
SIGMOD
Year
1998
Pagerank
0.00023050233
Overall Rank
252 | 98.31%
DOI
10.1145/276304.276342

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{manku_sigmod98,
        title = {{Approximate Medians and other Quantiles in One Pass and with Limited Memory}},
        author = {Manku, Gurmeet Singh and Rajagopalan, Sridhar and Lindsay, Bruce G.},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276342},
        url = {https://dl.acm.org/doi/10.1145/276304.276342},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057568153
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052121228
83 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00035978046
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018032912
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017962189
456 Mergeable Summaries 2012 PODS 0.0001791284
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016295476
710 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00014608975
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012594522
1,111 A Transducer-Based XML Query Processor 2002 VLDB 0.00011984202
1,769 Improving the Performance of List Intersection 2009 VLDB 9.6869284e-05
2,465 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.4253671e-05
2,558 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.3007355e-05
2,688 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.1265396e-05
3,094 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6533343e-05
3,613 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.162283e-05
3,678 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 7.104636e-05
4,097 Fast Data Stream Algorithms using Associative Memories 2007 SIGMOD 6.8092798e-05
4,564 Relative Error Streaming Quantiles 2021 PODS 6.5317429e-05
5,045 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.3001279e-05
5,320 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 6.1823673e-05
5,327 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.1783009e-05
5,698 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0317949e-05
7,247 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.5748328e-05
7,435 Efficient Computation of Quantiles over Joins 2023 PODS 5.5283535e-05
7,697 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 5.4754508e-05
7,792 Spatially-Decaying Aggregation Over a Network: Model and Algorithms 2004 SIGMOD 5.4516538e-05
7,816 B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 5.4481832e-05
8,104 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 5.3942942e-05
8,170 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 5.3844369e-05
9,496 Estimating Quantiles from the Union of Historical and Streaming Data 2017 VLDB 5.1708619e-05
9,509 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 5.1707704e-05
9,539 Controlled Intentional Degradation in Analytical Video Systems 2022 SIGMOD 5.1621607e-05
10,840 CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort 2026 VLDB 4.9793485e-05
10,909 Incremental Query Optimizer Statistics in Amazon Redshift 2026 VLDB 4.9793485e-05
11,691 Applications of Sketching and Pathways to Impact 2023 PODS 4.9793485e-05
11,878 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.9793485e-05
13,157 A Data Warehousing Architecture for Enabling Service Provisioning Process 2001 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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.0023947656
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047863192
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00014005637
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,678 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD
2 5,698 Approximate Quantiles and the Order of the Stream 2006 PODS
3 2,750 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS
4 710 Approximate Counts and Quantiles over Sliding Windows 2004 PODS
5 4,564 Relative Error Streaming Quantiles 2021 PODS
6 5,320 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS
7 9,570 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD
8 785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB
9 83 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD
10 450 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD