Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams

Summary: First deterministic one-pass algorithms for biased quantiles on data streams, providing skew-aware accuracy (more precise at extremes) with near-optimal sublinear space. Amortized updates are near-constant, practical and empirically use less space and are fast to maintain. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1398
Venue: PODS
Year: 2006
Pagerank: 7.8239173e-05
Overall Rank: 2,955 | 79.45%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
696	BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics	2020	VLDB	0.00018048935
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565
2,914	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9118579e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
3,313	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.2381634e-05
3,566	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9629443e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
5,594	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4192122e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-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
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited 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
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021044221
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-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
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05