Efficient sketches for Earth-Mover Distance, with applications

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. © 2009 IEEE.