{
  "annotation_id": "1108009b-9fb4-4730-978b-0d4d273bc50d",
  "date_created": "2026-02-17T05:53:26.460000Z",
  "date_modified": "2026-02-17T05:53:26.460000Z",
  "file_hash": "99609bc00d60d5dc73314b91417b5826b5ca7e929d81b915c7f39385fc1e291d",
  "private": false,
  "record": {
    "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.\n  In this paper, we design a new parallel batch-dynamic trees data structure called UFO trees that simultaneously supports a wide range of query functionality, supports work-efficient parallel batch-dynamic updates, and is competitive with link-cut trees when run sequentially. We prove that a key reason for the strong practical performance of both link-cut trees and UFO trees is that they can perform updates and queries in sub-logarithmic time for low-diameter trees. We perform an experimental study of our optimized C++ implementations of UFO trees with ten other dynamic tree implementations, several of which are new, in a broad benchmark of both synthetic and real-world trees of varying diameter and size. Our results show that, in both sequential and parallel settings, UFO trees are the fastest dynamic tree data structure that supports a wide range of queries. Our new implementation of UFO trees has low space usage and easily scales to billion-size inputs, making it a promising building block for implementing more complex dynamic graph algorithms in practice.",
    "arxiv_id": "2601.10706",
    "authors": [
      "Quinten De Man",
      "Atharva Sharma",
      "Kishen N Gowda",
      "Laxman Dhulipala"
    ],
    "categories": [
      "cs.DS"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees",
    "url": "https://arxiv.org/abs/2601.10706",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "56d2a757-aa5c-414c-b358-35eadb4901b1",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}