License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.2
URN: urn:nbn:de:0030-drops-128686
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12868/
Acar, Umut A. ;
Anderson, Daniel ;
Blelloch, Guy E. ;
Dhulipala, Laxman ;
Westrick, Sam
Parallel Batch-Dynamic Trees via Change Propagation
Abstract
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 nonlocal queries. Previous work-efficient dynamic trees of Tseng et al. were only capable of handling subtree queries [ALENEX'19, (2019), pp. 92 - 106]. To achieve this, we propose a framework for algorithmically dynamizing static round-synchronous algorithms to obtain parallel batch-dynamic algorithms. 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 [FOCS'85, (1985), pp. 478 - 489], 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(klog(1+n/k)) work in expectation, which matches the algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications.
BibTeX - Entry
@InProceedings{acar_et_al:LIPIcs:2020:12868,
author = {Umut A. Acar and Daniel Anderson and Guy E. Blelloch and Laxman Dhulipala and Sam Westrick},
title = {{Parallel Batch-Dynamic Trees via Change Propagation}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {2:1--2:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12868},
URN = {urn:nbn:de:0030-drops-128686},
doi = {10.4230/LIPIcs.ESA.2020.2},
annote = {Keywords: Dynamic trees, Graph algorithms, Parallel algorithms, Dynamic algorithms}
}
|
Keywords: |
|
Dynamic trees, Graph algorithms, Parallel algorithms, Dynamic algorithms |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
