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.8230109e-05
Overall Rank: 2,952 | 79.49%
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
694	BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics	2020	VLDB	0.00018031141
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956
2,918	DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees	2019	VLDB	7.9043213e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,220	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.3590708e-05
3,557	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9711051e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05
4,246	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.318484e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
5,602	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4153555e-05
5,954	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2542261e-05
6,474	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0422176e-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
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1905499e-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.00072660894
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
846	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00015949293
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021046587
4,024	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5177066e-05
9,244	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3648789e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
5,954	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2542261e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.380727e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05