Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914778584186880 |
|---|---|
| author | Liu, Quanquan C. Seshadhri, C. |
| author_facet | Liu, Quanquan C. Seshadhri, C. |
| contents | In this short note, we give a novel algorithm for $O(1)$ round triangle counting in bounded arboricity graphs. Counting triangles in $O(1)$ rounds (exactly) is listed as one of the interesting remaining open problems in the recent survey of Im et al. [IKLMV23]. The previous paper of Biswas et al. [BELMR20], which achieved the best bounds under this setting, used $O(\log \log n)$ rounds in sublinear space per machine and $O(mα)$ total space where $α$ is the arboricity of the graph and $n$ and $m$ are the number of vertices and edges in the graph, respectively. Our new algorithm is very simple, achieves the optimal $O(1)$ rounds without increasing the space per machine and the total space, and has the potential of being easily implementable in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00262 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Massively Parallel Triangle Counting in $O(1)$ Rounds Liu, Quanquan C. Seshadhri, C. Data Structures and Algorithms Distributed, Parallel, and Cluster Computing In this short note, we give a novel algorithm for $O(1)$ round triangle counting in bounded arboricity graphs. Counting triangles in $O(1)$ rounds (exactly) is listed as one of the interesting remaining open problems in the recent survey of Im et al. [IKLMV23]. The previous paper of Biswas et al. [BELMR20], which achieved the best bounds under this setting, used $O(\log \log n)$ rounds in sublinear space per machine and $O(mα)$ total space where $α$ is the arboricity of the graph and $n$ and $m$ are the number of vertices and edges in the graph, respectively. Our new algorithm is very simple, achieves the optimal $O(1)$ rounds without increasing the space per machine and the total space, and has the potential of being easily implementable in practice. |
| title | Improved Massively Parallel Triangle Counting in $O(1)$ Rounds |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2405.00262 |