Skip to main navigation Skip to search Skip to main content

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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 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.

Original languageEnglish
Title of host publicationEuro-Par 2024
Subtitle of host publicationParallel Processing - 30th European Conference on Parallel and Distributed Processing, Proceedings
Editors/authorsJesus Carretero, Javier Garcia-Blas, Sameer Shende, Ivona Brandic, Katzalin Olcoz, Martin Schreiber
PublisherSpringer Science and Business Media B.V.
Pages45-58
Number of pages14
ISBN (Print)9783031695827
DOIs
Publication statusPublished - 2024
Event30th International Conference on Parallel and Distributed Computing, Euro-Par 2024 - Madrid, Spain
Duration: 2024 Aug 26 → 2024 Aug 30

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14803 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International Conference on Parallel and Distributed Computing, Euro-Par 2024
Country/TerritorySpain
CityMadrid
Period2024/08/26 → 2024/08/30

Subject classification (UKÄ)

  • Computer Sciences

Free keywords

  • Boolean matrix product
  • congested clique
  • Hamming space
  • minimum spanning tree (MST)

Fingerprint

Dive into the research topics of 'Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique'. Together they form a unique fingerprint.

Cite this