AB-tree: Index for Concurrent Random Sampling and Updates

Summary: AB-tree, an aggregate B-tree index, enables highly concurrent random sampling and updates in logarithmic time. Identifies key concurrency challenges in maintaining aggregate weights and demonstrates efficiency gains across diverse AQP workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12684
Venue: VLDB
Year: 2022
Pagerank: 4.2421586e-05
Overall Rank: 9,949 | 30.79%
DOI: 10.14778/3538598.3538606

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,758	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	4.2879116e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05
11,285	Approximate Queries over Concurrent Updates	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
282	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00029057817
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,323	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00012601997
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,405	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012174592
1,573	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00011295081
2,203	Independent Range Sampling	2014	PODS	9.2981095e-05
2,394	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	8.9001843e-05
2,580	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.5058814e-05
3,244	Access Method Concurrency with Recovery	1992	SIGMOD	7.3262881e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,335	Efficient Computation of Temporal Aggregates with Range Predicates	2001	PODS	5.5647464e-05
2,580	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.5058814e-05
12,810	Index Concurrency Control in Firm Real-Time DBMS	1995	VLDB	4.1945683e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
10,337	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.1945683e-05
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05
357	Random Sampling from B+ trees	1989	VLDB	0.00026020098
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-05
10,556	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.1945683e-05
11,285	Approximate Queries over Concurrent Updates	2023	VLDB	4.1945683e-05