快速构建高维大数据的近似最小生成树，提速千倍且误差极小。
FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
- 分三阶段：近邻图构建、组件连接、边迭代优化。
- 百万级点、千维数据下速度提升1000倍，误差低。
- 适合大规模高维数据的聚类与图分析任务。
我们提出一种新型算法 FAMST，用于解决大规模高维数据构建最小生成树（MST）的计算难题。FAMST 采用三阶段策略：近似最近邻（ANN）图构建、ANN 组件间连接、迭代边优化。对于 $n$ 个 $d$ 维空间中的点，当考虑 $k$ 个最近邻时，其时间复杂度为 $/mathcal{O}(dn \log n)$，空间复杂度为 $/mathcal{O}(dn + kn)$，显著优于传统方法的 $/mathcal{O}(n^2)$ 时间与空间复杂度。在多种数据集上的实验表明，FAMST 在保持极低近似误差的同时，相较精确 MST 算法实现高达 1000 倍的加速。我们分析了关键超参数 $k$（邻域大小）和 $λ$（组件间边数）对性能的影响，提供实用的调参指导。该方法使基于 MST 的分析可扩展至百万级点与千维数据，将 MST 技术的应用范围拓展到此前被认为不可行的问题规模。
原文摘要 · Abstract (English)
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 $\mathcal{O}(dn \log n)$ time complexity and $\mathcal{O}(dn + kn)$ space complexity when $k$ nearest neighbors are considered, which is a significant improvement over the $\mathcal{O}(n^2)$ 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$\times$ 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。