New streaming algorithms for high dimensional EMD and MST
New streaming algorithms for high dimensional EMD and MST
复制标题
DOI：
10.1145/3519935.3519979
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Xi Chen;Rajesh Jayaram;Amit Levi;Erik Waingarten
中科院分区：
文献类型：
--
作者：
Xi Chen;Rajesh Jayaram;Amit Levi;Erik Waingarten
我们研究了两个基本几何问题的流算法：计算n点集X <${1，2，.，Δ}d的最小生成树（MST）的成本，以及计算大小为n的两个多点集A，B <${1，2，.，Δ}d之间的地球移动器距离（EMD）。我们考虑旋转栅门模型，其中点可以添加和删除。我们给出了MST的一次流算法和EMD的两次流算法，两者都实现了近似因子为n（logn）并且仅使用（n，d，Δ）-空间。此外，我们的算法EMD可以压缩到一个小的附加误差的单程。在此之前，最著名的子线性空间流算法实现了O（min{ logn，log（Δ d）} logn）的近似。对于MST，我们还证明了任何恒定空间流算法只能达到Ω（logn）的近似，类似于EMD的Ω（logn）下界。我们的算法是基于改进的分析递归空间划分方法一般称为四叉树。具体来说，我们证明了四叉树实现了EMD和MST的O（logn）近似，改进了O（min{ logn，log（Δ d）} logn）近似。
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an n-point set X ⊂ {1,2,…,Δ}d, and computing the Earth Mover Distance (EMD) between two multi-sets A,B ⊂ {1,2,…,Δ}d of size n. We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of Õ(logn) and using (n,d,Δ)-space only. Furthermore, our algorithm for EMD can be compressed to a single pass with a small additive error. Previously, the best known sublinear-space streaming algorithms for either problem achieved an approximation of O(min{ logn , log(Δ d)} logn). For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of Ω(logn), analogous to the Ω(logn) lower bound for EMD. Our algorithms are based on an improved analysis of a recursive space partitioning method known generically as the Quadtree. Specifically, we show that the Quadtree achieves an Õ(logn) approximation for both EMD and MST, improving on the O(min{ logn , log(Δ d)} logn) approximation.