{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:40:20Z","timestamp":1743597620366,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_70","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"834-845","source":"Crossref","is-referenced-by-count":4,"title":["Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance"],"prefix":"10.1007","author":[{"given":"Elad","family":"Verbin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. In: SoCG, pp. 39\u201350 (1995)","key":"70_CR1","DOI":"10.1145\/220279.220284"},{"doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Varadarajan, K.R.: A near-linear constant-factor approximation for euclidean bipartite matching? In: Symposium on Computational Geometry, pp. 247\u2013252 (2004)","key":"70_CR2","DOI":"10.1145\/997817.997856"},{"key":"70_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci.\u00a058, 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Ba, K.D., Indyk, P., Woodruff, D.: Efficient sketches for earth-mover distance, with applications. In: FOCS (2009)","key":"70_CR4","DOI":"10.1109\/FOCS.2009.25"},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Charikar, M.S., Neiman, O., Nguyen, H.L.: Near linear lower bound for dimension reduction in \u21131. In: IEEE Symposium on Foundations of Computer Science (2011)","key":"70_CR5","DOI":"10.1109\/FOCS.2011.87"},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., Krauthgamer, R.: Overcoming the \u21131 non-embeddability barrier: algorithms for product metrics. In: SODA, pp. 865\u2013874 (2009)","key":"70_CR6","DOI":"10.1137\/1.9781611973068.94"},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Streaming algorithms via precision sampling. In: FOCS, pp. 363\u2013372 (2011)","key":"70_CR7","DOI":"10.1109\/FOCS.2011.82"},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Nguyen, H.L.: Near-optimal sublinear time algorithms for Ulam distance. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 76\u201386 (2010)","key":"70_CR8","DOI":"10.1137\/1.9781611973075.8"},{"doi-asserted-by":"crossref","unstructured":"Andoni, A., Onak, K.: Approximating edit distance in near-linear time. In: STOC, pp. 199\u2013204 (2009)","key":"70_CR9","DOI":"10.1145\/1536414.1536444"},{"key":"70_CR10","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B. Brinkman","year":"2005","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in \u21131. J. ACM\u00a052, 766\u2013788 (2005)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: STOC, pp. 380\u2013388 (2002)","key":"70_CR11","DOI":"10.1145\/509907.509965"},{"doi-asserted-by":"crossref","unstructured":"Chefd\u2019hotel, C., Bousquet, G.: Intensity-based image registration using earth mover\u2019s distance. In: SPIE (2007)","key":"70_CR12","DOI":"10.1117\/12.709490"},{"issue":"3","key":"70_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.entcs.2009.10.006","volume":"253","author":"Y. Deng","year":"2009","unstructured":"Deng, Y., Du, W.: The Kantorovich metric in computer science: A brief survey. Electr. Notes Theor. Comput. Sci.\u00a0253(3), 73\u201382 (2009)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Grauman, K., Darrell, T.: Fast contour matching using approximate earth movers distance. In: CVPR, pp. 220\u2013227 (2004)","key":"70_CR14","DOI":"10.1109\/CVPR.2004.1315035"},{"issue":"9-10","key":"70_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0262-8856(02)00060-4","volume":"20","author":"A.S. Holmes","year":"2002","unstructured":"Holmes, A.S., Rose, C.J., Taylor, C.J.: Transforming pixel signatures into an improved metric space. Image Vision Comput\u00a020(9-10), 701\u2013707 (2002)","journal-title":"Image Vision Comput"},{"unstructured":"Indyk, P.: Algorithmic aspects of geometric embeddings. In: IEEE Symposium on Foundations of Computer Science (2001)","key":"70_CR16"},{"key":"70_CR17","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P. Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM\u00a053, 307\u2013323 (2006)","journal-title":"J. ACM"},{"unstructured":"Indyk, P.: A near linear time constant factor approximation for euclidean bichromatic matching (cost). In: SODA, pp. 39\u201342 (2007)","key":"70_CR18"},{"doi-asserted-by":"crossref","unstructured":"Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Handbook of Discrete and Computational Geometry, pp. 177\u2013196. CRC Press (2004)","key":"70_CR19","DOI":"10.1201\/9781420035315.ch8"},{"unstructured":"Indyk, P., Thaper, N.: Fast color image retrieval via embeddings. In: Workshop on Statistical and Computational Theories of Vision, at ICCV (2003)","key":"70_CR20"},{"doi-asserted-by":"crossref","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics, vol.\u00a026, pp. 189\u2013206. American Mathematical Society (1984)","key":"70_CR21","DOI":"10.1090\/conm\/026\/737400"},{"issue":"7-8","key":"70_CR22","first-page":"227","volume":"37","author":"L.V. Kantorovich","year":"1942","unstructured":"Kantorovich, L.V.: On the translocation of masses. Dokl. Akad. Nauk SSSR\u00a037(7-8), 227\u2013229 (1942)","journal-title":"Dokl. Akad. Nauk SSSR"},{"unstructured":"Lawler, E.: Combinatorial optimization - networks and matroids. Holt, Rinehart and Winston, New York (1976)","key":"70_CR23"},{"doi-asserted-by":"crossref","unstructured":"Levina, E., Bickel, P.J.: The earth mover\u2019s distance is the mallows distance: Some insights from statistics. In: ICCV, pp. 251\u2013256 (2001)","key":"70_CR24","DOI":"10.1109\/ICCV.2001.937632"},{"doi-asserted-by":"crossref","unstructured":"Linial, N.: Finite metric spaces - combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians III, pp. 573\u2013586 (2002)","key":"70_CR25","DOI":"10.1145\/513400.513441"},{"doi-asserted-by":"crossref","unstructured":"Maurey, B.: Type, cotype and k-convexity. In: Handbook of the Geometry of Banach Spaces, vol.\u00a02, pp. 1299\u20131332. North-Holland (2003)","key":"70_CR26","DOI":"10.1016\/S1874-5849(03)80037-2"},{"unstructured":"McGregor, A.: Open problems in data streams, property testing, and related topics (2011), http:\/\/www.cs.umass.edu\/~mcgregor\/papers\/11-openproblems.pdf","key":"70_CR27"},{"issue":"3","key":"70_CR28","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/05064206X","volume":"37","author":"A. Naor","year":"2007","unstructured":"Naor, A., Schechtman, G.: Planar earthmover is not in \u21131. SIAM J. Comput.\u00a037(3), 804\u2013826 (2007)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computations. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 204\u2013212 (1990)","key":"70_CR29","DOI":"10.1145\/100216.100242"},{"doi-asserted-by":"crossref","unstructured":"Puzicha, J., Buhmann, J.M., Rubner, Y., Tomasi, C.: Empirical evaluation of dissimilarity measures for color and texture. In: ICCV, pp. 1165\u20131173 (1999)","key":"70_CR30","DOI":"10.1109\/ICCV.1999.790412"},{"key":"70_CR31","doi-asserted-by":"publisher","first-page":"2000","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y. Rubner","year":"2000","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: The earth movers distance as a metric for image retrieval. International Journal of Computer Vision\u00a040 (2000)","journal-title":"International Journal of Computer Vision"},{"key":"70_CR32","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput.\u00a018, 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."},{"unstructured":"Varadarajan, K.R., Agarwal, P.K.: Approximation algorithms for bipartite and non-bipartite matching in the plane. In: SODA, pp. 805\u2013814 (1999)","key":"70_CR33"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:12:53Z","timestamp":1743595973000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}