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
- 13813
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,556 | 26.57%
- DOI
-
10.14778/3718057.3718074
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
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.0032169493 |
| 23 |
A Critique of ANSI SQL Isolation Levels |
1995 |
SIGMOD |
0.00083894938 |
| 349 |
Serializable Isolation for Snapshot Databases |
2008 |
SIGMOD |
0.00026440605 |
| 497 |
Column-Stores vs. Row-Stores: How Different Are They Really? |
2008 |
SIGMOD |
0.00021716559 |
| 957 |
Serializable Snapshot Isolation in PostgreSQL |
2012 |
VLDB |
0.00015048214 |
| 972 |
Immortal DB: Transaction Time Support for SQL Server |
2005 |
SIGMOD |
0.00014922442 |
| 986 |
Managing Intervals Efficiently in Object-Relational Databases |
2000 |
VLDB |
0.00014838568 |
| 1,359 |
Range Queries in OLAP Data Cubes |
1997 |
SIGMOD |
0.0001238588 |
| 3,045 |
Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager |
2008 |
SIGMOD |
7.6595001e-05 |
| 3,134 |
Transaction Time Indexing with Version Compression |
2008 |
VLDB |
7.4967274e-05 |
| 3,614 |
Persistent Data Sketching |
2015 |
SIGMOD |
6.9147318e-05 |
| 3,689 |
Compacting Transactional Data in Hybrid OLTP&OLAP Databases |
2012 |
VLDB |
6.8396366e-05 |
| 3,810 |
Searching in Time |
2006 |
SIGMOD |
6.7394548e-05 |
| 4,444 |
Hierarchical Cubes for Range-Sum Queries |
1999 |
VLDB |
6.1831691e-05 |
| 5,909 |
At-the-time and Back-in-time Persistent Sketches |
2021 |
SIGMOD |
5.2769377e-05 |
| 7,915 |
HINT: A Hierarchical Index for Intervals in Main Memory |
2022 |
SIGMOD |
4.617775e-05 |
| 8,580 |
LIT: Lightning-fast In-memory Temporal Indexing |
2024 |
SIGMOD |
4.492241e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,692 |
Supporting Frequent Updates in R-Trees: A Bottom-Up Approach |
2003 |
VLDB |
5.9958252e-05 |
| 4,021 |
Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures |
2016 |
PODS |
6.5225987e-05 |
| 7,208 |
Efficient Bulk Updates on Multiversion B-trees |
2013 |
VLDB |
4.7998295e-05 |
| 10,562 |
FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update |
2025 |
VLDB |
4.1945683e-05 |
| 7,054 |
Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability |
2018 |
VLDB |
4.8496866e-05 |
| 11,822 |
Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries |
2016 |
PODS |
4.1945683e-05 |
| 9,949 |
AB-tree: Index for Concurrent Random Sampling and Updates |
2022 |
VLDB |
4.2421586e-05 |
| 12,411 |
Towards Efficient Main-Memory Use For Optimum Tree Index Update |
2008 |
VLDB |
4.1945683e-05 |
| 10,387 |
Parallel kd-tree with Batch Updates |
2025 |
SIGMOD |
4.1945683e-05 |
| 1,774 |
Query and Update Efficient B+-Tree Based Indexing of Moving Objects |
2004 |
VLDB |
0.00010604097 |