A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data

Summary: One-pass, deterministic algorithm for estimating p-quantiles on disk-resident data; yields tight lower/upper bounds without distributional assumptions. Scalable parallel formulation; constant per-quantile overhead after the first, with robust validation on IBM SP-2 across distributions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8435
Venue: VLDB
Year: 1997
Pagerank: 0.00021044221
Overall Rank: 526 | 96.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
619	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00019066583
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
2,702	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.2725214e-05
7,515	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	4.7180617e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
362	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00025770385
599	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00019394214

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
10,113	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	4.1945683e-05
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
9,237	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD	4.3690661e-05
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901