Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique

Lingas, Andrzej LU (2024) 30th International Conference on Parallel and Distributed Computing, Euro-Par 2024 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14803 LNCS. p.45-58
Abstract

We present a protocol for the Boolean matrix product of two n×n 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 O~Mn+1 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... (More)

We present a protocol for the Boolean matrix product of two n×n 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 O~Mn+1 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(log3n) rounds on the congested clique with n nodes.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Boolean matrix product, congested clique, Hamming space, minimum spanning tree (MST)
host publication
Euro-Par 2024 : Parallel Processing - 30th European Conference on Parallel and Distributed Processing, Proceedings - Parallel Processing - 30th European Conference on Parallel and Distributed Processing, Proceedings
series title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
editor
Carretero, Jesus ; Garcia-Blas, Javier ; Shende, Sameer ; Brandic, Ivona ; Olcoz, Katzalin and Schreiber, Martin
volume
14803 LNCS
pages
14 pages
publisher
Springer Science and Business Media B.V.
conference name
30th International Conference on Parallel and Distributed Computing, Euro-Par 2024
conference location
Madrid, Spain
conference dates
2024-08-26 - 2024-08-30
external identifiers
  • scopus:85202786151
ISSN
0302-9743
1611-3349
ISBN
9783031695827
DOI
10.1007/978-3-031-69583-4_4
language
English
LU publication?
yes
id
a92e984e-c267-4f87-af68-3d897c1ee725
date added to LUP
2024-12-13 15:00:15
date last changed
2025-05-03 01:20:27
@inproceedings{a92e984e-c267-4f87-af68-3d897c1ee725,
  abstract     = {{<p>We present a protocol for the Boolean matrix product of two n×n 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}<sup>n</sup>. With high probability (w.h.p), it uses O~Mn+1 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}<sup>n</sup>. 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}<sup>n</sup>. 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}<sup>n</sup> using O(log<sup>3</sup>n) rounds on the congested clique with n nodes.</p>}},
  author       = {{Lingas, Andrzej}},
  booktitle    = {{Euro-Par 2024 : Parallel Processing - 30th European Conference on Parallel and Distributed Processing, Proceedings}},
  editor       = {{Carretero, Jesus and Garcia-Blas, Javier and Shende, Sameer and Brandic, Ivona and Olcoz, Katzalin and Schreiber, Martin}},
  isbn         = {{9783031695827}},
  issn         = {{0302-9743}},
  keywords     = {{Boolean matrix product; congested clique; Hamming space; minimum spanning tree (MST)}},
  language     = {{eng}},
  pages        = {{45--58}},
  publisher    = {{Springer Science and Business Media B.V.}},
  series       = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
  title        = {{Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique}},
  url          = {{http://dx.doi.org/10.1007/978-3-031-69583-4_4}},
  doi          = {{10.1007/978-3-031-69583-4_4}},
  volume       = {{14803 LNCS}},
  year         = {{2024}},
}