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

CREATORQuinten De Man, Atharva Sharma, Kishen N Gowda, Laxman Dhulipala
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10706

Browse the full library · About the Tower of Babel