New streaming algorithms for high dimensional EMD and MST

DOI10.1145/3519935.3519979MaRDI QIDQ6083479zbMATH OpenOpenAlexFDO

Authors Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03528

zbMATH Keywords

earth-mover's distanceminimum spanning treesketchingstreaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an $n$-point set $Xsubset{1,2,dots,Delta}^d$, and computing the Earth Mover Distance (EMD) between two multi-sets $A,Bsubset{1,2,dots,Delta}^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 $ildeO(logn)$ and using polylog$(n,d,Delta)$-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(minlogn,log(Deltad)logn)$ [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20]. For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of $Omega(logn)$, analogous to the $Omega(logn)$ lower bound for EMD of [Andoni-Indyk-Krauthgamer '08]. 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 $ildeO(logn)$ approximation for both EMD and MST, improving on the $O(minlogn,log(Deltad)logn)$ approximation of [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20].

Cited in

(9)

• Streaming algorithms for extent problems in high dimensions
• scientific article; zbMATH DE number 1629825 (Why is no real title available?)
• An approximate L^p difference algorithm for massive data streams
• scientific article; zbMATH DE number 6297803 (Why is no real title available?)
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Fully-scalable MPC algorithms for clustering in high dimension
• Moderate dimension reduction for k-center clustering
• Streaming algorithms for geometric Steiner forest
• Streaming diameter of high-dimensional points

This page was built for publication: New streaming algorithms for high dimensional EMD and MST

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083479)