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 |
| _version_ | 1826200985174802432 |
|---|---|
| author | Indyk, Piotr Woodruff, David Do Ba, Khanh Andoni, Alexandr |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Woodruff, David Do Ba, Khanh Andoni, Alexandr |
| author_sort | Indyk, Piotr |
| collection | MIT |
| description | 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 applications to the streaming and nearest neighbor search problems. |
| first_indexed | 2024-09-23T11:44:48Z |
| format | Article |
| id | mit-1721.1/58879 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:44:48Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/588792022-09-27T21:37:06Z Efficient Sketches for Earth-Mover Distance, with Applications Indyk, Piotr Woodruff, David Do Ba, Khanh Andoni, Alexandr Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Indyk, Piotr Do Ba, Khanh Andoni, Alexandr Earth-Mover Distance embedding sketching streaming 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 applications to the streaming and nearest neighbor search problems. National Science Foundation (U.S.) (CAREER award CCR-0133849) Alfred P. Sloan Foundation David and Lucile Packard Foundation 2010-10-05T19:58:01Z 2010-10-05T19:58:01Z 2010-03 2009-10 Article http://purl.org/eprint/type/JournalArticle 0272-5428 INSPEC Accession Number: 11207133 http://hdl.handle.net/1721.1/58879 Andoni, A. et al. “Efficient Sketches for Earth-Mover Distance, with Applications.” Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on. 2009. 324-330. © 2010 Institute of Electrical and Electronics Engineers. https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1109/focs.2009.25 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS '09 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Earth-Mover Distance embedding sketching streaming Indyk, Piotr Woodruff, David Do Ba, Khanh Andoni, Alexandr Efficient Sketches for Earth-Mover Distance, with Applications |
| title | Efficient Sketches for Earth-Mover Distance, with Applications |
| title_full | Efficient Sketches for Earth-Mover Distance, with Applications |
| title_fullStr | Efficient Sketches for Earth-Mover Distance, with Applications |
| title_full_unstemmed | Efficient Sketches for Earth-Mover Distance, with Applications |
| title_short | Efficient Sketches for Earth-Mover Distance, with Applications |
| title_sort | efficient sketches for earth mover distance with applications |
| topic | Earth-Mover Distance embedding sketching streaming |
| url | http://hdl.handle.net/1721.1/58879 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT indykpiotr efficientsketchesforearthmoverdistancewithapplications AT woodruffdavid efficientsketchesforearthmoverdistancewithapplications AT dobakhanh efficientsketchesforearthmoverdistancewithapplications AT andonialexandr efficientsketchesforearthmoverdistancewithapplications |