Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a cutting-edge lecture on Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree problems. Delve into the latest advancements in distributed algorithms for clustering large-scale, high-dimensional datasets. Learn about the challenges of solving Euclidean Minimum Spanning Tree (MST) problems in the Massively Parallel Computation (MPC) model and discover a novel approach that achieves a constant factor approximation in O~(loglogn) rounds. Understand the limitations of previous tree-embedding methods and how the presented algorithm combines graph-based distributed MST algorithms with geometric space partitions to overcome these constraints. Gain insights into the application of this technique to the Euclidean Traveling Salesman Problem (TSP), achieving a significant improvement in round complexity. This talk, presented by Peilin Zhong from Google, offers valuable knowledge for researchers and practitioners working with massive transformer-based embeddings and other high-dimensional data clustering challenges.
Syllabus
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Taught by
Simons Institute
Related Courses
计算几何 | Computational GeometryTsinghua University via edX Geometric Algorithms
EIT Digital via Coursera Computational Geometry
Saint Petersburg State University via Coursera Computational Geometry
Indian Institute of Technology Delhi via Swayam Computational Geometry
NPTEL via YouTube