{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T17:25:16Z","timestamp":1791307516694,"version":"4.3.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>\n            In this paper we study the tradeoff between parallelism and communication cost in a map-reduce computation. For any problem that is not \"embarrassingly parallel,\" the finer we partition the work of the reducers so that more parallelism can be extracted, the greater will be the total communication between mappers and reducers. We introduce a model of problems that can be solved in a single round of map-reduce computation. This model enables a generic recipe for discovering lower bounds on communication cost as a function of the maximum number of inputs that can be assigned to one reducer. We use the model to analyze the tradeoff for three problems: finding pairs of strings at Hamming distance\n            <jats:italic>d<\/jats:italic>\n            , finding triangles and other patterns in a larger graph, and matrix multiplication. For finding strings of Hamming distance 1, we have upper and lower bounds that match exactly. For triangles and many other graphs, we have upper and lower bounds that are the same to within a constant factor. For the problem of matrix multiplication, we have matching upper and lower bounds for one-round map-reduce algorithms. We are also able to explore two-round map-reduce algorithms for matrix multiplication and show that these never have more communication, for a given reducer size, than the best one-round algorithm, and often have significantly less.\n          <\/jats:p>","DOI":"10.14778\/2535570.2488334","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"277-288","source":"Crossref","is-referenced-by-count":64,"title":["Upper and lower bounds on the cost of a map-reduce computation"],"prefix":"10.14778","volume":"6","author":[{"given":"Anish Das","family":"Sarma","sequence":"first","affiliation":[{"name":"Google Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Foto N.","family":"Afrati","sequence":"additional","affiliation":[{"name":"National Technical University of Athens"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Semih","family":"Salihoglu","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey D.","family":"Ullman","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"issue":"9","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1109\/TKDE.2011.47","article-title":"Optimizing multiway joins in a map-reduce environment","volume":"23","author":"Afrati F.","year":"2011","unstructured":"F. Afrati and J. Ullman . Optimizing multiway joins in a map-reduce environment . IEEE Transactions on Knowledge and Data Engineering , 23 ( 9 ): 1282 - 1298 , 2011 . F. Afrati and J. Ullman. Optimizing multiway joins in a map-reduce environment. IEEE Transactions on Knowledge and Data Engineering, 23(9):1282-1298, 2011.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_2_1","volume-title":"Stanford InfoLab","author":"Afrati F. N.","year":"2012","unstructured":"F. N. Afrati , D. Fotakis , and J. D. Ullman . Enumerating subgraph instances using map-reduce. Technical report , Stanford InfoLab , January 2012 . Available at http:\/\/ilpubs.stanford.edu:8090\/1020\/. F. N. Afrati, D. Fotakis, and J. D. Ullman. Enumerating subgraph instances using map-reduce. Technical report, Stanford InfoLab, January 2012. Available at http:\/\/ilpubs.stanford.edu:8090\/1020\/."},{"key":"e_1_2_1_3_1","volume-title":"ICDE","author":"Afrati F. N.","year":"2012","unstructured":"F. N. Afrati , A. D. Sarma , D. Menestrina , A. Parameswaran , and J. D. Ullman . Fuzzy joins using mapreduce . In ICDE , 2012 . F. N. Afrati, A. D. Sarma, D. Menestrina, A. Parameswaran, and J. D. Ullman. Fuzzy joins using mapreduce. In ICDE, 2012."},{"key":"e_1_2_1_4_1","volume-title":"Upper and lower bounds on the cost of a map-reduce computation. CoRR, abs\/1206.4377","author":"Afrati F. N.","year":"2012","unstructured":"F. N. Afrati , A. D. Sarma , S. Salihoglu , and J. D. Ullman . Upper and lower bounds on the cost of a map-reduce computation. CoRR, abs\/1206.4377 , 2012 . F. N. Afrati, A. D. Sarma, S. Salihoglu, and J. D. Ullman. Upper and lower bounds on the cost of a map-reduce computation. CoRR, abs\/1206.4377, 2012."},{"issue":"1","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF02761855","article-title":"On the number of subgraphs of prescribed type of graphs with a given number of edges","volume":"38","author":"Alon N.","year":"1981","unstructured":"N. Alon . On the number of subgraphs of prescribed type of graphs with a given number of edges . Israel Journal of Mathematics , 38 ( 1-2 ): 116 - 130 , 1981 . N. Alon. On the number of subgraphs of prescribed type of graphs with a given number of edges. Israel Journal of Mathematics, 38(1-2):116-130, 1981.","journal-title":"Israel Journal of Mathematics"},{"key":"e_1_2_1_6_1","volume-title":"Amazon Elastic Compute Cloud (Amazon EC2)","year":"2008","unstructured":"Amazon. Amazon Elastic Compute Cloud (Amazon EC2) . Amazon Inc ., 2008 . Amazon. Amazon Elastic Compute Cloud (Amazon EC2). Amazon Inc., 2008."},{"key":"e_1_2_1_7_1","first-page":"739","volume-title":"FOCS","author":"Atserias A.","year":"2008","unstructured":"A. Atserias , M. Grohe , and D. Marx . Size bounds and query plans for relational joins . In FOCS , pages 739 - 748 , 2008 . A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. In FOCS, pages 739-748, 2008."},{"key":"e_1_2_1_8_1","volume-title":"KDD","author":"Cordeiro R. L. F.","year":"2011","unstructured":"R. L. F. Cordeiro , C. T. Jr., A. J. M. Traina , J. L\u00f3pez , U. Kang , and C. Faloutsos . Clustering very large multi-dimensional datasets with mapreduce . In KDD , 2011 . R. L. F. Cordeiro, C. T. Jr., A. J. M. Traina, J. L\u00f3pez, U. Kang, and C. Faloutsos. Clustering very large multi-dimensional datasets with mapreduce. In KDD, 2011."},{"key":"e_1_2_1_9_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: simplified data processing on large clusters . In OSDI , pages 137 - 150 , 2004 . J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. In OSDI, pages 137-150, 2004."},{"key":"e_1_2_1_10_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","year":"1968","unstructured":"W. Feller . An Introduction to Probability Theory and Its Applications . Vol. 1 , 3 rd ed. New York : Wiley , 1968 . (Stirling's Formula in Section 2.9). W. Feller. An Introduction to Probability Theory and Its Applications. Vol. 1, 3rd ed. New York: Wiley, 1968. (Stirling's Formula in Section 2.9).","edition":"3"},{"key":"e_1_2_1_11_1","first-page":"231","volume-title":"ICDE","author":"Ghoting A.","year":"2011","unstructured":"A. Ghoting , R. Krishnamurthy , E. P. D. Pednault , B. Reinwald , V. Sindhwani , S. Tatikonda , Y. Tian , and S. Vaithyanathan . Systemml: Declarative machine learning on mapreduce . In ICDE , pages 231 - 242 , 2011 . A. Ghoting, R. Krishnamurthy, E. P. D. Pednault, B. Reinwald, V. Sindhwani, S. Tatikonda, Y. Tian, and S. Vaithyanathan. Systemml: Declarative machine learning on mapreduce. In ICDE, pages 231-242, 2011."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/1109557.1109590","volume-title":"SODA","author":"Grohe M.","year":"2006","unstructured":"M. Grohe and D. Marx . Constraint solving via fractional edge covers . In SODA , pages 289 - 298 , 2006 . M. Grohe and D. Marx. Constraint solving via fractional edge covers. In SODA, pages 289-298, 2006."},{"key":"e_1_2_1_13_1","volume-title":"VLDB","author":"Hasan W.","year":"1994","unstructured":"W. Hasan and R. Motwani . Optimization algorithms for exploiting the parallelism-communication tradeoff in pipelined parallelism . In VLDB , 1994 . W. Hasan and R. Motwani. Optimization algorithms for exploiting the parallelism-communication tradeoff in pipelined parallelism. In VLDB, 1994."},{"key":"e_1_2_1_14_1","volume-title":"CIDR","author":"Ikeda R.","year":"2011","unstructured":"R. Ikeda , H. Park , and J. Widom . Provenance for generalized map and reduce workflows . In CIDR , 2011 . R. Ikeda, H. Park, and J. Widom. Provenance for generalized map and reduce workflows. In CIDR, 2011."},{"key":"e_1_2_1_15_1","first-page":"938","volume-title":"SODA","author":"Karloff H. J.","year":"2010","unstructured":"H. J. Karloff , S. Suri , and S. Vassilvitskii . A model of computation for mapreduce . In SODA , pages 938 - 948 , 2010 . H. J. Karloff, S. Suri, and S. Vassilvitskii. A model of computation for mapreduce. In SODA, pages 938-948, 2010."},{"key":"e_1_2_1_16_1","first-page":"223","volume-title":"PODS","author":"Koutris P.","year":"2011","unstructured":"P. Koutris and D. Suciu . Parallel evaluation of conjunctive queries . In PODS , pages 223 - 234 , 2011 . P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In PODS, pages 223-234, 2011."},{"key":"e_1_2_1_17_1","first-page":"25","volume-title":"SIGMOD Conference","author":"Kwon Y.","year":"2012","unstructured":"Y. Kwon , M. Balazinska , B. Howe , and J. A. Rolia . Skewtune: mitigating skew in mapreduce applications . In SIGMOD Conference , pages 25 - 36 , 2012 . Y. Kwon, M. Balazinska, B. Howe, and J. A. Rolia. Skewtune: mitigating skew in mapreduce applications. In SIGMOD Conference, pages 25-36, 2012."},{"issue":"3","key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/362875.362879","article-title":"Organizing matrices and matrix operations for paged memory systems","volume":"12","author":"McKellar A. C.","year":"1969","unstructured":"A. C. McKellar and E. G. Coffman . Organizing matrices and matrix operations for paged memory systems . Commun. ACM , 12 ( 3 ): 153 - 165 , 1969 . A. C. McKellar and E. G. Coffman. Organizing matrices and matrix operations for paged memory systems. Commun. ACM, 12(3):153-165, 1969.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_19_1","first-page":"949","volume-title":"SIGMOD Conference","author":"Okcan A.","year":"2011","unstructured":"A. Okcan and M. Riedewald . Processing theta-joins using mapreduce . In SIGMOD Conference , pages 949 - 960 , 2011 . A. Okcan and M. Riedewald. Processing theta-joins using mapreduce. In SIGMOD Conference, pages 949-960, 2011."},{"key":"e_1_2_1_20_1","volume-title":"Proc. of VLDB","author":"Olston C.","year":"2011","unstructured":"C. Olston and B. Reed . Inspector gadget: A framework for custom monitoring and debugging of distributed dataflows . In Proc. of VLDB , 2011 . C. Olston and B. Reed. Inspector gadget: A framework for custom monitoring and debugging of distributed dataflows. In Proc. of VLDB, 2011."},{"key":"e_1_2_1_21_1","volume-title":"Space-round tradeoffs for mapreduce computations. CoRR, abs\/1111.2228","author":"Pietracaprina A.","year":"2011","unstructured":"A. Pietracaprina , G. Pucci , M. Riondato , F. Silvestri , and E. Upfal . Space-round tradeoffs for mapreduce computations. CoRR, abs\/1111.2228 , 2011 . A. Pietracaprina, G. Pucci, M. Riondato, F. Silvestri, and E. Upfal. Space-round tradeoffs for mapreduce computations. CoRR, abs\/1111.2228, 2011."},{"key":"e_1_2_1_22_1","volume-title":"Mining of Massive Datasets","author":"Rajaraman A.","unstructured":"A. Rajaraman and J. D. Ullman . Mining of Massive Datasets . Cambridge University Press . Also available on-line at i.stanford.edu\/~ullman\/mmds.html, 2011. A. Rajaraman and J. D. Ullman. Mining of Massive Datasets. Cambridge University Press. Also available on-line at i.stanford.edu\/~ullman\/mmds.html, 2011."},{"key":"e_1_2_1_23_1","volume-title":"Algorithmic Aspects of Triangle-Based Network","author":"Schank T.","year":"2007","unstructured":"T. Schank . Algorithmic Aspects of Triangle-Based Network . University of Karlsruhe (TH) , 2007 . T. Schank. Algorithmic Aspects of Triangle-Based Network. University of Karlsruhe (TH), 2007."},{"key":"e_1_2_1_24_1","volume-title":"WWW","author":"Suri S.","year":"2011","unstructured":"S. Suri and S. Vassilvitskii . Counting triangles and the curse of the last reducer . In WWW , 2011 . S. Suri and S. Vassilvitskii. Counting triangles and the curse of the last reducer. In WWW, 2011."},{"key":"e_1_2_1_25_1","volume-title":"Past, Current, and Future","author":"Tan W.-C.","year":"2008","unstructured":"W.-C. Tan . Provenance in Databases : Past, Current, and Future . IEEE Data Engineering Bulletin , 2008 . W.-C. Tan. Provenance in Databases: Past, Current, and Future. IEEE Data Engineering Bulletin, 2008."},{"key":"e_1_2_1_26_1","volume-title":"SIGMOD Conference","author":"Vernica R.","year":"2010","unstructured":"R. Vernica , M. J. Carey , and C. Li . Efficient parallel set-similarity joins using mapreduce . In SIGMOD Conference , 2010 . R. Vernica, M. J. Carey, and C. Li. Efficient parallel set-similarity joins using mapreduce. In SIGMOD Conference, 2010."},{"key":"e_1_2_1_27_1","volume-title":"Storage and Analysis at Internet Scale (2. ed.). O'Reilly","author":"White T.","year":"2011","unstructured":"T. White . Hadoop - The Definitive Guide : Storage and Analysis at Internet Scale (2. ed.). O'Reilly , 2011 . T. White. Hadoop - The Definitive Guide: Storage and Analysis at Internet Scale (2. ed.). O'Reilly, 2011."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2535570.2488334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:03:39Z","timestamp":1672225419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2535570.2488334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.14778\/2535570.2488334"],"URL":"https:\/\/doi.org\/10.14778\/2535570.2488334","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,2]]}}}