Dynamic algorithms capable of supporting batches of updates are increasingly relevant today due to the emergence of rapidly-evolving dynamic datasets. Since processing updates on a single processor is often unrealistic for large batches of updates, designing parallel dynamic algorithms that achieve provably low span is important for many applications. In this paper, motivated by the difficulty in designing parallel batch-dynamic algorithms by hand, we propose a framework for algorithmically dynamizing static round-synchronous algorithms  to obtain parallel batch-dynamic algorithms with good bounds on their work and span. In our framework, the algorithm designer can apply the technique to any suitably defined static algorithm. We then obtain theoretical guarantees for algorithms in our framework by defining the notion of a computation distance between two executions of the underlying algorithm. Using this framework , we develop the first work-efficient parallel batch-dynamic algorithm for dynamic trees that supports both subtree queries and path queries, as well as a variety of nonlocal queries such as centers and medians. We further investigate the applicability of the framework by analyzing map-reduce-based computations, and a random-mate list contraction algorithm , which, when dynamized, yields a simple solution to the batch-dynamic lists problem that matches the work bounds of the best known hand-crafted data structure .
The dynamic trees problem is to maintain a forest subject to edge insertions and deletions while facilitating queries such as connectivity, path weights, and subtree weights. Dynamic trees are a fundamental building block of a large number of graph algorithms. Although traditionally studied in the single-update setting, dynamic algorithms capable of supporting batches of updates are increasingly relevant today due to the emergence of rapidly evolving dynamic datasets. Since processing updates on a single processor is often unrealistic for large batches of updates, designing parallel batch-dynamic algorithms that achieve provably low span is important for many applications. In this work, we design the first work-efficient parallel batch-dynamic algorithm for dynamic trees that is capable of supporting both path queries and subtree queries, as well as a variety of non-local queries. To achieve this, we propose a framework for algorithmically dynamizing static round-synchronous algorithms that allows us to obtain parallel batch-dynamic algorithms with good bounds on their work and span. In our framework, the algorithm designer can apply the technique to any suitably defined static algorithm. We then obtain theoretical guarantees for algorithms in our framework by defining the notion of a computation distance between two executions of the underlying algorithm. Our dynamic trees algorithm is obtained by applying our dynamization framework to the parallel tree contraction algorithm of Miller and Reif, and then performing a novel analysis of the computation distance of this algorithm under batch updates. We show that k updates can be performed in O(k \log(1+n/k)) work in expectation, which matches an existing algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications .
R
Dynamic algorithms
The dynamic trees problem is to maintain a forest subject to edge insertions and deletions while facilitating queries such as connectivity, path weights, and subtree weights. Dynamic trees are a fundamental building block of a large number of graph algorithms. Although traditionally studied in the single-update setting, dynamic algorithms
R
rapidly-evolving
rapidly evolving
R
dynamic
batch-dynamic
R
paper, motivated by the difficulty in designing
work, we design the first work-efficient
R
algorithms by hand,
algorithm for dynamic trees that is capable of supporting both path queries and subtree queries, as well as a variety of non-local queries. To achieve this,
A
that allows us
R
Using this framework , we develop the first work-efficient parallel batch-dynamic algorithm for dynamic trees that supports both subtree queries and path queries, as well as a variety of nonlocal queries such as centers and medians. We further investigate the applicability of the framework by analyzing map-reduce-based computations, and a random-mate list contraction algorithm , which, when dynamized, yields a simple solution to the batch-dynamic lists problem that matches the work bounds of the best known hand-crafted data structure
Our dynamic trees algorithm is obtained by applying our dynamization framework to the parallel tree contraction algorithm of Miller and Reif, and then performing a novel analysis of the computation distance of this algorithm under batch updates. We show that k updates can be performed in O(k \log(1+n/k)) work in expectation, which matches an existing algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications