Efficient Concurrent Updates to Persistent Randomized Binary Search Trees

Summary: Concurrent update strategy for persistent randomized BSTs achieving m updates on n elements in O(log n + m) time with O(log n) threads, enabling high-speed updates while preserving read-only snapshots for consistent range/historical queries. Hybrid concurrency implementation improves multicore scalability and outperforms prior persistent-BST designs across workloads and data distributions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14001
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,824 | 25.74%
DOI: 10.14778/3718057.3718074

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Guanhao Hou (Chinese University of Hong Kong)
2. Jinchao Huang (Chinese University of Hong Kong)
3. Fangyuan Zhang (Chinese University of Hong Kong)
4. Sibo Wang (Chinese University of Hong Kong)

BibTeX Citation

@article{hou_vldb25,
        title = {{Efficient Concurrent Updates to Persistent Randomized Binary Search Trees}},
        author = {Hou, Guanhao and Huang, Jinchao and Zhang, Fangyuan and Wang, Sibo},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {5},
        pages = {1481--1494},
        doi = {10.14778/3718057.3718074},
        url = {https://doi.org/10.14778/3718057.3718074},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,212	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
19	A Critique of ANSI SQL Isolation Levels	1995	SIGMOD	0.00058720861
245	Serializable Isolation for Snapshot Databases	2008	SIGMOD	0.00023458287
345	Column-Stores vs. Row-Stores: How Different Are They Really?	2008	SIGMOD	0.00020656723
733	Serializable Snapshot Isolation in PostgreSQL	2012	VLDB	0.00014533437
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
1,139	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.0001202217
1,210	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011656235
2,824	Transaction Time Indexing with Version Compression	2008	VLDB	8.0882727e-05
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
3,038	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.8272965e-05
3,292	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.5518441e-05
3,691	Searching in Time	2006	SIGMOD	7.1998478e-05
3,954	Hierarchical Cubes for Range-Sum Queries	1999	VLDB	6.9956335e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
7,225	HINT: A Hierarchical Index for Intervals in Main Memory	2022	SIGMOD	5.6673083e-05
8,575	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.4095946e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
2	6,126	Efficient Bulk Updates on Multiversion B-trees	2013	VLDB
3	10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
4	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
5	12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
6	10,093	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB
7	12,605	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
8	10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD
9	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
10	10,212	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD