Towards Scalable and Practical Batch-Dynamic Connectivity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915024680779776 |
|---|---|
| author | De Man, Quinten Dhulipala, Laxman Karczmarz, Adam Łącki, Jakub Shun, Julian Wang, Zhongqi |
| author_facet | De Man, Quinten Dhulipala, Laxman Karczmarz, Adam Łącki, Jakub Shun, Julian Wang, Zhongqi |
| contents | We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem which is work-efficient, supports batches of updates, runs in polylogarithmic depth, and uses only linear total space. The existing algorithms for the problem either use super-linear space, do not come with strong theoretical bounds, or are not parallel. On the empirical side, we provide the first implementation of the cluster forest algorithm, the first linear-space and poly-logarithmic update time algorithm for dynamic connectivity. Experimentally, we find that our algorithm uses up to 19.7x less space and is up to 6.2x faster than the level-set algorithm of HDT, arguably the most widely-implemented dynamic connectivity algorithm with strong theoretical guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11781 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Scalable and Practical Batch-Dynamic Connectivity De Man, Quinten Dhulipala, Laxman Karczmarz, Adam Łącki, Jakub Shun, Julian Wang, Zhongqi Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem which is work-efficient, supports batches of updates, runs in polylogarithmic depth, and uses only linear total space. The existing algorithms for the problem either use super-linear space, do not come with strong theoretical bounds, or are not parallel. On the empirical side, we provide the first implementation of the cluster forest algorithm, the first linear-space and poly-logarithmic update time algorithm for dynamic connectivity. Experimentally, we find that our algorithm uses up to 19.7x less space and is up to 6.2x faster than the level-set algorithm of HDT, arguably the most widely-implemented dynamic connectivity algorithm with strong theoretical guarantees. |
| title | Towards Scalable and Practical Batch-Dynamic Connectivity |
| topic | Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2411.11781 |