Random Sampling from B+ trees

Summary: Introduces acceptance/rejection algorithms for simple random sampling directly from standard B+ trees, avoiding auxiliary rank metadata and its maintenance overhead. Compares iterative and batch variants against ranked-tree sampling, emphasizing easy DBMS retrofitting. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h68f4f03cbd3b9246
Venue: VLDB
Year: 1989
Pagerank: 0.00017573936
Overall Rank: 480 | 96.79%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Frank Olken (Lawrence Berkeley National Laboratory)
2. Doron Rotem (Lawrence Berkeley National Laboratory)

BibTeX Citation

@article{olken_vldb89,
        title = {{Random Sampling from B+ trees}},
        author = {Olken, Frank and Rotem, Doron},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {269--275},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024275691
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020265363
477	Sampling Large Databases for Association Rules	1996	VLDB	0.00017624579
491	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017383221
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,237	Random Sampling from Hash Files	1990	SIGMOD	0.00011381076
1,469	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010533259
1,647	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	9.9747449e-05
2,335	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6050778e-05
2,748	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0453265e-05
3,825	Spatial Online Sampling and Aggregation	2016	VLDB	6.9795872e-05
4,236	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7028998e-05
4,563	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5201574e-05
5,835	Spatial Independent Range Sampling	2021	SIGMOD	5.9606673e-05
7,549	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.4809567e-05
8,976	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.2343756e-05
9,181	Towards Systematic Index Dynamization	2024	VLDB	5.1989155e-05
10,535	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	4.9605343e-05
12,454	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,864	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB
2	9,318	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
3	793	Random Sampling over Joins Revisited	2018	SIGMOD
4	7,576	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
5	8,579	Sampling Big Ideas in Query Optimization	2023	PODS
6	6,597	Efficient Search of Multidimensional B-Trees	1995	VLDB
7	10,345	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB
8	57	On Random Sampling over Joins	1999	SIGMOD
9	175	Simple Random Sampling from Relational Databases	1986	VLDB
10	4,563	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB