# New Streaming Algorithms for High Dimensional EMD and MST

arXiv: https://arxiv.org/abs/2111.03528 · HTML: https://mlsanity.com/paper/2111.03528/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2021.

## Built on by (most cited first, 5 of 5)

- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport](https://mlsanity.com/paper/2210.13630/) (2022)
- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)
- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [Field Codes for Distributed Coupling Samplers and Certified Empirical Transport](https://mlsanity.com/paper/2607.27078/) (2026)

## Abstract (arXiv)

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an n-point set X subset 1,2,dots,Deltad, and computing the Earth Mover Distance (EMD) between two multi-sets A,B subset 1,2,dots,Deltad 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 tildeO(log n) 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(min log n , log (Delta d) log n) [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(log n), analogous to the Omega(log n) 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 tildeO(log n) approximation for both EMD and MST, improving on the O(min log n , log (Delta d) log n) approximation of [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20].