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 [Δ][superscript 2], we achieve space ΔE for approximation O(1/E), for any desired 0 < E < 1. Our sketch has immediate a...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/58879 https://orcid.org/0000-0002-7983-9524 |