Parallel Batch-Dynamic Trees via Change Propagation

Authors Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Sam Westrick



PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.2.pdf
  • Filesize: 0.57 MB
  • 23 pages

Document Identifiers

Author Details

Umut A. Acar
  • Carnegie Mellon University, Pittsburgh, PA, USA
Daniel Anderson
  • Carnegie Mellon University, Pittsburgh, PA, USA
Guy E. Blelloch
  • Carnegie Mellon University, Pittsburgh, PA, USA
Laxman Dhulipala
  • Carnegie Mellon University, Pittsburgh, PA, USA
Sam Westrick
  • Carnegie Mellon University, Pittsburgh, PA, USA

Acknowledgements

The authors would like to thank Ticha Sethapakdi for helping with the figures.

Cite AsGet BibTex

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.2

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Shared memory algorithms
Keywords
  • Dynamic trees
  • Graph algorithms
  • Parallel algorithms
  • Dynamic algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Umut A Acar, Daniel Anderson, Guy E Blelloch, and Laxman Dhulipala. Parallel batch-dynamic graph connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019. Google Scholar
  2. Umut A Acar, Daniel Anderson, Guy E Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel batch-dynamic trees via change propagation. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.05129.
  3. Umut A Acar, Guy E Blelloch, and Robert Harper. Adaptive functional programming. In ACM Symposium on Principles of Programming Languages (POPL), 2002. Google Scholar
  4. Umut A Acar, Guy E Blelloch, Robert Harper, Jorge L Vittes, and Shan Leung Maverick Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004. Google Scholar
  5. Umut A Acar, Guy E Blelloch, and Jorge L Vittes. An experimental analysis of change propagation in dynamic trees. In Algorithm Engineering and Experiments (ALENEX), 2005. Google Scholar
  6. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms (TALG), 1(2):243-264, 2005. Google Scholar
  7. Pramod Bhatotia, Alexander Wieder, Rodrigo Rodrigues, Umut A. Acar, and Rafael Pasquini. Incoop: MapReduce for incremental computations. In ACM Symposium on Cloud Computing (SoCC), 2011. Google Scholar
  8. Guy E Blelloch, Jeremy T Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020. Google Scholar
  9. Tyson Condie, Neil Conway, Peter Alvaro, Joseph M. Hellerstein, Khaled Elmeleegy, and Russell Sears. Mapreduce online. In Symposium on Networked Systems Design and Implementation (NSDI), 2010. Google Scholar
  10. Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. Parallel batch-dynamic graphs: Algorithms and lower bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. Google Scholar
  11. Greg N Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 14(4):781-798, 1985. Google Scholar
  12. Joseph Gil, Yossi Matias, and Uzi Vishkin. Towards a theory of nearly constant time parallel algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS), 1991. Google Scholar
  13. Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. A top-down parallel semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015. Google Scholar
  14. Pradeep Kumar Gunda, Lenin Ravindranath, Chandramohan A. Thekkath, Yuan Yu, and Li Zhuang. Nectar: Automatic management of data and computation in data centers. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2010. Google Scholar
  15. Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502-516, 1999. Google Scholar
  16. Giuseppe F Italiano, Silvio Lattanzi, Vahab S Mirrokni, and Nikos Parotsidis. Dynamic algorithms for the massively parallel computation model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019. Google Scholar
  17. Joseph JáJá. An Introduction to Parallel Algorithms, volume 17. Addison-Wesley Reading, 1992. Google Scholar
  18. Donald B Johnson and Panagiotis Metaxas. Optimal algorithms for the vertex updating problem of a minimum spanning tree. In International Parallel Processing Symposium (IPPS), 1992. Google Scholar
  19. David R Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, 2000. Google Scholar
  20. Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, October 1985. Google Scholar
  21. Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. In Randomness and Computation, pages 47-72. JAI Press, Greenwich, Connecticut, 1989. Vol. 5. Google Scholar
  22. Gary L. Miller and John H. Reif. Parallel tree contraction part 2: Further applications. SIAM Journal on Computing, 20(6):1128-1147, 1991. Google Scholar
  23. Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Martín Abadi. Naiad: A timely dataflow system. In ACM Symposium on Operating Systems Principles (SOSP), 2013. Google Scholar
  24. Daniel Peng and Frank Dabek. Large-scale incremental processing using distributed transactions and notifications. In Symposium on Operating Systems Design and Implementation (OSDI), 2010. Google Scholar
  25. John H Reif and Stephen R Tate. Dynamic parallel tree contraction. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 1994. Google Scholar
  26. Natcha Simsiri, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Work-efficient parallel union-find with applications to incremental graph connectivity. In European Conference on Parallel Processing (Euro-Par), 2016. Google Scholar
  27. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. Google Scholar
  28. Robert E Tarjan and Renato F Werneck. Self-adjusting top trees. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005. Google Scholar
  29. Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. Batch-parallel Euler tour trees. In Algorithm Engineering and Experiments (ALENEX), 2019. Google Scholar
  30. Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33:103-111, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail