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: 7907
Venue: VLDB
Year: 1989
Pagerank: 0.00026020098
Overall Rank: 357 | 97.52%
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.00051315959
152	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00040963225
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
473	Sampling Large Databases for Association Rules	1996	VLDB	0.0002233798
588	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00019604754
783	Random Sampling from Hash Files	1990	SIGMOD	0.00016704834
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012051353
1,433	Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results	1994	SIGMOD	0.00012009649
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
2,813	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0773142e-05
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
4,245	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.3272687e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
7,362	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	4.752436e-05
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05
9,903	Towards Systematic Index Dynamization	2024	VLDB	4.258022e-05
11,913	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	4.1945683e-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
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-05
9,404	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	4.3441378e-05
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05
8,470	Sampling Big Ideas in Query Optimization	2023	PODS	4.5038423e-05
6,480	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0475112e-05
9,949	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.2421586e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05