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: h0dcd84962de15a4f
Venue: VLDB
Year: 1997
Pagerank: 0.00014005637
Overall Rank: 785 | 94.73%
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 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023050233
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
450	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018032912
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016295476
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
2,631	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.1996438e-05
8,104	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3942942e-05
10,840	CrocSort: Resource-Efficient, Skew-Resilient Parallel External Merge Sort	2026	VLDB	4.9793485e-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
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
385	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.0001946565
620	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015502611

Semantically Similar Papers

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