Random Sampling from B+ trees

Summary: Introduces acceptance/rejection (A/R) sampling from standard B+ trees to obtain simple random samples without auxiliary rank data. Compared to ranked B+ tree methods, A/R sampling is retrofit-friendly to existing DBMSs and supports iterative and batch sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7908
Venue: VLDB
Year: 1989
Pagerank: 0.00026276293
Overall Rank: 352 | 97.56%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Frank Olken
2. Doron Rotem

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
151	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00041010211
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
473	Sampling Large Databases for Association Rules	1996	VLDB	0.00022304724
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531
764	Random Sampling from Hash Files	1990	SIGMOD	0.00016958917
803	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016438972
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012044433
1,432	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00012000371
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
2,817	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0695314e-05
3,965	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5786424e-05
4,032	Spatial Online Sampling and Aggregation	2016	VLDB	6.5131946e-05
4,244	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.3228453e-05
5,955	Spatial Independent Range Sampling	2021	SIGMOD	5.2539404e-05
7,358	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	4.7478752e-05
9,760	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2838028e-05
9,902	Towards Systematic Index Dynamization	2024	VLDB	4.2539423e-05
11,921	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1905499e-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
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-05
9,410	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	4.3399748e-05
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
8,602	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4822166e-05
8,467	Sampling Big Ideas in Query Optimization	2023	PODS	4.4995247e-05
6,473	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0427056e-05
9,945	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.240067e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
3,965	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5786424e-05