SODA 2026 | 大规模并行计算下的高维动态树嵌入算法

随机树嵌入（Probabilistic Tree Embedding）是一类基本的度量嵌入（Metric Embedding）技术，旨在将复杂的度量空间嵌入到随机的树度量空间中， 且保证嵌入的距离误差的期望尽可能小。 该技术首先被 Bartal 等人提出 [Bar96]，随后 Fakcharoenphol 等人 [FRT04] 证明，任意  点度量空间都可嵌入到随机树度量中并达到  的期望距离误差。可以证明这一结果在渐近意义下是最优的。

具体来说，树嵌入将任意  点度量空间  映射到树的叶子上（非叶子结点仅用于辅助定义树距离），满足树的所有叶子在同一层，同高度的节点到父亲的连边边权相等，且任何从叶子到根的路径的边权以  倍指数递增。 该树嵌入一般是随机的。设树上的距离是 ，则对于 ，如果满足下面的条件则称该随机树  的误差是  ：对任何  有

1.   和

2.    。

在高维欧式空间  中，即  ，许多基本组合优化问题都属于难解问题，如旅行商问题（TSP）[Tre00]、k-Median [ACKS15] 等问题均被证明是 APX-Hard 的。 树嵌入对于高维欧氏空间也适用，并且由于树嵌入上的树距离具有简单的结构，这些难解组合优化问题普遍存在树上的高效的高精度算法。因此，如果能高效地将高维欧式空间嵌入到随机树度量中，则可以为高维欧式空间设计出高效的近似算法。

这套基于树嵌入的方法也同时是亚线性计算模型下用来解决高维优化问题的有力工具， 尤其是数据流模型和大规模并行计算（Massively Parallel Computation, MPC）模型中。 然而，在这些模型上的树嵌入构造均未能实现  的最优误差。 此外，除流模型与 MPC 模型外，高维场景下的树嵌入能否在动态模型（fully dynamic model）中高效维护（即支持点集通过插入 / 删除动态更新），目前也仍是未知问题。 因此，针对各类亚线性模型的高效树嵌入，尤其是应用于  等特殊度量空间的树嵌入，仍需一套新的系统性框架。

定理 1 设  为任意常数。 存在一个算法，对于任意以点插入/删除方式给出的  点的   上的数据集，维护一个  误差的随机树嵌入，每次操作的均摊运行时间为  。

其中  表示隐藏了  的低次数多项式。 对于任意常数  ，该算法都能实现近似比为  的动态树嵌入，这一结果在渐近意义下是最优的。

该动态树嵌入算法可直接应用于多种经典问题的动态近似求解中。基于该算法，本文推导出适用于 k-中位、欧氏最小权二分匹配（即推土机距离）、欧氏最小权一般匹配与几何传输距离的新动态算法。 例如，本文将定理 1与 [CALNF⁺21] 中给出的在树上的求解算法相结合，设计了一个新的动态 k-中位 算法。

推论 设   为任意常数。 存在一个算法，对于任意以点插入/删除方式给出的  点的  上的数据集，维护一个  近似的 k-中位的解，每次操作的均摊运行时间为  。

本文的另一个主要贡献是：在 MPC 模型中实现了高维欧式空间的高效树嵌入。MPC 模型是一种并行计算模型，脱胎于 MapReduce 等主流大数据计算框架，在理论计算机科学中由 Karloff 等人 [KSV10] 率先进行了形式化定义。 在 MPC 模型中，  个数据点分布式存储在若干个机器中，每个机器可以存储  个数据点，其中  是模型的主要参数。MPC 模型上的计算以（同步）轮的方式进行，在每一轮中，每台机器在总收发数据量至多是  的前提下，可以与任何其他机器进行通信，并且本地进行的计算不作任何限制。

定理 2 设  为任意常数。存在一个 MPC 算法，对于任意  点的  上的数据集以及任意的本地存储空间参数 （  ），在  轮内计算一个  误差的树嵌入。算法需要的所有机器的总空间为总空间为 。

算法的轮数为  轮（可以取决于  ），基本已达到最优。 算法改进了 Ahanchi 等人 [AAH⁺23] 的 MPC 树嵌入结果：他们仅得到  的误差，而我们可以得到  的（接近）最优的误差。 同时，结合现有基于树嵌入的 MPC 近似算法，本文的算法可直接应用于多种经典问题的近似求解中，由此得到包括 k-均值、欧氏最小生成树（EMST）、欧氏最小权二分匹配/推土机距离等问题的新 MPC 算法，并且达到目前最好的近似比。

本文的树嵌入算法可以一般性地作用在任何一个给定的有界空间划分。这里，对于参数  ，一个  -有界空间划分将空间划分为直径至多是    若干点集。 我们的树嵌入算法可以利用一个参数  ，来平衡整个算法的局部性和得到的树嵌入的误差。具体来说：

1. （局部性）算法的核心需要调用一个局部性受  调控的子过程：计算半径为   的球与给定的   -有界划分相交的部分。

2. （误差）返回的树嵌入的误差是  的。

即，随着  的增大，局部性变好，但误差变大。我们的算法结合近期提出的、若干针对欧氏空间的局部性较好的、可以高效在动态和 MPC 模型实现的空间划分/几何哈希技术（例如 [CJK⁺22] 中提出的“一致几何哈希”），即可得到定理 1 和定理 2 的结果。

技术上，我们的算法可以看作是经典的 CKR 分解 [CKR04] 框架在给定  -有界空间划分上的实现。下面我们进行简要介绍。

CKR 分解 [CKR04] 是一种随机空间划分技术。 考虑一般度量空间 ，其中  是点集，是距离函数。对于 ，定义度量球 ，。 CKR 分解需要接受一个直径参数  ，之后按如下过程构造空间划分：

1. 生成随机映射   。

2. 生成随机数   。

3. 对于每个  ，计算其标签  。

这些标签隐式定义了 的一个划分。通过将相同标签的点划为同一块，可以使用以下算法构造嵌入树：独立执行上述过程  次，对每个距离尺度  使用  ，得到标签   ，最终由这些标签隐式定义树嵌入。

然而，在 CKR 分解中要在度量球内找到  的最小值，这一步骤较难高效实现。 我们利用有界空间划分来近似实现这一目标：选取足够小的  ，将度量球用与其相交的  -有界空间划分中的部分来进行近似。 给定参数   和  ，改造的 CKR 算法大体如下所示：

1. 构造一个  -有界空间划分   。

2. 尺度调整：  的取值改为从  中均匀随机选取。

3. 对原始 CKR 算法的核心修改：将  ，替换为  ，即使用某个近似的球  替代   。

粗略地说，为定义 ，先取  与有界空间划分  相交的部分的并集，并从中额外去除那些与数据集  没有交集的部分， 最后取落在这些剩余部分的数据点。这种定义并非最简单自然的方式， 但在我们的分析论证中该定义的每个细节都有关键作用。

我们最后可以证明该近似 CKR 分解的误差只会比原始 CKR 形成的树嵌入多一个 因子。另外，算法唯一非凡的步骤是第三行，且该行只需要利用我们前面提到的局部性子过程：计算半径为  的球与给定的  -有界划分相交的部分。这呼应了我们提到的误差和局部性的主要保证。

[Bar96] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184–193. IEEE, 1996.

[FRT04] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004.

[Tre00] Luca Trevisan. When hamming meets euclid: The approximability of geometric tsp and steiner tree. SIAM Journal on Computing, 30(2):475–485, 2000.

[ACKS15] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. arXiv preprint arXiv:1502.03316, 2015.

[CALNF⁺21] Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svensson. Parallel and efficient hierarchical k-median clustering. Advances in Neural Information Processing Systems, 34:20333–20345, 2021.

[KSV10] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In SODA, pages 938–948, 2010. doi:10.1137/1.9781611973075.76.

[AAH⁺23] AmirMohsen Ahanchi, Alexandr Andoni, Mohammad Taghi Hajiaghayi, Marina Knittel, and Peilin Zhong. Massively parallel tree embeddings for high dimensional spaces. In SPAA, pages 77–88. ACM, 2023.

[CJK⁺22] Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesely, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In FOCS, pages 450–461. IEEE, 2022.

图文 | 孔启皓

PKU 姜少峰Lab