Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917674832887808 |
|---|---|
| author | Lingas, Andrzej |
| author_facet | Lingas, Andrzej |
| contents | We present a protocol for the Boolean matrix product of two $n\times b$ Boolean matrices on the congested clique designed for the situation when the rows of the first matrix or the columns of the second matrix are highly clustered in the space $\{0,1\}^n.$ With high probability (w.h.p), it uses $\tilde{O}\left(\sqrt {\frac M n+1}\right)$ rounds on the congested clique with $n$ nodes, where $M$ is the minimum of the cost of a minimum spanning tree (MST) of the rows of the first input matrix and the cost of an MST of the columns of the second input matrix in the Hamming space $\{0,1\}^n.$ A key step in our protocol is the computation of an approximate minimum spanning tree of a set of $n$ points in the space $\{0,1\}^n$. We provide a protocol for this problem (of interest in its own rights) based on a known randomized technique of dimension reduction in Hamming spaces. W.h.p., it constructs an $O(1)$-factor approximation of an MST of $n$ points in the Hamming space $\{ 0,\ 1\}^n$ using $O(\log^3 n)$ rounds on the congested clique with $n$ nodes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16103 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique Lingas, Andrzej Data Structures and Algorithms Distributed, Parallel, and Cluster Computing F.2.2 F.2.2 We present a protocol for the Boolean matrix product of two $n\times b$ Boolean matrices on the congested clique designed for the situation when the rows of the first matrix or the columns of the second matrix are highly clustered in the space $\{0,1\}^n.$ With high probability (w.h.p), it uses $\tilde{O}\left(\sqrt {\frac M n+1}\right)$ rounds on the congested clique with $n$ nodes, where $M$ is the minimum of the cost of a minimum spanning tree (MST) of the rows of the first input matrix and the cost of an MST of the columns of the second input matrix in the Hamming space $\{0,1\}^n.$ A key step in our protocol is the computation of an approximate minimum spanning tree of a set of $n$ points in the space $\{0,1\}^n$. We provide a protocol for this problem (of interest in its own rights) based on a known randomized technique of dimension reduction in Hamming spaces. W.h.p., it constructs an $O(1)$-factor approximation of an MST of $n$ points in the Hamming space $\{ 0,\ 1\}^n$ using $O(\log^3 n)$ rounds on the congested clique with $n$ nodes. |
| title | Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing F.2.2 F.2.2 |
| url | https://arxiv.org/abs/2405.16103 |