UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees

Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming 2026

View at publisher
Authors: Quinten De Man, Atharva Sharma, Kishen N. Gowda, Laxman Dhulipala
DOI: 10.1145/3774934.3786431
Cited by: 1
References: 23

Abstract

The dynamic trees problem is to maintain a tree under edge updates while supporting queries like connectivity queries or path queries. Despite the first data structure for this fundamental problem---the link-cut tree---being invented 40 years ago, our experiments reveal that they are still the fastest sequential data structure for the problem. However, link-cut trees cannot support parallel batch-dynamic updates and have limitations on the kinds of queries they support.

Fields of Study & Subjects

Data Management and Algorithms Advanced Database Systems and Queries Distributed systems and fault tolerance

Publication details

Journal / source
Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming
Publisher
ACM
Pages
109–122
Publication date
28 January 2026