{"data":{"id":"10.48550/arxiv.1404.6287","type":"dois","attributes":{"doi":"10.48550/arxiv.1404.6287","prefix":"10.48550","suffix":"arxiv.1404.6287","identifiers":[{"identifier":"1404.6287","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1404.6287"}],"creators":[{"name":"Yousefi, Arman","nameType":"Personal","givenName":"Arman","familyName":"Yousefi","affiliation":[],"nameIdentifiers":[]},{"name":"Ostrovsky, Rafail","nameType":"Personal","givenName":"Rafail","familyName":"Ostrovsky","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Improved Approximation Algorithms for Earth-Mover Distance in Data Streams"}],"publisher":"arXiv","container":{},"publicationYear":2014,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2014-04-24T22:55:53Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2014-04-28T00:02:24Z","dateType":"Updated","dateInformation":"v1"},{"date":"2014-04","dateType":"Available","dateInformation":"v1"},{"date":"2014","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"For two multisets $S$ and $T$ of points in $[Δ]^2$, such that $|S| = |T|= n$, the earth-mover distance (EMD) between $S$ and $T$ is the minimum cost of a perfect bipartite matching with edges between points in $S$ and $T$, i.e., $EMD(S,T) = \\min_{π:S\\rightarrow T}\\sum_{a\\in S}||a-π(a)||_1$, where $π$ ranges over all one-to-one mappings. The sketching complexity of approximating earth-mover distance in the two-dimensional grid is mentioned as one of the open problems in the literature. We give two algorithms for computing EMD between two multi-sets when the number of distinct points in one set is a small value $k=\\log^{O(1)}(Δn)$. Our first algorithm gives a $(1+ε)$-approximation using $O(kε^{-2}\\log^{4}n)$ space and works only in the insertion-only model. The second algorithm gives a $O(\\min(k^3,\\logΔ))$-approximation using $O(\\log^{3}Δ\\cdot\\log\\logΔ\\cdot\\log n)$-space in the turnstile model.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNDA0LjYyODc8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xNDA0LjYyODc8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+WW91c2VmaSwgQXJtYW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkFybWFuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPllvdXNlZmk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+T3N0cm92c2t5LCBSYWZhaWw8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlJhZmFpbDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Pc3Ryb3Zza3k8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPkltcHJvdmVkIEFwcHJveGltYXRpb24gQWxnb3JpdGhtcyBmb3IgRWFydGgtTW92ZXIgRGlzdGFuY2UgaW4gRGF0YSBTdHJlYW1zPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDE0PC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+RGF0YSBTdHJ1Y3R1cmVzIGFuZCBBbGdvcml0aG1zIChjcy5EUyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBDb21wdXRlciBhbmQgaW5mb3JtYXRpb24gc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE0LTA0LTI0VDIyOjU1OjUzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE0LTA0LTI4VDAwOjAyOjI0WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTQtMDQ8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPkZvciB0d28gbXVsdGlzZXRzICRTJCBhbmQgJFQkIG9mIHBvaW50cyBpbiAkW86UXV4yJCwgc3VjaCB0aGF0ICR8U3wgPSB8VHw9IG4kLCB0aGUgZWFydGgtbW92ZXIgZGlzdGFuY2UgKEVNRCkgYmV0d2VlbiAkUyQgYW5kICRUJCBpcyB0aGUgbWluaW11bSBjb3N0IG9mIGEgcGVyZmVjdCBiaXBhcnRpdGUgbWF0Y2hpbmcgd2l0aCBlZGdlcyBiZXR3ZWVuIHBvaW50cyBpbiAkUyQgYW5kICRUJCwgaS5lLiwgJEVNRChTLFQpID0gXG1pbl97z4A6U1xyaWdodGFycm93IFR9XHN1bV97YVxpbiBTfXx8YS3PgChhKXx8XzEkLCB3aGVyZSAkz4AkIHJhbmdlcyBvdmVyIGFsbCBvbmUtdG8tb25lIG1hcHBpbmdzLiBUaGUgc2tldGNoaW5nIGNvbXBsZXhpdHkgb2YgYXBwcm94aW1hdGluZyBlYXJ0aC1tb3ZlciBkaXN0YW5jZSBpbiB0aGUgdHdvLWRpbWVuc2lvbmFsIGdyaWQgaXMgbWVudGlvbmVkIGFzIG9uZSBvZiB0aGUgb3BlbiBwcm9ibGVtcyBpbiB0aGUgbGl0ZXJhdHVyZS4gV2UgZ2l2ZSB0d28gYWxnb3JpdGhtcyBmb3IgY29tcHV0aW5nIEVNRCBiZXR3ZWVuIHR3byBtdWx0aS1zZXRzIHdoZW4gdGhlIG51bWJlciBvZiBkaXN0aW5jdCBwb2ludHMgaW4gb25lIHNldCBpcyBhIHNtYWxsIHZhbHVlICRrPVxsb2dee08oMSl9KM6UbikkLiBPdXIgZmlyc3QgYWxnb3JpdGhtIGdpdmVzIGEgJCgxK861KSQtYXBwcm94aW1hdGlvbiB1c2luZyAkTyhrzrVeey0yfVxsb2deezR9bikkIHNwYWNlIGFuZCB3b3JrcyBvbmx5IGluIHRoZSBpbnNlcnRpb24tb25seSBtb2RlbC4gVGhlIHNlY29uZCBhbGdvcml0aG0gZ2l2ZXMgYSAkTyhcbWluKGteMyxcbG9nzpQpKSQtYXBwcm94aW1hdGlvbiB1c2luZyAkTyhcbG9nXnszfc6UXGNkb3RcbG9nXGxvZ86UXGNkb3RcbG9nIG4pJC1zcGFjZSBpbiB0aGUgdHVybnN0aWxlIG1vZGVsLjwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/1404.6287","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-10T06:28:28.000Z","registered":"2022-03-10T06:28:29.000Z","published":"2014","updated":"2022-03-10T06:28:29.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1404.6287","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}