{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T17:45:24Z","timestamp":1785519924333,"version":"3.56.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,4,10]],"date-time":"2010-04-10T00:00:00Z","timestamp":1270857600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00224-010-9265-8","type":"journal-article","created":{"date-parts":[[2010,4,9]],"date-time":"2010-04-09T17:48:22Z","timestamp":1270835302000},"page":"428-442","source":"Crossref","is-referenced-by-count":20,"title":["Sublinear Time Algorithms for Earth Mover\u2019s Distance"],"prefix":"10.1007","volume":"48","author":[{"given":"Khanh Do","family":"Ba","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huy L.","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huy N.","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,4,10]]},"reference":[{"key":"9265_CR1","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1109\/SFCS.2000.892111","volume-title":"FOCS \u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"N. Alon","year":"2000","unstructured":"Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of clustering. In: FOCS \u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 240. IEEE Computer Society, Washington (2000)"},{"key":"9265_CR2","first-page":"343","volume-title":"SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Andoni","year":"2008","unstructured":"Andoni, A., Indyk, P., Krauthgamer, R.: Earth mover distance over high-dimensional spaces. In: SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 343\u2013352. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"key":"9265_CR3","first-page":"184","volume-title":"FOCS \u201996: Proceedings of the 37th Annual Symposium on Foundations of Computer Science","author":"Y. Bartal","year":"1996","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS \u201996: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p. 184. IEEE Computer Society, Washington (1996)"},{"key":"9265_CR4","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1109\/SFCS.2000.892113","volume-title":"FOCS \u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"T. Batu","year":"2000","unstructured":"Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: FOCS \u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 259. IEEE Computer Society, Washington (2000)"},{"key":"9265_CR5","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1109\/SFCS.2001.959920","volume-title":"FOCS \u201901: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science","author":"T. Batu","year":"2001","unstructured":"Batu, T., Fortnow, L., Fischer, E., Kumar, R., Rubinfeld, R., White, P.: Testing random variables for independence and identity. In: FOCS \u201901: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, p. 442. IEEE Computer Society, Washington (2001)"},{"key":"9265_CR6","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1145\/509907.509965","volume-title":"STOC \u201902: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing","author":"M.S. Charikar","year":"2002","unstructured":"Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: STOC \u201902: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 380\u2013388. ACM, New York (2002)"},{"key":"9265_CR7","doi-asserted-by":"crossref","first-page":"1076","DOI":"10.1109\/ICCV.1999.790393","volume-title":"ICCV \u201999: Proceedings of the International Conference on Computer Vision","author":"S. Cohen","year":"1999","unstructured":"Cohen, S., Guibas, L.: The earth mover\u2019s distance under transformation sets. In: ICCV \u201999: Proceedings of the International Conference on Computer Vision, vol.\u00a02, p. 1076. IEEE Computer Society, Washington (1999)"},{"key":"9265_CR8","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1145\/780542.780608","volume-title":"STOC \u201903: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing","author":"J. Fakcharoenphol","year":"2003","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC \u201903: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 448\u2013455. ACM, New York (2003)"},{"key":"9265_CR9","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. In: Electronic Colloquium on Computational Complexity (ECCC), 7(20), (2000)"},{"key":"9265_CR10","first-page":"39","volume-title":"SODA \u201907: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Indyk","year":"2007","unstructured":"Indyk, P.: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: SODA \u201907: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201342. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"key":"9265_CR11","unstructured":"Indyk, P., Thaper, N.: Fast image retrieval via embeddings. In: 3rd International Workshop on Statistical and Computational Theories of Vision. ICCV (2003)"},{"key":"9265_CR12","doi-asserted-by":"crossref","unstructured":"Peleg, S., Werman, M., Rom, H.: A unified approach to the change of resolution: space and gray-level (1989)","DOI":"10.1117\/12.944709"},{"key":"9265_CR13","doi-asserted-by":"crossref","unstructured":"Rubner, Y., Tomasi, C.: Texture metrics. In: Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference on, vol. 5, pp. 4601\u20134607 Oct. 1998","DOI":"10.1109\/ICSMC.1998.727577"},{"key":"9265_CR14","unstructured":"Rubner, Y., Guibas, L.J., Tomasi, C.: The earth movers distance, multi-dimensional scaling, and color-based image retrieval. In: APRA Image Understanding Workshop, pp. 661\u2013668, May 1997"},{"key":"9265_CR15","doi-asserted-by":"crossref","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: A metric for distributions with applications to image databases. In Computer Vision, 1998. Sixth International Conference on, pp. 59\u201366 (1998)","DOI":"10.1109\/ICCV.1998.710701"},{"issue":"2","key":"9265_CR16","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y. Rubner","year":"2000","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover\u2019s distance as a metric for image retrieval. Int. J. Comput. Vision 40(2), 99\u2013121 (2000)","journal-title":"Int. J. Comput. Vision"},{"key":"9265_CR17","unstructured":"Ruzon, M.A., Tomasi, C.: Color Edge Detection with the Compass Operator, vol. 2, p. 166 (1999)"},{"key":"9265_CR18","doi-asserted-by":"crossref","unstructured":"Ruzon, M.A., Tomasi, C.: Corner detection in textured color images. In: Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, vol. 2, pp. 1039\u20131045 (1999)","DOI":"10.1109\/ICCV.1999.790384"},{"key":"9265_CR19","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1145\/1374376.1374432","volume-title":"STOC \u201908: Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"P. Valiant","year":"2008","unstructured":"Valiant, P.: Testing symmetric properties of distributions. In: STOC \u201908: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 383\u2013392. ACM, New York (2008)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9265-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9265-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9265-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T22:20:52Z","timestamp":1740003652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9265-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,10]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9265"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9265-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,10]]}}}