Efficient Sketches for Earth-Mover Distance, with Applications
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff · 2009
We provide the first sub-linear sketching algorithm for estimating the planar Earth-Mover Distance with a constant approximation. For sets living in the two-dimensional grid [¿]2, we achieve space ¿¿for approximation O(1/¿), for any desired 0 < ¿ < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.