betaFeedback

WorksComputer Science

Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces

Abstract

We develop a unified algorithmic framework for computing approximate minimum spanning trees (MSTs) in metric spaces in the fully scalable Massively Parallel Computation (MPC) model. Using this framework, we obtain the following results for any fixed constant σ∈(0,1)σ\in(0,1): - General metrics: Given all pairwise distances, we compute a (1+ε)(1+\varepsilon)-approximate MST in O(log⁡(1/ε))O(\log(1/\varepsilon)) rounds using nσn^σ local space per machine and O~(n2)\widetilde{O}(n^2) total space. - Euclidean spaces: Given nn points in Rd\mathbb{R}^d, we compute an O(1/σ4)O(1/σ^4)-approximate MST in O(1)O(1) rounds using (nd)σ(nd)^σ local space per machine and O(nd+n1+σ)O(nd+n^{1+σ}) total space. - Doubling metrics: Given nn points in a metric of doubling dimension ddim=O(σlog⁡n)\mathrm{ddim}=O(σ\log n), we compute an O(1/σ)O(1/σ)-approximate MST in O(ddim/σ4)O(\mathrm{ddim}/σ^4) rounds using nσn^σ local space per machine and O~(n1+σ)⋅2O(ddim)\widetilde{O}(n^{1+σ})\cdot 2^{O(\mathrm{ddim})} total space. For any fixed constant ε∈(0,1)\varepsilon\in(0,1), these results give the first constant-round MPC algorithms achieving (1+ε)(1+\varepsilon)-approximation in general metrics and O(1)O(1)-approximation in a high-dimensional Euclidean space, respectively. They improve upon the O(log⁡log⁡n+log⁡(1/ε))O(\log\log n+\log(1/\varepsilon))-round algorithm for general metrics [SODA'25] and the O(log⁡log⁡n⋅log⁡log⁡log⁡n)O(\log\log n\cdot\log\log\log n)-round algorithm for Euclidean spaces [SODA'24], respectively. Moreover, our round complexity for general metrics is asymptotically optimal in its dependence on ε\varepsilon, matching the Ω(log⁡(1/ε))Ω(\log(1/\varepsilon)) lower bound of [SODA'25] under the 1-vs-2-cycles conjecture. Our result also answers an open question raised by [STOC'23].

Introduction

In this paper, we study the minimum spanning tree (MST) problem in metric spaces, which is one of the fundamental problems in computer science. Given a set of points and their pairwise distances, the goal is to compute a spanning tree of minimum total weight in the complete graph on the point set, where the weight of each edge is the distance between its endpoints. The MST problem has been extensively studied, giving rise to a rich body of algorithmic techniques. A central application is hierarchical clustering: removing the edges of an MST in decreasing order of weight progressively partitions the point set into clusters [41, 53]. In particular, MST-based clustering has been used to identify structures in astronomical data [41, 3] and to cluster high-dimensional datasets in machine learning [38]. MSTs also find applications in biology [49 YTW+20, 48] as well as in representation learning [29, 39, 40].

Such applications often involve processing large data sets. This motivates the use of modern distributed computing frameworks such as MapReduce, Spark, Hadoop, and Dryad [22, 21, 50, 31]. Although their implementations differ, these systems must coordinate computation across many machines, and the resulting communication overhead can significantly affect algorithmic efficiency. The Massively Parallel Computation (MPC) model, introduced in [36], has become a central theoretical framework for capturing the algorithmic challenges in these systems. Over the past decade, various algorithmic problems including the MST problem have been extensively studied in the MPC model [1, 5, 8, 11, 24, 53].

In the MPC model, the input of NN words is distributed across mm machines, each with ss words of local memory, giving a total memory of m⋅sm \cdot s words. Computation proceeds in synchronous rounds of local computation and communication. In each round, each machine can perform unrestricted local computation within its memory bound, and then send and receive O(s)O(s) words. The primary complexity measures of an MPC algorithm are its round complexity, local memory ss, and the total space m⋅sm \cdot s. In this work, we consider the fully scalable regime where s=Nσs = N^\sigma for an arbitrary fixed constant σ∈(0,1)\sigma\in(0, 1). Our goal is to minimize the number of rounds, ideally achieving O(1)O(1) rounds, while keeping the total space as small as possible.

We focus on the metric MST problem in the fully scalable MPC model. Since a metric induces a complete edge-weighted graph, a natural approach is to apply MPC algorithms for MSTs in general graphs. For general edge-weighted graphs, an exact MST can be computed in O(log⁡n)O(\log n) rounds in the fully scalable regime [4, 6, 11]. However, under the 1-vs-2-cycles conjecture, even computing an approximate MST in a general edge-weighted graph requires Ω(log⁡n)\Omega(\log n) rounds.1 This barrier has motivated extensive work on MPC algorithms for MSTs in more structured settings, particularly metric spaces, including Euclidean and doubling metrics [2, 28, 17, 1, 35]. A natural question in this direction is whether approximate MSTs can be computed in o(log⁡n)o(\log n) rounds by exploiting metric structure.

Although Euclidean MST is a special case of metric MST, their input representations differ significantly in the MPC model. Our goal is to keep the total space close to linear in the input size. In the general metric setting, all pairwise distances are explicitly given, resulting in an input size of N=Θ(n2)N = \Theta(n^2). In contrast, in the Euclidean setting, the input consists of the coordinates of nn points in Rd\mathbb{R}^d, requiring only Θ(nd)\Theta(nd) words. In the doubling metric setting, we assume that each point has an O(1)O(1)-word representation from which pairwise distances can be computed locally, resulting in an input size of Θ(n)\Theta(n). Therefore, directly applying MPC algorithms for general metrics to Euclidean and doubling metric spaces may not achieve the desired total space complexity.

Previous work. We review the best-known prior MPC results for MSTs in various metric settings. In the following, we sometimes treat σ\sigma and ε\varepsilon as fixed constants. Instead, we indicate any hidden dependence on these parameters by subscripts in the O(⋅)O(\cdot) notation.

For low-dimensional Euclidean spaces, Andoni, Nikolov, Onak, and Yaroslavtsev [2] presented a randomized Oσ(1)O_{\sigma}(1)-round MPC algorithm that constructs a (1+ε)(1+\varepsilon)-approximate MST in expectation using linear total space. This result also extends to doubling metrics without increasing the round complexity and the total space complexity. Although they state their results for the O(1)O(1)-dimensional case, their analysis also applies to higher dimensions: d=Oε(σlog⁡n/log⁡log⁡n)d = O_{\varepsilon}(\sigma\log n / \log\log n) in Euclidean spaces and ddim⁡=Oε(σlog⁡n)\operatorname{ddim} = O_{\varepsilon}(\sqrt{\sigma\log n}) in doubling metrics, using O(nσ)O(n^{\sigma}) local space.2 As long as the dimensions are within these ranges, the dependence on the dimension in the round complexity and the total space complexity is linear.

For high-dimensional Euclidean spaces, [12] presented an MPC algorithm that estimates the MST cost within a factor of (1+ε)(1+\varepsilon) in Oσ,ε(1)O_{\sigma,\varepsilon}(1) rounds using O(nd)O(nd) total space. However, their algorithm does not construct an actual spanning tree. In fact, constructing a constant-factor approximate MST in high-dimensional Euclidean spaces was more challenging; previously, it could be constructed in Oσ(log⁡n)O_{\sigma}(\log n) rounds by constructing a sparse Euclidean spanner and then applying an MPC algorithm for MSTs in general graphs. Jayaram, Mirrokni, Narayanan, and Zhong [35] broke this O(log⁡n)O(\log n) barrier by presenting an Oσ(log⁡log⁡n⋅log⁡log⁡log⁡n)O_{\sigma}(\log\log n \cdot\log\log\log n)-round MPC algorithm that constructs an Oσ(1)O_{\sigma}(1)-approximate MST using O(nd+n1+σ)O(nd+n^{1+\sigma}) total space.

For general metric spaces, [1] gave a randomized Oσ(log⁡(1/ε)+log⁡log⁡n)O_{\sigma}(\log(1/\varepsilon)+\log\log n)-round MPC algorithm that constructs a (1+ε)(1+\varepsilon)-approximate MST using O~(n2)\widetilde{O}(n^2) total space. The total space is thus near-linear in the input size. Under the 1-vs-2-cycles conjecture, they also proved that any MPC algorithm with n1−Ω(1)n^{1-\Omega(1)} local space and polynomial total space requires Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)) rounds to construct a (1+ε)(1+\varepsilon)-approximate MST in a general metric space, for 1/n≤ε≤11/n \le\varepsilon\le1.

Despite recent progress on MPC algorithms for metric MSTs, the best-known algorithms for constructing approximate MSTs in general metrics and high-dimensional Euclidean spaces still require a super-constant number of rounds for fixed ε\varepsilon. This raises the following question, which was also explicitly posed in [12, 32]:

Can one construct approximate MSTs in both general metric spaces and high-dimensional Euclidean spaces in O(1)O(1) rounds in the fully scalable MPC model, while maintaining the approximation ratios of the previous best-known algorithms?

Our contributions. We answer this question affirmatively by developing a unified algorithmic framework for constructing approximate MSTs in general metric spaces and high-dimensional Euclidean spaces. In particular, we improve the round complexities of the algorithms of [35] and of [1] without increasing the total space complexities and the approximation ratios. This framework also applies to doubling metric spaces. Specifically, we prove the following theorems.

Theorem 1.1. Fix two parameters σ∈(0,1)\sigma\in(0,1) and ε∈(0,1)\varepsilon\in(0,1). There is an O(log⁡(1/(εσ))/σ2)O(\log(1/(\varepsilon\sigma))/\sigma^2)-round randomized MPC algorithm that, given all pairwise distances of an nn-point metric (X,dist⁡)(X,\operatorname{dist}), returns a spanning tree of XX whose total weight is at most (1+ε)(1+\varepsilon) times the weight of a minimum spanning tree of (X,dist⁡)(X,\operatorname{dist}). The algorithm succeeds with probability at least 1−n−Ω(1)1-n^{-\Omega(1)} and uses nσn^\sigma local space per machine and O~(n2)\widetilde{O}(n^2) total space.

Theorem 1.2. Fix a constant σ∈(0,1)\sigma\in(0,1). There is an O(1/σ2)O(1/\sigma^2)-round randomized MPC algorithm that, given a set PP of nn points in Rd\mathbb{R}^{d}, returns a spanning tree of PP whose total weight is O(1/σ4)O(1/\sigma^4) times the weight of a minimum spanning tree of PP. The algorithm succeeds with probability at least 1−n−Ω(1)1-n^{-\Omega(1)} and uses (dn)σ(dn)^{\sigma} local space per machine and O(nd+n1+σ)O(nd+n^{1+\sigma}) total space.

Theorem 1.3. Fix a constant σ∈(0,1)\sigma\in(0,1). There is an O(ddim⁡/σ4)O(\operatorname{ddim}/\sigma^4)-round randomized MPC algorithm that, given a set PP of nn points in a metric space with doubling dimension ddim⁡\operatorname{ddim} satisfying σlog⁡n≥Ω(ddim⁡)\sigma\log n\ge\Omega(\operatorname{ddim}), returns a spanning tree of PP whose total weight is O(1/σ)O(1/\sigma) times the weight of a minimum spanning tree of PP. The algorithm succeeds with probability at least 1−n−Ω(1)1-n^{-\Omega(1)} and uses nσn^{\sigma} local space per machine and O~(n1+σ)⋅2O(ddim⁡)\widetilde{O}(n^{1+\sigma})\cdot2^{O(\operatorname{ddim})} total space.

Table 1 compares our algorithms with previous MPC algorithms for metric MSTs. For general metrics, we remove the additive Oσ(log⁡log⁡n)O_{\sigma}(\log\log n) term in the round complexity of Azarmehr, Behnezhad, Jayaram, Łącki, Mirrokni, and Zhong [1]. For high-dimensional Euclidean spaces, we improve the Oσ(log⁡log⁡n⋅log⁡log⁡log⁡n)O_{\sigma}(\log\log n\cdot\log\log\log n)-round bound of Jayaram, Mirrokni, Narayanan, and Zhong [35] to Oσ(1)O_{\sigma}(1) rounds. For doubling metrics, we extend the dimension range from Oε(σlog⁡n)O_{\varepsilon}(\sqrt{\sigma\log n}) in [2] to O(σlog⁡n)O(\sigma\log n) while retaining Oσ(ddim⁡)O_{\sigma}(\operatorname{ddim}) rounds. On the other hand, the approximation ratio becomes Oσ(1)O_{\sigma}(1) while the approximation ratio of [2] is 1+ε1+\varepsilon.

MetricDimensionApproximationRoundsTotal spaceTree?Source
General—1+ε1+\varepsilonOσ(log⁡(1/ε)+log⁡log⁡n)O_{\sigma}(\log(1/\varepsilon)+\log\log n)O~(n2)\widetilde{O}(n^2)✓[1]
1+ε1+\varepsilonOσ(log⁡(1/ε))O_{\sigma}(\log(1/\varepsilon))O~(n2)\widetilde{O}(n^2)✓Theorem 1.1
Euclideand=O(1)d=O(1)1+ε1+\varepsilonOσ(1)O_{\sigma}(1)Oσ(n)O_{\sigma}(n)✓[2]
arbitrary dd1+ε1+\varepsilonOσ((1/ε)⋅log⁡(1/ε))O_{\sigma}((1/\varepsilon)\cdot\log(1/\varepsilon))O~(dn)\widetilde{O}(dn)—[12]
Oσ(1)O_{\sigma}(1)Oσ(log⁡log⁡n⋅log⁡log⁡log⁡n)O_{\sigma}(\log\log n\cdot\log\log\log n)O(nd+n1+σ)O(nd+n^{1+\sigma})✓[35]
Oσ(1)O_{\sigma}(1)Oσ(1)O_{\sigma}(1)O(nd+n1+σ)O(nd+n^{1+\sigma})✓Theorem 1.2
Doublingddim⁡=Oε(σlog⁡n)\operatorname{ddim}=O_{\varepsilon}(\sqrt{\sigma\log n})1+ε1+\varepsilonOσ(ddim⁡)O_{\sigma}(\operatorname{ddim})Oσ(n⋅ddim⁡)O_{\sigma}(n\cdot\operatorname{ddim})✓[2]
ddim⁡=O(σlog⁡n)\operatorname{ddim}=O(\sigma\log n)Oσ(1)O_{\sigma}(1)Oσ(ddim⁡)O_{\sigma}(\operatorname{ddim})O~(n1+σ)⋅2O(ddim⁡)\widetilde{O}(n^{1+\sigma})\cdot2^{O(\operatorname{ddim})}✓Theorem 1.3

Table 1. Comparison of previous and our results. The local space per machine is nσn^{\sigma} for general and doubling metrics and (nd)σ(nd)^{\sigma} for Euclidean spaces, except that [12] uses dO(1)nσd^{O(1)}n^{\sigma} local space. The sixth column with label “Tree?” indicates whether the algorithms return an actual spanning tree.

As an application, our algorithms also yield MPC algorithms for the traveling salesman problem (TSP) in metric spaces. Doubling the weight of an approximate MST immediately gives an estimate of the optimal TSP cost, with twice the approximation factor. We show how to compute an approximate TSP tour itself. The standard method doubles every tree edge, computes an Euler tour, and shortcuts repeated visits to each point. However, under the 1-vs-2-cycles conjecture, computing the traversal order of an arbitrary tree given only its edges requires Ω(log⁡n)\Omega(\log n) rounds in the worst case in the fully scalable MPC model [35]. We instead use a hierarchical structure of an approximate MST constructed during our MST algorithms to compute an Euler tour. This gives a (2+ε)(2+\varepsilon)-approximation in general metric spaces and an Oσ(1)O_{\sigma}(1)-approximation in Euclidean and doubling metric spaces, with high probability, without asymptotically increasing the round complexity, local space per machine, or total space of the corresponding MST algorithms. For details, see § 7.

Estimating the cost vs. Computing an actual tree. Beyond estimating the MST cost, our main contribution is to improve the round complexity for constructing approximate MSTs themselves in the MPC model. This distinction matters not only from an algorithmic perspective but also in applications that require the connections between points. For example, in hierarchical clustering, one can remove the edges of an MST (or an approximate MST) in decreasing order of weight to obtain a nested sequence of partitions of the points. The connected components after each removal determine which points belong to the same cluster at that level. An estimate of the MST cost alone does not identify the edges or the resulting clusters. Another example is network design. The edges of a spanning tree specify which pairs of sites to connect; an approximate MST provides such connections with a total weight within a provable factor of the minimum.

Conceptual contribution and main insights. A by-now-standard framework for estimating MST costs in sublinear models uses threshold graphs [18]. For a threshold tt, two points are adjacent in the threshold graph if their distance is at most tt. By Kruskal’s algorithm, the number of MST edges longer than tt is exactly one less than the number of connected components of the threshold graph at tt. Thus, by counting the connected components at thresholds 1,(1+ε),(1+ε)2,…1,(1+\varepsilon),(1+\varepsilon)^2,\ldots, we can determine how many MST edges have lengths between consecutive thresholds and use this information to estimate the MST cost. This approach has led to efficient algorithms in several sublinear models [18, 19, 13, 23, 12]. However, constructing an approximate MST is more challenging, since knowing the number of MST edges at each scale does not tell us which edges to include in the tree. Previous MPC algorithms for computing an approximate MST in metrics addressed this issue in this framework, but required a super-constant number of rounds [1, 35].

We instead take a different approach based on Prim’s algorithm, inspired by [47, 7]. In particular, [7] presented an O(1)O(1)-round adaptive MPC algorithm for computing an exact MST in a general graph based on Prim’s algorithm.3 This suggests a natural question: Can a Prim-based approach also be used to construct an approximate MST in fewer MPC rounds? We run truncated executions of Prim in parallel on small neighborhoods that fit on individual machines. The resulting forest serves as a building block for our algorithm, whose main insights are as follows.

  • By choosing appropriate stopping conditions, each truncated execution selects only edges belonging to a common MST of the input. Their union therefore forms a forest. However, this forest may contain very large trees or too many small trees.

  • Large trees may span many machines, making it difficult to identify their connected components. We overcome this problem by cutting edges so that each point can identify the root of its resulting tree locally.

  • Even when the forest contains many small trees, we can use sampling to merge them into fewer trees. The stopping conditions of the Prim executions allow us to bound the expected total weight of the edges added by this procedure by a constant factor of the MST cost.

References

  1. [1]Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Łącki, Vahab Mirrokni, and Peilin Zhong. Massively parallel minimum spanning tree in general metric spaces. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 143–174, 2025. doi:10.1137/1.9781611978322.5.DOI
  2. [2]Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 574–583, 2014. doi:10.1145/2591796.2591805.DOI
  3. [3]Mehmet Alpaslan, Aaron S. G. Robotham, Simon Driver, Peder Norberg, Ivan Baldry, Amanda E. Bauer, Joss Bland-Hawthorn, Michael Brown, Michelle Cluver, Matthew Colless, Caroline Foster, Andrew Hopkins, Eelco Van Kampen, Lee Kelvin, Maritza A. Lara-Lopez, Jochen Liske, Angel R. Lopez-Sanchez, Jon Loveday, Tamsyn McNaught-Roberts, Alexander Merson, and Kevin Pimbblet. Galaxy And Mass Assembly (GAMA): the large-scale structure of galaxies and comparison to mock universes. Monthly Notices of the Royal Astronomical Society, 438(1):177–194, 2014. doi:10.1093/mnras/stt2136.DOI
  4. [4]Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 674–685, 2018. doi:10.1109/FOCS.2018.00070.DOI
  5. [5]Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 461–470, 2019. doi:10.1145/3293611.3331596.DOI
  6. [6]Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni. Near-optimal massively parallel graph connectivity. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1615–1636, 2019. doi:10.1109/FOCS.2019.00095.DOI
  7. [7]Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni, and Warren Schudy. Parallel graph algorithms in constant adaptive rounds: theory meets practice. Proceedings of the VLDB Endowment, 13(13):3588–3602, 2020. doi:10.14778/3424573.3424579.DOI
  8. [8]Sujoy Bhore, Arnold Filtser, Eunjin Oh, Hyeonjun Shin, and Himanshi Singh. Geometric hashing in MPC with applications to clustering and stochastic embeddings, 2026. To appear in SODA 2027. arXiv:2610.21371, doi:10.48550/arXiv.2610.21371.
  9. [10]Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Optimal deterministic massively parallel connectivity on forests. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2589–2631, 2023. doi:10.1137/1.9781611977554.CH99.DOI
  10. [11]Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. SIAM Journal on Computing, 52(5):1269–1318, 2023. doi:10.1137/22M1520177.DOI
  11. [12]Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming Euclidean MST to a constant factor. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 156–169, 2023. doi:10.1145/3564246.3585168.DOI
  12. [13]Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, and Christian Sohler. Approximating the weight of the Euclidean minimum spanning tree in sublinear time. SIAM Journal on Computing, 35(1):91–109, 2005. doi:10.1137/S0097539703435297.DOI
  13. [14]Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing, 2023. Full version; a preliminary version appeared in FOCS 2022. arXiv:2204.02095, doi:10.48550/arXiv.2204.02095.arxiv.org/abs/2204.02095
  14. [15]Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-scalable MPC algorithms for clustering in high dimension. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages 50:1–50:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.50.DOI
  15. [16]Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 450–461, 2022. doi:10.1109/FOCS54457.2022.00050.DOI
  16. [17]Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional EMD and MST. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), pages 222–233, 2022. doi:10.1145/3519935.3519979.
  17. [18]Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370–1379, 2005. doi:10.1137/S0097539702403244.DOI
  18. [19]Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, 39(3):904–922, 2009. doi:10.1137/060672121.DOI
  19. [20]Yi-Jun Chang and Da Wei Zheng. Fully scalable massively parallel algorithms for embedded planar graphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 4410–4450, 2024. doi:10.1137/1.9781611977912.155.DOI
  20. [21]Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI 2004), pages 137–150, 2004. URL: https://www.usenix.org/conference/osdi-04/mapreduce-simplified-data-processing-large-clusters.
  21. [22]Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008. doi:10.1145/1327452.1327492.
  22. [23]Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff. Range counting oracles for geometric problems. In Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025), pages 42:1–42:16, 2025. doi:10.4230/LIPIcs.SoCG.2025.42.DOI
  23. [24]Mohsen Ghaffari. Massively parallel algorithms. Lecture Notes from ETH Zurich, 2019. URL: http://people.csail.mit.edu/ghaffari/MPA19/Notes/MPA.pdf.
  24. [25]Michael T. Goodrich. Communication-efficient parallel sorting. SIAM Journal on Computing, 29(2):416–432, 1999. doi:10.1137/S0097539795294141.DOI
  25. [26]Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1–29, 1968. doi:10.1137/0116001.DOI
  26. [27]Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the MapReduce framework. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), pages 374–383, 2011. doi:10.1007/978–3–642–25591–5_39.
  27. [28]Junhao Gan, Anthony Wirth, and Zhuo Zhang. O(1)-round MPC algorithms for multi-dimensional grid graph connectivity, Euclidean MST and DBSCAN. In Proceedings of the 28th International Conference on Database Theory (ICDT 2025), pages 7:1–7:20, 2025. doi:10.4230/LIPIcs.ICDT.2025.7.
  28. [29]Christoph Hofer, Florian Graf, Marc Niethammer, and Roland Kwitt. Topologically densified distributions. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), pages 4304–4313, 2020. URL: https://proceedings.mlr.press/v119/hofer20a.html.arxiv.org/abs/2002.04805
  29. [30]James W. Hegeman, Sriram V. Pemmaraju, and Vivek B. Sardeshmukh. Near-constant-time distributed algorithms on a Congested Clique. In Proceedings of the 28th International Symposium on Distributed Computing (DISC 2014), pages 514–530, 2014. doi:10.1007/978–3–662–45174–8_35.
  30. [31]Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 (EuroSys 2007), pages 59–72, 2007. doi:10.1145/1272996.1273005.
  31. [32]Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Weicheng Wang. Round-efficient fully-scalable MPC algorithms for k-means, 2026. arXiv:2604.00954, doi:10.48550/arXiv.2604.00954.
  32. [33]William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemporary Mathematics, pages 189–206, 1984. doi:10.1090/conm/026/737400.DOI
  33. [34]Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for TSP, Steiner tree, and set cover. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pages 386–395, 2005. doi:10.1145/1060590.1060649.DOI
  34. [35]Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 3960–3996, 2024. doi:10.1137/1.9781611977912.139.DOI
  35. [36]Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 938–948, 2010. doi:10.1137/1.9781611973075.76.DOI
  36. [37]Andrzej Lingas. Boolean matrix multiplication for highly clustered data on the Congested Clique. In Proceedings of the 30th European Conference on Parallel Processing (Euro-Par 2024), pages 45–58, 2024. doi:10.1007/978-3-031-69583-4_4.
  37. [38]Chih Lai, Taras Rafa, and Dwight E. Nelson. Approximate minimum spanning tree clustering in high-dimensional space. Intelligent Data Analysis, 13(4):575–597, 2009. doi:10.3233/IDA-2009-0382.DOI
  38. [39]Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), pages 7045–7054, 2020. URL: https://proceedings.mlr.press/v119/moor20a.html.arxiv.org/abs/1906.00722
  39. [40]Julie Mordacq, David Loiseaux, Vicky Kalogeiton, and Steve Oudot. T-REGS: minimum spanning tree regularization for self-supervised learning. In Proceedings of the 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025), pages 12184–12214, 2025. doi:10.52202/085713-0408.DOI
  40. [41]William B. March, Parikshit Ram, and Alexander G. Gray. Fast Euclidean minimum spanning tree: algorithm, analysis, and applications. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010), pages 603–612, 2010. doi:10.1145/1835804.1835882.DOI
  41. [42]Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear metric Steiner tree via improved bounds for set cover. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 74:1–74:24, 2025. doi:10.4230/LIPIcs.ITCS.2025.74.DOI
  42. [43]Krzysztof Nowicki. A deterministic algorithm for the MST problem in constant rounds of Congested Clique. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), pages 1154–1165, 2021. doi:10.1145/3406325.3451136.DOI
  43. [44]Dan upon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. Distributed Computing, 35(2):165–183, 2022. doi:10.1007/s00446-021-00418-2.DOI
  44. [45]Eunjin Oh and Hyeonjun Shin. Fully scalable MPC algorithms for WSPD in doubling and Euclidean spaces. In Proceedings of the 34th Annual European Symposium on Algorithms (ESA 2026), pages 88:1–88:16, 2026. doi:10.4230/LIPIcs.ESA.2026.88.DOI
  45. [46]Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-fast MST algorithms in the Congested Clique using o(m) messages. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), pages 47:1–47:15, 2016. doi:10.4230/LIPIcs.FSTTCS.2016.47.DOI
  46. [47]Gryphon Patlin and Jan van den Brand. Sublinear-time algorithm for MST-weight revisited. In Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA 2025), pages 46–53, 2025. doi:10.1137/1.9781611978315.3.DOI
  47. [48]Stephen-John Sammut, Jacob D. Galson, Ralph Minter, Bo Sun, Suet-Feung Chin, Leticia De Mattos-Arruda, Donna K. Finch, Sebastian Schätzle, Jorge Dias, Oscar M. Rueda, Joan Seoane, Jane Osbourn, Carlos Caldas, and Rachael J. M. Bashford-Rogers. Predictability of B cell clonal persistence and immunosurveillance in breast cancer. Nature Immunology, 25(5):916–924, 2024. doi:10.1038/s41590-024-01821-0.DOI
  48. [49]Cole Trapnell, Davide Cacchiarelli, Jonna Grimsby, Prapti Pokharel, Shuqiang Li, Michael Morse, Niall J. Lennon, Kenneth J. Livak, Tarjei S. Mikkelsen, and John L. Rinn. The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells. Nature Biotechnology, 32(4):381–386, 2014. doi:10.1038/nbt.2859.DOI
  49. [50]Tom White. Hadoop: the definitive guide. O’Reilly Media, Inc., 3rd edition, 2012. URL: https://www.oreilly.com/library/view/hadoop-the-definitive/9781449328917/.
  50. [51]Chilei Wang, Qiang-Sheng Hua, and Hai Jin. Massively parallel approximate Steiner tree algorithms. In Proceedings of the 31st International Computing and Combinatorics Conference (COCOON 2025), pages 110–124, 2025. doi:10.1007/978-981-95-0218-9_9.DOI
  51. [53]Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under ℓₚ distances. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), pages 5600–5609, 2018. URL: https://proceedings.mlr.press/v80/yaroslavtsev18a.html.arxiv.org/abs/1710.01431

Paper details

vlnc:W_stgya4cv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents