We introduce MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. MOJOS yields the first theoretically-efficient batch-parallel link-cut tree, the first batch-dynamic data structure supporting path queries to achieve O(log n) depth for batch updates, and a new batch-parallel Euler tour tree that outperforms prior implementations.

We introduce hybrid sketching for dynamic connectivity: sketch dense graph cores and store sparse peripheries losslessly. Our HybridSCALE system is the first sketch-based dynamic connectivity implementation to save space on sparse real-world graphs.

We present a new parallel batch-dynamic tree data structure called UFO trees which supports a wide range of query functionality and supports efficient batch-parallel updates. Our results show that in both sequential and parallel settings, UFO trees are the fastest dynamic tree data structure that supports a wide range of queries.

This paper describes a parallel dynamic graph sketching algorithms for graph connectivity. Our system, CUPCaKE, can rapidly process massive and dense dynamic graphs while using significantly less memory than existing systems.

This paper is the first to study dynamic single-linkage dendrogram (SLD) maintenance. We introduce novel sequential and batch-parallel algorithms that can update the SLD faster than recomputing it from scratch.

We present the first parallel algorithm for batch-dynamic graph connectivity that is work-efficient, uses linear space, and handles updates in polylogarithmic time. We study the performance of the cluster forest algorithm sequentially.

This paper is a workshop version of the conference paper of the same name.

For BFS, we describe several performance engineering techniques for real-world graphs. For SSSP, we introduce a contraction based preprocessing method which significantly speeds up queries on high diameter graphs.