DBScholar

Back to papers

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.9605343e-05
Overall Rank
11,296 | 24.29%
DOI
10.14778/3718057.3718074
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

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

Authors

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,506 Concurrent Path-Copying Update to Tree Structures 2026 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

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.0019892478
19 A Critique of ANSI SQL Isolation Levels 1995 SIGMOD 0.00058631912
237 Serializable Isolation for Snapshot Databases 2008 SIGMOD 0.00023615848
332 Column-Stores vs. Row-Stores: How Different Are They Really? 2008 SIGMOD 0.00020739447
725 Serializable Snapshot Isolation in PostgreSQL 2012 VLDB 0.00014434166
1,091 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001205609
1,110 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011949109
1,210 Immortal DB: Transaction Time Support for SQL Server 2005 SIGMOD 0.00011495323
2,857 Transaction Time Indexing with Version Compression 2008 VLDB 7.9152217e-05
3,090 Persistent Data Sketching 2015 SIGMOD 7.6420011e-05
3,108 Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager 2008 SIGMOD 7.6237576e-05
3,308 Compacting Transactional Data in Hybrid OLTP&OLAP Databases 2012 VLDB 7.4195851e-05
3,763 Searching in Time 2006 SIGMOD 7.0180801e-05
4,056 Hierarchical Cubes for Range-Sum Queries 1999 VLDB 6.8142516e-05
5,399 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 6.1336701e-05
7,391 HINT: A Hierarchical Index for Intervals in Main Memory 2022 SIGMOD 5.5208477e-05
8,773 LIT: Lightning-fast In-memory Temporal Indexing 2024 SIGMOD 5.2682366e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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