Parallel batch queries on dynamic trees: algorithms and experiments
Humza Ikram, Andrew Brady, Daniel Anderson, Guy Blelloch · 2025
Read Parallel batch queries on dynamic trees: algorithms and experiments by Humza Ikram, Andrew Brady, Daniel Anderson, Guy Blelloch (2025) 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-2506-16477.txt.
Introduction
Humza Ikram, Andrew Brady, Daniel Anderson, and Guy Blelloch improve data structures that maintain a forest of linked nodes while its edges change. Such dynamic tree structures sit inside many modern algorithms and answer each query in logarithmic time. Recent work let them handle batches of changes at once, in parallel, and this team pushes that line further. They widen a tree method so nodes can have any number of links, not just two.
Their version also answers new kinds of batch questions: about subtrees, paths between nodes, shared ancestors, and the nearest marked node. They prove tight bounds on the work involved and a short parallel running depth. The team built the first general implementation of such batch trees. Tests, using a generator that makes forests of shapes, show strong speedups that hold across tree types. They also use the structure to speed a classic spanning tree algorithm.
Catalog record
| CREATOR | Humza Ikram, Andrew Brady, Daniel Anderson, Guy Blelloch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16477
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parallel batch queries on dynamic trees: algorithms and experiments Humza Ikram, Andrew Brady, Daniel Anderson, Guy Blelloch Abstract . Dynamic tree data structures maintain a forest while supporting insertion and deletion of edges and a broad set of queries in O ( log n ) O(\log n) time per operation. Such data structures are at the core of many modern algorithms. Recent work has extended dynamic trees so as to support batches of updates or queries so as to run in parallel, and these batch parallel dynamic trees are now used in several parallel algorithms. In this work we describe improvements to batch parallel dynamic trees, describe an implementation that incorporates these improvements, and experiments using it. The improvements includes generalizing prior work on RC (rake compress) trees to work with arbitrary degree while still supporting a rich set of queries, and describing how to support batch subtree queries, path queries, LCA queries, and nearest-marked-vertex queries in O ( k + k log ( 1 + n / k ) ) O(k+k\log(1+n/k)) work and polylogarithmic span. Our implementation is the first general implementation of batch dynamic trees (supporting arbitrary degree and general queries). Our experiments include measuring the time to create the trees, varying batch sizes for updates and queries, and using the tree to implement incremental batch-parallel minimum spanning trees. To run the experiments we develop a forest generator that is parameterized to create distributions of trees of differing characteristics (e.g., degree, depth, and relative tree sizes). Our experiments show good speedup and that the algorithm performance is robust across forest characteristics. 1. Introduction The dynamic trees problem is to maintain a forest of trees while supporting insertion and deletions of edges, and a variety of queries on the tree. Queries can include, for example, determining whether two vertices are in the same tree, the minimum weight on a path in a tree, the sum of values on a subtree, and many more. The problem was introduced by Sleator and Tarjan ( Sleator and Tarjan 1983 ) , where they presented a data structures that supports updates as well as path queries (e.g., max weight or sum of weights on a path) in O(\log n) amortized time per operation on a tree with n vertices. They also present important applications of dynamic trees, including to incremental minimum spanning trees, maximum flow, and network simplex. In all cases the dynamic trees improved the bounds over prior results. Since the work of Sleator and Tarjan, there have been many improvements and extensions ( Henzinger and King 1995 ; Frederickson 1985 ; Frederickson 1997a ; Frederickson 1997b ; Holm and de Lichtenberg 1998 ; Tarjan and Werneck 2005 ; Alstrup et al. 2005 ; Acar et al. 2004 ; Acar et al. 2005 ) . Furthermore, researchers have identified many more applications of dynamic trees, including algorithms for dynamic graph connectivity ( Frederickson 1985 ; Henzinger and King 1995 ; Holm et al. 2001 ; Kapron et al. 2013 ; Acar et al. 2019 ) , dynamic minimum spanning trees ( Frederickson 1985 ; Henzinger and King 1995 ; Henzinger and King 2001 ; Holm et al. 2001 ; Anderson et al. 2020 ) , and minimum cuts ( Karger 2000 ; Geissmann and Gianinazzi 2018 ; Gawrychowski et al. 2020 ; Anderson and Blelloch 2023 ) . Importantly, dynamic trees play a key role in recent groundbreaking results on maximum flow in almost linear time ( Chen et al. 2023 ) . Most of this work has considered sequential algorithms that permit a single update each time step. Given that all modern machines are now parallel, it is important to support processing multiple updates in parallel. Thus, more recent work has sought to maintain a forest in the batch-parallel dynamic model, where edges are inserted and deleted in batches that must be handled in parallel. The goal of such batch dynamic data structures is typically to ensure the work per update is no more than in the sequential context (i.e., work efficient) and that the span is polylogarithmic in the size of the forest. The span is the critical path of dependences and hence the minimum time that is required to run a computation in parallel. The first such work was Tseng et al.’s batch-parallel Euler-tour trees ( Tseng et al. 2019 ) , which for batch updates of size k , achieves O(k\log(1+\frac{n}{k})) expected work, which matches the sequential algorithms ( O(\log n) work per edge) for low values of k , and is optimal ( O(n) work) for large values of k . Furthermore, the span for processing each batch is O(\log n) . Their work also included an implementation that showed that maintaining Euler tour trees is efficient in practice. However, Euler-tour trees are quite limited in the set of operations they support. For example, they do not support path queries, or subtree queries where the operator does not have an inverse (e.g., find the maximum in a subtree). Acar et al. developed parallel batch-dynamic Rake-Compress-trees ( Acar et al. 2020 ) (RC-trees) with the same cost bounds. RC-trees support a much broader class of queries, including all queries that are supported by any of the other known dynamic trees. Batch parallel RC-trees have proven to be a powerful technique in developing other parallel algorithms, including batch parallel incremental MST ( Anderson et al. 2020 ) , parallel minimum cut ( Anderson and Blelloch 2023 ) , and parallel breadth-first search ( Ghaffari et al. 2023 ) . The original work on RC-trees used randomization. Recent work has show that the same work bounds can be achieved deterministically ( Anderson and Blelloch 2024 ) . RC-trees, however, only directly support trees with constant vertex degree. Prior work has had to apply ad-hoc techniques to simulate trees with higher degree. Furthermore only a minimal implementation of RC-trees exists ( Anderson et al. 2021 ) . In this paper we present several results that build on RC-trees. We show how to layer d -ary trees on top of trees with constant degree while still supporting dynamic updates and queries. We maintain the same bounds as with constant degree, at the cost of requiring randomization. We also present some new better bounds on queries. In particular we describe algorithms for batch Lowest Common Ancestor (LCA) queries, batch subtree queries, batch patch queries, and batch nearest-marked-vertex queries that run in O(k+k\log(1+\frac{n}{k})) work where k is the batch size and n is the number of vertices in the forest. The span for these queries is O(\log n) . This improves over simply running the queries independently, which would require O(k\log n) work. Theoretically, we achieve the following result: Theorem 1.1. There exists a data structure that support the following operations on arbitrary weighted forests: • A batch of k edge insertions and deletions in O(k+k\log(1+\frac{n}{k})) work and O(\log^{2}n) span. • A batch of k subtree queries over weights from a commutative semigroup in O(k\log(1+\frac{n}{k})) work and O(\log n) span. • A batch of k path queries over weights from a commutative group, or min/max queries in O(k+k\log(1+\frac{n}{k})) work and O(\log n) span. • A batch of k LCA