Fast and Compact Sketch-Based Dynamic Connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915500569657344 |
|---|---|
| author | De Man, Quinten Jafri, Qamber Delayo, Daniel West, Evan T. Bender, Michael A. Tench, David |
| author_facet | De Man, Quinten Jafri, Qamber Delayo, Daniel West, Evan T. Bender, Michael A. Tench, David |
| contents | We study the dynamic connectivity problem for massive, dense graphs. Our goal is to build a system for dense graphs that simultaneously answers connectivity queries quickly, maintains a fast update throughput, and a uses a small amount of memory. Existing systems at best achieve two of these three performance goals at once.
We present a parallel dynamic connectivity algorithm using graph sketching techniques that has space complexity $O(V \log^3 V)$ and query complexity $O(\log V/\log\log V)$. Its updates are fast and parallel: in the worst case, it performs updates in $O(\log^2 V)$ depth and $O(\log^4 V)$ work. For updates which don't change the spanning forests maintained by our data structure, the update complexity is $O(\log V)$ depth and $O(\log^2 V)$ work.
We also present CUPCaKE (Compact Updating Parallel Connectivity and Sketching Engine), a dynamic connectivity system based on our parallel algorithm. It uses an order of magnitude less memory than the best lossless systems on dense graph inputs, answers queries with microsecond latency, and ingests millions of updates per second on dense graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast and Compact Sketch-Based Dynamic Connectivity De Man, Quinten Jafri, Qamber Delayo, Daniel West, Evan T. Bender, Michael A. Tench, David Data Structures and Algorithms We study the dynamic connectivity problem for massive, dense graphs. Our goal is to build a system for dense graphs that simultaneously answers connectivity queries quickly, maintains a fast update throughput, and a uses a small amount of memory. Existing systems at best achieve two of these three performance goals at once. We present a parallel dynamic connectivity algorithm using graph sketching techniques that has space complexity $O(V \log^3 V)$ and query complexity $O(\log V/\log\log V)$. Its updates are fast and parallel: in the worst case, it performs updates in $O(\log^2 V)$ depth and $O(\log^4 V)$ work. For updates which don't change the spanning forests maintained by our data structure, the update complexity is $O(\log V)$ depth and $O(\log^2 V)$ work. We also present CUPCaKE (Compact Updating Parallel Connectivity and Sketching Engine), a dynamic connectivity system based on our parallel algorithm. It uses an order of magnitude less memory than the best lossless systems on dense graph inputs, answers queries with microsecond latency, and ingests millions of updates per second on dense graphs. |
| title | Fast and Compact Sketch-Based Dynamic Connectivity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.14433 |