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
- 13814
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,565 | 26.58%
- 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.0032118946 |
| 23 |
A Critique of ANSI SQL Isolation Levels |
1995 |
SIGMOD |
0.00083899338 |
| 348 |
Serializable Isolation for Snapshot Databases |
2008 |
SIGMOD |
0.00026473778 |
| 496 |
Column-Stores vs. Row-Stores: How Different Are They Really? |
2008 |
SIGMOD |
0.00021705611 |
| 956 |
Serializable Snapshot Isolation in PostgreSQL |
2012 |
VLDB |
0.00015068342 |
| 972 |
Immortal DB: Transaction Time Support for SQL Server |
2005 |
SIGMOD |
0.00014907846 |
| 986 |
Managing Intervals Efficiently in Object-Relational Databases |
2000 |
VLDB |
0.00014825631 |
| 1,363 |
Range Queries in OLAP Data Cubes |
1997 |
SIGMOD |
0.00012380611 |
| 3,048 |
Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager |
2008 |
SIGMOD |
7.6522631e-05 |
| 3,141 |
Transaction Time Indexing with Version Compression |
2008 |
VLDB |
7.4910063e-05 |
| 3,618 |
Persistent Data Sketching |
2015 |
SIGMOD |
6.9080647e-05 |
| 3,686 |
Compacting Transactional Data in Hybrid OLTP&OLAP Databases |
2012 |
VLDB |
6.839208e-05 |
| 3,812 |
Searching in Time |
2006 |
SIGMOD |
6.7325618e-05 |
| 4,443 |
Hierarchical Cubes for Range-Sum Queries |
1999 |
VLDB |
6.1772772e-05 |
| 5,910 |
At-the-time and Back-in-time Persistent Sketches |
2021 |
SIGMOD |
5.2718714e-05 |
| 7,916 |
HINT: A Hierarchical Index for Intervals in Main Memory |
2022 |
SIGMOD |
4.6133471e-05 |
| 8,577 |
LIT: Lightning-fast In-memory Temporal Indexing |
2024 |
SIGMOD |
4.4879347e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,683 |
Supporting Frequent Updates in R-Trees: A Bottom-Up Approach |
2003 |
VLDB |
5.9940496e-05 |
| 4,026 |
Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures |
2016 |
PODS |
6.5166769e-05 |
| 7,208 |
Efficient Bulk Updates on Multiversion B-trees |
2013 |
VLDB |
4.795225e-05 |
| 10,571 |
FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update |
2025 |
VLDB |
4.1905499e-05 |
| 7,046 |
Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability |
2018 |
VLDB |
4.8471584e-05 |
| 11,830 |
Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries |
2016 |
PODS |
4.1905499e-05 |
| 9,945 |
AB-tree: Index for Concurrent Random Sampling and Updates |
2022 |
VLDB |
4.240067e-05 |
| 12,420 |
Towards Efficient Main-Memory Use For Optimum Tree Index Update |
2008 |
VLDB |
4.1905499e-05 |
| 10,398 |
Parallel kd-tree with Batch Updates |
2025 |
SIGMOD |
4.1905499e-05 |
| 1,766 |
Query and Update Efficient B+-Tree Based Indexing of Moving Objects |
2004 |
VLDB |
0.00010611043 |