Database Paper Browser

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
3258
Venue
SIGMOD
Year
2001
Pagerank
0.00044753012
Overall Rank
126 | 99.13%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 32 of 82 citing papers.

Rank Citing Paper Year Venue Pagerank
6,474 Sampling Based Algorithms for Quantile Computation in Sensor Networks 2011 SIGMOD 5.0422176e-05
6,600 Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory 2024 SIGMOD 4.9925547e-05
6,717 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS 4.9459755e-05
6,791 On-Off Sketch: A Fast and Accurate Sketch on Persistence 2021 VLDB 4.9204179e-05
7,181 Spatially-Decaying Aggregation Over a Network: Model and Algorithms 2004 SIGMOD 4.8030491e-05
7,268 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 4.7769096e-05
7,340 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7526052e-05
7,514 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7135369e-05
7,533 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7134753e-05
7,697 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6701245e-05
7,839 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 4.6338068e-05
8,066 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 4.5899218e-05
8,133 Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald 2024 PODS 4.5740737e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5552628e-05
8,376 Adaptive Sampling for Geometric Problems over Data Streams 2004 PODS 4.5277777e-05
8,669 CoopStore: Optimizing Precomputed Summaries for Aggregation 2020 VLDB 4.4667395e-05
9,041 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 4.3997447e-05
9,162 Estimating Quantiles from the Union of Historical and Streaming Data 2017 VLDB 4.380727e-05
9,230 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 4.3650857e-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
9,471 DimBoost: Boosting Gradient Boosting Decision Tree to Higher Dimensions 2018 SIGMOD 4.3300949e-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
10,514 SuSe: Summary Selection for Regular Expression Subsequence Aggregation over Streams 2025 SIGMOD 4.1905499e-05
10,616 Approximation-First Timeseries Query At Scale 2025 VLDB 4.1905499e-05
11,172 Applications of Sketching and Pathways to Impact 2023 PODS 4.1905499e-05
11,373 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.1905499e-05
11,509 Approximating Median Absolute Deviation with Bounded Error 2021 VLDB 4.1905499e-05
11,909 Compact Summaries over Large Datasets 2015 PODS 4.1905499e-05
12,603 StreamMiner: A Classifier Ensemble-based Engine to Mine Concept-drifting Data Streams 2004 VLDB 4.1905499e-05
Previous Page 2 / 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
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
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
446 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00023002059
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
398 Mergeable Summaries 2012 PODS 0.00024383201
9,244 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3648789e-05
2,952 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8230109e-05
8,133 Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald 2024 PODS 4.5740737e-05
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
4,969 Relative Error Streaming Quantiles 2021 PODS 5.790405e-05
446 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00023002059
7,514 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 4.7135369e-05
5,954 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2542261e-05