A Surprisingly Simple Method for Distributed Euclidean-Minimum Spanning Tree / Single Linkage Dendrogram Construction from High Dimensional Embeddings via Distance Decomposition

我们介绍了一种分解方法，用于在高维空间中（其中次二次算法无效）或更一般的完全图的几何最小生成树的分布式计算。在该图$G=(V,E)$中，每个顶点$v\in V$由向量$\vec{v}\in \mathbb{R}^n$表示，对于任何边，图中的边的权重由代表向量之间的对称二进制“距离”函数给出$w(\{x,y\}) = d(\vec{x},\vec{y})$。这是由神经网络产生的高维嵌入聚类任务激发出来的，其中低维算法无效；这些几何最小生成树在单连通性树状图的构建中作为子程序应用，因为两种结构可以有效地相互转换。

论文旨在提出一种分解方法，用于在高维空间中分布计算精确的欧几里得最小生成树或更广义的几何最小生成树。这解决了在高维空间中使用低维算法无效的问题，为神经网络嵌入聚类提供了一种有效的解决方案。

论文提出了一种分解方法，用于在高维空间中分布计算精确的欧几里得最小生成树或更广义的几何最小生成树。这种方法可以有效地解决在高维空间中使用低维算法无效的问题。

论文的亮点包括提出一种有效的解决方案来解决高维空间中的聚类问题，以及提出一种新的分解方法来计算精确的欧几里得最小生成树或更广义的几何最小生成树。实验结果表明，该方法在高维空间中表现出色。

最近的相关研究包括“Fast Euclidean minimum spanning tree computation”和“Approximate Euclidean minimum spanning trees”。