Batch-parallel link-cut trees achieve faster dynamic graph updates
Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
Data Structures and Algorithms
Summary
Updating data structures that represent changing networks quickly is a hard problem, especially when many changes happen at once. The paper introduces MOJOS, a new way to handle many updates in parallel efficiently, improving over older methods. MOJOS builds on a clever combination of existing tree representations and a new data structure called treaps that handle batch operations with optimal speed. This work also provides the first parallel link-cut tree that balances quick updates and queries, making certain dynamic network algorithms faster and more practical.
What this means in practice
- •For network schedulers: Use fast batch-parallel link-cut trees to update and query changing network structures in real-time scheduling systems.
- •For database engineers: Improve dynamic indexing and query processing by integrating batch-parallel tree data structures for faster data structure modifications.
Authors
Quinten De Man, Laxman Dhulipala
Abstract
Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic tree data structures, including Euler tour trees, UFO trees, topology trees, and rake-compress trees, are all significantly outperformed in the sequential setting by link-cut trees, which have been the sequential state-of-the-art for over 40 years. Despite their excellent performance in the sequential setting, designing efficient batch-parallel link-cut trees has remained a major open problem. In this paper, we close this gap by introducing MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. We exploit the fact that both Euler tour trees and link-cut trees rely on a common dynamic sequence abstraction that supports splitting and joining. We introduce a new batch-dynamic sequence built using treaps that achieves optimal work and depth, and outperforms existing parallel skip list and treap implementations for batch updates, queries, and memory usage. With MOJOS, we develop a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries. Unlike prior batch-parallel Euler tour trees which rely on skip list's ability to represent cyclic sequences, MOJOS allows any batch-dynamic sequence data structure to be used as a drop-in replacement. Finally, we develop the first theoretically-efficient batch-parallel link-cut tree, which is also the first batch-dynamic data structure supporting path queries to achieve $O(\log n)$ depth for batch updates in the binary-forking model. Our link-cut tree implementation outperforms all known parallel batch-dynamic tree data structures supporting path queries.