Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2601.05225 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911398778372096 |
|---|---|
| author | Wrench, Evan Singh, Ajay Roh, Younghun Fatourou, Panagiota Jayanti, Siddhartha Ruppert, Eric Wei, Yuanhao |
| author_facet | Wrench, Evan Singh, Ajay Roh, Younghun Fatourou, Panagiota Jayanti, Siddhartha Ruppert, Eric Wei, Yuanhao |
| contents | Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to insertion, deletion, and lookup. In this paper, we present the first lock-free augmented balanced search tree supporting generic augmentation functions. Our algorithmic ideas build upon a recent augmented unbalanced search tree presented by Fatourou and Ruppert [DISC, 2024]. We implement both data structures, solving some memory reclamation challenges in the process, and provide an experimental performance analysis of them. We also present optimized versions of our balanced tree that use delegation to achieve better scalability and performance (by more than 2x in most workloads). Our experiments show that our augmented balanced tree completes updates 2.2 to 30 times faster than the unbalanced augmented tree, and outperforms unaugmented trees by up to several orders of magnitude on 120 threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05225 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Concurrent Balanced Augmented Trees Wrench, Evan Singh, Ajay Roh, Younghun Fatourou, Panagiota Jayanti, Siddhartha Ruppert, Eric Wei, Yuanhao Data Structures and Algorithms Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to insertion, deletion, and lookup. In this paper, we present the first lock-free augmented balanced search tree supporting generic augmentation functions. Our algorithmic ideas build upon a recent augmented unbalanced search tree presented by Fatourou and Ruppert [DISC, 2024]. We implement both data structures, solving some memory reclamation challenges in the process, and provide an experimental performance analysis of them. We also present optimized versions of our balanced tree that use delegation to achieve better scalability and performance (by more than 2x in most workloads). Our experiments show that our augmented balanced tree completes updates 2.2 to 30 times faster than the unbalanced augmented tree, and outperforms unaugmented trees by up to several orders of magnitude on 120 threads. |
| title | Concurrent Balanced Augmented Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.05225 |