FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data

We present Fast Approximate Minimum Spanning Tree (FAMST), a novel algorithm that addresses the computational challenges of constructing Minimum Spanning Trees (MSTs) for large-scale and high-dimensional datasets. FAMST utilizes a three-phase approach: Approximate Nearest Neighbor (ANN) graph construction, ANN inter-component connection, and iterative edge refinement. For a dataset of n points in a d-dimensional space, FAMST achieves O(dn log n) time complexity and O(dn + kn) space complexity when k nearest neighbors are considered, which is a significant improvement over the O(n2) time and space complexity of traditional methods. Experiments across diverse datasets demonstrate that FAMST achieves remarkably low approximation errors while providing speedups of up to 1000× compared to exact MST algorithms. We analyze how the key hyperparameters, k (neighborhood size) and λ (inter-component edges), affect performance, providing practical guidelines for hyperparameter selection. FAMST enables MST-based analysis on datasets with millions of points and thousands of dimensions, extending the applicability of MST techniques to problem scales previously considered infeasible.