Google Research

Adaptive Massively Parallel Connectivity in Optimal Space

SPAA'23 (2023)


We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when the total available space is linear in the size of the input graph the problem can be solved in O(log n) rounds in forests (with high probability) and 2^O(log n) expected rounds in general graphs. This improves upon an existing O(log log_(m/n) n) round algorithm.

For the case when the desired number of rounds is constant we show that both problems can be solved with only O(m + n log^(k) n) total space, 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 Omega(m + n log n) total space.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work