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: h0e07e46bf3568e4f
Venue: VLDB
Year: 2025
Pagerank: 4.9793485e-05
Overall Rank: 11,232 | 24.49%
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,428	Concurrent Path-Copying Update to Tree Structures	2026	SIGMOD	4.9793485e-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.001992968
19	A Critique of ANSI SQL Isolation Levels	1995	SIGMOD	0.00058781151
237	Serializable Isolation for Snapshot Databases	2008	SIGMOD	0.00023660039
331	Column-Stores vs. Row-Stores: How Different Are They Really?	2008	SIGMOD	0.0002077683
726	Serializable Snapshot Isolation in PostgreSQL	2012	VLDB	0.00014459037
1,106	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00011994008
1,128	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00011905274
1,207	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011538247
2,847	Transaction Time Indexing with Version Compression	2008	VLDB	7.9447157e-05
3,080	Persistent Data Sketching	2015	SIGMOD	7.6662346e-05
3,097	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.6524049e-05
3,308	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.4411187e-05
3,757	Searching in Time	2006	SIGMOD	7.0441066e-05
4,032	Hierarchical Cubes for Range-Sum Queries	1999	VLDB	6.8400896e-05
5,373	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1569337e-05
7,374	HINT: A Hierarchical Index for Intervals in Main Memory	2022	SIGMOD	5.5401491e-05
8,743	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.2882178e-05

Semantically Similar Papers

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