EUVIMEDEUVIMED entdecken
Crossref

Efficient Concurrent Updates to Persistent Randomized Binary Search Trees

Guanhao Hou, Jinchao Huang, Fangyuan Zhang, Sibo Wang

Proceedings of the VLDB Endowment · 2025-01 · 18 (5) · 1481-1494

DOI: 10.14778/3718057.3718074 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 27.08.2025. Verfasst von Guanhao Hou und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 73 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the era of big data, the demand for historical data analytics is growing across various applications. Simultaneously, range queries have been extensively explored within the domain of databases. Binary search trees are a classic type of in-memory index for facilitating range queries. Persistent binary search trees provide read-only snapshots of these trees, allowing range queries to be processed during updates while ensuring consistency. Additionally, multiple versions of snapshots support queries related to historical moments to meet the demands of numerous applications. However, existing implementations do not support both highspeed updates and efficient, accurate historical queries on multi-core platforms. Motivated by this gap, we propose a novel concurrent update strategy to balance update and query performance. For a binary search tree containing n elements, our approach completes m updates in O (log n + m ) time using O (log n ) threads. We further implement a hybrid concurrent strategy to improve the scalability and practical performance of our solution. The experimental results demonstrate that our proposal strikes a good balance between update and query performance. In particular, our proposal outperforms existing solutions under workloads with different data distributions and varying update-query ratios.

Zitieren

APA

Hou, G., Huang, J., Zhang, F., & Wang, S. (2025). Efficient Concurrent Updates to Persistent Randomized Binary Search Trees. Proceedings of the VLDB Endowment, 18(5), 1481-1494. https://doi.org/10.14778/3718057.3718074

Vancouver

Hou G, Huang J, Zhang F, Wang S. Efficient Concurrent Updates to Persistent Randomized Binary Search Trees. Proceedings of the VLDB Endowment. 2025;18(5):1481-1494. doi:10.14778/3718057.3718074

BibTeX
@article{Hou2025,
  author = {Hou, Guanhao and Huang, Jinchao and Zhang, Fangyuan and Wang, Sibo},
  title = {Efficient Concurrent Updates to Persistent Randomized Binary Search Trees},
  journal = {Proceedings of the VLDB Endowment},
  year = {2025},
  volume = {18},
  number = {5},
  pages = {1481--1494},
  doi = {10.14778/3718057.3718074}
}
Kostenlos starten →