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: 3257
Venue: SIGMOD
Year: 2001
Pagerank: 0.00044744986
Overall Rank: 126 | 99.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Michael Greenwald
2. Sanjeev Khanna

Incoming Citations (Sorted by Pagerank)

Showing 32 of 82 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
6,716	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	4.9507254e-05
6,790	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	4.9251439e-05
7,180	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	4.807579e-05
7,271	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	4.7813404e-05
7,358	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7529363e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
7,534	Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams	2022	VLDB	4.7180004e-05
7,699	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	4.6746076e-05
7,834	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	4.6382551e-05
8,062	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5943269e-05
8,130	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	4.5784634e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
8,377	Adaptive Sampling for Geometric Problems over Data Streams	2004	PODS	4.5321044e-05
8,673	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	4.4709116e-05
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.4039656e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
9,227	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3692732e-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
9,469	DimBoost: Boosting Gradient Boosting Decision Tree to Higher Dimensions	2018	SIGMOD	4.3342363e-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
10,505	SuSe: Summary Selection for Regular Expression Subsequence Aggregation over Streams	2025	SIGMOD	4.1945683e-05
10,608	Approximation-First Timeseries Query At Scale	2025	VLDB	4.1945683e-05
11,169	Applications of Sketching and Pathways to Impact	2023	PODS	4.1945683e-05
11,371	Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments	2022	VLDB	4.1945683e-05
11,505	Approximating Median Absolute Deviation with Bounded Error	2021	VLDB	4.1945683e-05
11,901	Compact Summaries over Large Datasets	2015	PODS	4.1945683e-05
12,594	StreamMiner: A Classifier Ensemble-based Engine to Mine Concept-drifting Data Streams	2004	VLDB	4.1945683e-05

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
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
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
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
8,130	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS	4.5784634e-05
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05