MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918105271238656 |
|---|---|
| author | Manor, Daniel Perry, Mor Sulamy, Moshe |
| author_facet | Manor, Daniel Perry, Mor Sulamy, Moshe |
| contents | In concurrent data structures, the efficiency of set operations can vary significantly depending on the workload characteristics. Numerous concurrent set implementations are optimized and fine-tuned to excel in scenarios characterized by predominant read operations. However, they often perform poorly when confronted with workloads that heavily prioritize updates. Additionally, current leading-edge concurrent sets optimized for update-heavy tasks typically lack efficiency in handling atomic range queries. This study introduces the MTASet, which leverages a concurrent (a,b)-tree implementation. Engineered to accommodate update-heavy workloads and facilitate atomic range queries, MTASet surpasses existing counterparts optimized for tasks in range query operations by up to 2x. Notably, MTASet ensures linearizability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20041 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads Manor, Daniel Perry, Mor Sulamy, Moshe Distributed, Parallel, and Cluster Computing Data Structures and Algorithms In concurrent data structures, the efficiency of set operations can vary significantly depending on the workload characteristics. Numerous concurrent set implementations are optimized and fine-tuned to excel in scenarios characterized by predominant read operations. However, they often perform poorly when confronted with workloads that heavily prioritize updates. Additionally, current leading-edge concurrent sets optimized for update-heavy tasks typically lack efficiency in handling atomic range queries. This study introduces the MTASet, which leverages a concurrent (a,b)-tree implementation. Engineered to accommodate update-heavy workloads and facilitate atomic range queries, MTASet surpasses existing counterparts optimized for tasks in range query operations by up to 2x. Notably, MTASet ensures linearizability. |
| title | MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.20041 |