UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
Quinten De Man, Atharva Sharma, Kishen N Gowda, Laxman Dhulipala · 2026
Read UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees by Quinten De Man, Atharva Sharma, Kishen N Gowda, Laxman Dhulipala (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10706.txt.
Description
Quinten De Man, Atharva Sharma, Kishen N Gowda, and Laxman Dhulipala present UFO Trees, a data structure for dynamic forests. The dynamic trees problem asks software to keep a tree current as edges come and go. Queries ask whether two nodes are linked, or what lies on a path. The classic link-cut tree has led this field for forty years.
The authors' tests show link-cut trees are still the fastest sequential option. UFO Trees target parallel batch updates instead, where many changes land at once. The design claims both practical speed and proven efficiency bounds. Such structures sit inside graph analytics and network tools that must track changing connections at scale.
Catalog record
| CREATOR | Quinten De Man, Atharva Sharma, Kishen N Gowda, Laxman Dhulipala |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-10706