Logo image
Back
Sublinear-time Sampling of Spanning Trees in the Congested Clique
Preprint   Open access

Sublinear-time Sampling of Spanning Trees in the Congested Clique

Sriram V Pemmaraju, Sourya Roy and Joshua Z Sobel
ArXiV.org
Cornell University
11/20/2024
DOI: 10.48550/arxiv.2411.13334
url
https://doi.org/10.48550/arxiv.2411.13334View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We present the first sublinear round algorithm for approximately sampling uniform spanning trees in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ(n0.658) rounds for sampling a spanning tree from a distribution within total variation distance 1/nc, for arbitrary constant c>0, from the uniform distribution. More precisely, our algorithm requires Õ(n1/2+α) rounds, where O(nα) is the running time of matrix multiplication in the CongestedClique model, currently at α=1−2/ω=0.158, where ω is the sequential matrix multiplication time exponent. In addition, we show how to take somewhat shorter random walks even more efficiently in the CongestedClique model. Specifically, we show how to construct length-τ walks, for τ=Ω(n/logn), in O(τnlogτlogn) rounds and for τ=O(n/logn) in O(logτ) rounds. This implies an O(log3n)-round algorithm in the CongestedClique model for sampling spanning trees for Erdős-Rényi graphs and regular expander graphs due to the O(nlogn) bound on their cover time. This also implies that polylogarithmic-length walks, which are useful for page rank estimation, can be constructed in O(loglogn) rounds in the CongestedClique model. These results are obtained by adding a load balancing component to the random walk algorithm of Bahmani, Chakrabarti and Xin (SIGMOD 2011) that uses the ``doubling'' technique.
Computer Science - Distributed, Parallel, and Cluster Computing

Details

Metrics

7 Record Views
Logo image