Adaptive Massively Parallel Connectivity in Optimal Space

Rustam Latypov; Jakub Łacki; Yannic Maus; Jara Uitto

doi:10.1145/3558481.3591103

Adaptive Massively Parallel Connectivity in Optimal Space

Rustam Latypov, Jakub Łacki, Yannic Maus, Jara Uitto

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

26 Downloads (Pure)

Abstract

We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.

Original language	English
Title of host publication	SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	ACM
Pages	431-441
Number of pages	11
ISBN (Electronic)	978-1-4503-9545-8
DOIs	https://doi.org/10.1145/3558481.3591103
Publication status	Published - 17 Jun 2023
MoE publication type	A4 Conference publication
Event	Annual ACM Symposium on Parallelism in Algorithms and Architectures - Orlando, United States Duration: 17 Jun 2023 → 19 Jun 2023 Conference number: 35

Conference

Conference	Annual ACM Symposium on Parallelism in Algorithms and Architectures
Abbreviated title	SPAA
Country/Territory	United States
City	Orlando
Period	17/06/2023 → 19/06/2023

Keywords

adaptive massively parallel model
ampc
connectivity

Access to Document

10.1145/3558481.3591103Licence: CC BY

SCI_Latypov_etal_SPAA_2023Final published version, 736 KBLicence: CC BY

Cite this

@inproceedings{5bd9a0899dad412b99d4332bac03a4b0,

title = "Adaptive Massively Parallel Connectivity in Optimal Space",

abstract = "We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.",

keywords = "adaptive massively parallel model, ampc, connectivity",

author = "Rustam Latypov and Jakub {\L}acki and Yannic Maus and Jara Uitto",

note = "Funding Information: Supported by the Academy of Finland, Grant 334238 Publisher Copyright: {\textcopyright} 2023 Owner/Author.; Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ; Conference date: 17-06-2023 Through 19-06-2023",

year = "2023",

month = jun,

day = "17",

doi = "10.1145/3558481.3591103",

language = "English",

pages = "431--441",

booktitle = "SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "ACM",

address = "United States",

}

Latypov, R, Łacki, J, Maus, Y & Uitto, J 2023, Adaptive Massively Parallel Connectivity in Optimal Space. in SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp. 431-441, Annual ACM Symposium on Parallelism in Algorithms and Architectures, Orlando, Florida, United States, 17/06/2023. https://doi.org/10.1145/3558481.3591103

TY - GEN

T1 - Adaptive Massively Parallel Connectivity in Optimal Space

AU - Latypov, Rustam

AU - Łacki, Jakub

AU - Maus, Yannic

AU - Uitto, Jara

N1 - Conference code: 35

PY - 2023/6/17

Y1 - 2023/6/17

N2 - We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.

AB - We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in O(log∗n) rounds in forests (with high probability) and 2O(log∗n) expected rounds in general graphs. This improves upon an existing O(log logm/nn) round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using I(m + n log(k) n) total space in expectation (in each round), where k is an arbitrarily large constant and log(k) is the k-th iterate of the log2 function. This improves upon existing algorithms requiring ω(m + n log n) total space.

KW - adaptive massively parallel model

KW - ampc

KW - connectivity

UR - http://www.scopus.com/inward/record.url?scp=85164284976&partnerID=8YFLogxK

U2 - 10.1145/3558481.3591103

DO - 10.1145/3558481.3591103

M3 - Conference article in proceedings

AN - SCOPUS:85164284976

SP - 431

EP - 441

BT - SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

PB - ACM

T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

Y2 - 17 June 2023 through 19 June 2023

ER -

Adaptive Massively Parallel Connectivity in Optimal Space

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this

Adaptive Massively Parallel Connectivity in Optimal Space

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this