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: 8098
Venue: VLDB
Year: 1989
Pagerank: 0.00018002218
Overall Rank: 467 | 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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
210	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024797689
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
462	Sampling Large Databases for Association Rules	1996	VLDB	0.00018065337
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,206	Random Sampling from Hash Files	1990	SIGMOD	0.00011663837
1,440	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010778889
1,603	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00010236342
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
2,683	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.2608808e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
4,138	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.8779166e-05
4,458	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.6905953e-05
5,692	Spatial Independent Range Sampling	2021	SIGMOD	6.119196e-05
7,385	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.6278655e-05
8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.3722049e-05
8,988	Towards Systematic Index Dynamization	2024	VLDB	5.3384135e-05
10,244	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	5.093636e-05
12,112	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	5.093636e-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
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149

Semantically Similar Papers

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