New streaming algorithms for high dimensional EMD and MST
Authors:
Open Access
- 9 June 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 222-233
Abstract
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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Convolutional wasserstein distancesACM Transactions on Graphics, 2015
- Sketching and Embedding are Equivalent for Norms2015
- Glove: Global Vectors for Word Representation2014
- 1-Pass Relative-Error Lp-Sampling with Applications2010
- Planar Earthmover Is Not in $L_1$SIAM Journal on Computing, 2007
- Stable distributions, pseudorandom generators, embeddings, and data stream computationJournal of the ACM, 2006
- Nonembeddability theorems via Fourier analysisMathematische Annalen, 2006
- An information statistics approach to data stream and communication complexityJournal of Computer and System Sciences, 2004
- Finding Frequent Items in Data Streams2002
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970