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.00017632787
Overall Rank: 477 | 96.80%
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.00036487763
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024344086
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020329113
473	Sampling Large Databases for Association Rules	1996	VLDB	0.00017673931
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,229	Random Sampling from Hash Files	1990	SIGMOD	0.00011420642
1,467	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010567959
1,640	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00010011692
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
2,736	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0758355e-05
3,818	Spatial Online Sampling and Aggregation	2016	VLDB	7.0060535e-05
4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7271293e-05
4,546	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5436884e-05
5,819	Spatial Independent Range Sampling	2021	SIGMOD	5.9832748e-05
7,527	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.5016558e-05
8,944	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.2542285e-05
9,149	Towards Systematic Index Dynamization	2024	VLDB	5.2186338e-05
10,458	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	4.9793485e-05
12,405	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.9793485e-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.00040035279

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB
2	9,699	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
3	795	Random Sampling over Joins Revisited	2018	SIGMOD
4	7,557	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
5	8,553	Sampling Big Ideas in Query Optimization	2023	PODS
6	6,584	Efficient Search of Multidimensional B-Trees	1995	VLDB
7	10,315	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,546	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB