Random Sampling from Pseudo-Ranked B+ Trees

Summary: Introduces sampling from pseudo-ranked B+ trees, augmented with rank limits. Low rejection with marginal update cost; outperforms full-root updates and high-rejection sampling, validated on production databases and prototype workload simulations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h684e01a4bb4d6df7
Venue: VLDB
Year: 1992
Pagerank: 6.5201574e-05
Overall Rank: 4,563 | 69.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Gennady Antoshenkov (Digital Equipment Corporation)

BibTeX Citation

@article{antoshenkov_vldb92,
        title = {{Random Sampling from Pseudo-Ranked B+ Trees}},
        author = {Antoshenkov, Gennady},
        journal = {PVLDB},
        series = {{VLDB} '92},
        pages = {375},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
2,176	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.9031141e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026701703
183	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026316699
297	Object and File Management in the EXODUS Extensible Database System	1986	VLDB	0.0002187415
480	Random Sampling from B+ trees	1989	VLDB	0.00017573936
1,012	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012489386
1,423	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010696781

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,076	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
2	14,848	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
3	3,035	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD
4	175	Simple Random Sampling from Relational Databases	1986	VLDB
5	6,597	Efficient Search of Multidimensional B-Trees	1995	VLDB
6	57	On Random Sampling over Joins	1999	SIGMOD
7	10,345	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB
8	11,296	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
9	9,318	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
10	480	Random Sampling from B+ trees	1989	VLDB