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

Summary: A deterministic, distribution-oblivious one-pass algorithm estimates disk-resident quantiles with strong lower/upper bounds and no prior data knowledge. It scales in parallel, while each additional quantile costs only constant extra time and memory. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8626
Venue: VLDB
Year: 1997
Pagerank: 0.00014076306
Overall Rank: 783 | 94.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Khaled Alsabti (Syracuse University)
2. Sanjay Ranka (University of Florida)
3. Vineet Singh (Hitachi)

BibTeX Citation

@article{alsabti_vldb97,
        title = {{A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data}},
        author = {Alsabti, Khaled and Ranka, Sanjay and Singh, Vineet},
        journal = {PVLDB},
        series = {{VLDB} '97},
        volume = {23},
        pages = {346--355},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016635191
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
2,587	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.3747444e-05
7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.5181056e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019869565
606	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015804851

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,318	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
2	9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD
3	842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB
4	4,472	Relative Error Streaming Quantiles	2021	PODS
5	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
6	9,386	Determining Exact Quantiles with Randomized Summaries	2024	SIGMOD
7	443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD
8	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
9	3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
10	261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD