{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:23:54Z","timestamp":1777965834417,"version":"3.51.4"},"reference-count":63,"publisher":"Emerald","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>The algorithms community has been modeling the underlying key features and constraints of massively parallel frameworks and using these models to discover new algorithmic techniques tailored to them. This monograph focuses on the Massively Parallel Model of Computation (MPC) framework, also known as the MapReduce model in the literature. It describes algorithmic tools that have been developed to leverage the unique features of the MPC framework. These tools were chosen for their broad applicability, as they can serve as building blocks to design new algorithms. The monograph is not exhaustive and includes topics such as partitioning and coresets, sample and prune, dynamic programming, round compression, and lower bounds.<\/jats:p>","DOI":"10.1561\/2400000025","type":"journal-article","created":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T03:36:36Z","timestamp":1695872196000},"page":"340-417","source":"Crossref","is-referenced-by-count":4,"title":["Massively Parallel Computation: Algorithms and Applications"],"prefix":"10.1108","volume":"5","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California , ,","place":["Merced, USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google , ,","place":["Mountain View, USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvo","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google , ,","place":["Barcelona, Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University ,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Google , ,","place":["New York, USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2023,9,28]]},"reference":[{"key":"2026033014423126700_ref001","volume-title":"Upper and Lower Bounds on the Cost of a Map-Reduce Computation","author":"Afrati","year":"2012"},{"key":"2026033014423126700_ref002","first-page":"574","article-title":"Parallel Algorithms for Geometric Graph Problems","volume-title":"STOC","author":"Andoni","year":"2014"},{"key":"2026033014423126700_ref003","first-page":"674","article-title":"Parallel Graph Connectivity in Log Diameter Rounds","volume-title":"FOCS","author":"Andoni","year":"2018"},{"key":"2026033014423126700_ref004","first-page":"1616","article-title":"Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs","volume-title":"SODA","author":"Assadi","year":"2019"},{"key":"2026033014423126700_ref005","first-page":"333","article-title":"Distributed Weighted Matching via Randomized Composable Coresets","volume-title":"ICML","author":"Assadi","year":"2019"},{"issue":"5","key":"2026033014423126700_ref006","first-page":"454","article-title":"Densest Subgraph in Streaming and MapReduce","volume":"5","author":"Bahmani","year":"2012","journal-title":"PVLDB"},{"issue":"7","key":"2026033014423126700_ref007","first-page":"622","article-title":"Scalable K-Means++","volume":"5","author":"Bahmani","year":"2012","journal-title":"PVLDB"},{"key":"2026033014423126700_ref008","first-page":"6867","article-title":"Affinity clustering: Hierarchical clustering at scale","volume-title":"NIPS","author":"Bateni","year":"2017"},{"issue":"6","key":"2026033014423126700_ref009","doi-asserted-by":"crossref","first-page":"40:1","DOI":"10.1145\/3125644","article-title":"Communication steps for parallel query processing","volume":"64","author":"Beame","year":"2017","journal-title":"JACM"},{"key":"2026033014423126700_ref010","first-page":"1615","article-title":"Near-Optimal Massively Parallel Graph Connectivity","volume-title":"FOCS","author":"Behnezhad","year":"2019"},{"key":"2026033014423126700_ref011","first-page":"1637","article-title":"Exponentially Faster Massively Parallel Maximal Matching","volume-title":"FOCS","author":"Behnezhad","year":"2019"},{"key":"2026033014423126700_ref012","first-page":"569","article-title":"Distributed Clustering via LSH Based Data Partitioning","volume-title":"ICML","author":"Bhaskara","year":"2018"},{"key":"2026033014423126700_ref013","first-page":"676","article-title":"A lower bound technique for communication on BSP with application to the FFT","volume-title":"ECPP","author":"Bilardi","year":"2012"},{"key":"2026033014423126700_ref014","first-page":"233","article-title":"Scalable K-Means by ranked retrieval","volume-title":"WSDM","author":"Broder","year":"2014"},{"issue":"7","key":"2026033014423126700_ref015","doi-asserted-by":"crossref","first-page":"766","DOI":"10.14778\/3317315.3317319","article-title":"Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially","volume":"12","author":"Ceccarello","year":"2019","journal-title":"Proc. VLDB Endow"},{"key":"2026033014423126700_ref016","first-page":"471","article-title":"The Complexity of (\u0394+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation","volume-title":"PODC","author":"Chang","year":"2019"},{"key":"2026033014423126700_ref017","first-page":"141","article-title":"New lower bounds for Massively Parallel Computation from query complexity","volume-title":"SPAA","author":"Charikar","year":"2020"},{"key":"2026033014423126700_ref018","first-page":"231","article-title":"Max-cover in map-reduce","volume-title":"WWW","author":"Chierichetti","year":"2010"},{"key":"2026033014423126700_ref019","first-page":"2069","article-title":"Correlation Clustering in Constant Many Parallel Rounds","volume-title":"ICML","author":"Cohen-Addad","year":"2021"},{"key":"2026033014423126700_ref020","article-title":"Parallel and Efficient Hierarchical k-Median Clustering","volume-title":"NeurIPS","author":"Cohen-Addad","year":"2021"},{"key":"2026033014423126700_ref021","first-page":"162","article-title":"Deterministic massively parallel connectivity","volume-title":"STOC","author":"Coy","year":"2022"},{"key":"2026033014423126700_ref022","first-page":"471","article-title":"Round compression for parallel matching algorithms","volume-title":"STOC","author":"Czumaj","year":"2018"},{"key":"2026033014423126700_ref023","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"MapReduce: Simplified Data Processing on Large Clusters","volume":"51","author":"Dean","year":"2008","journal-title":"CACM"},{"key":"2026033014423126700_ref024","first-page":"681","article-title":"Fast clustering using MapReduce","volume-title":"KDD","author":"Ene","year":"2011"},{"key":"2026033014423126700_ref025","first-page":"787","article-title":"Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions","volume-title":"ICML","author":"Ene","year":"2015"},{"key":"2026033014423126700_ref026","first-page":"1396","article-title":"Parallel and Streaming Algorithms for K-Core Decomposition","volume-title":"ICML","author":"Esfandiari","year":"2018"},{"issue":"4","key":"2026033014423126700_ref027","doi-asserted-by":"crossref","first-page":"66:1","DOI":"10.1145\/1824777.1824786","article-title":"On distributing symmetric streaming computations","volume":"6","author":"Feldman","year":"2010","journal-title":"TALG"},{"issue":"1","key":"2026033014423126700_ref028","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2071379.2071383","article-title":"Cache-Oblivious Algorithms","volume":"8","author":"Frigo","year":"2012","journal-title":"TALG"},{"key":"2026033014423126700_ref029","first-page":"129","article-title":"Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover","volume-title":"PODC","author":"Ghaffari","year":"2018"},{"key":"2026033014423126700_ref030","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2019.00097","article-title":"Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds","volume-title":"FOCS. FOCS \u201819","author":"Ghaffari","year":"2019"},{"key":"2026033014423126700_ref031","first-page":"2201","article-title":"Improved Parallel Algorithms for Density-Based Network Clustering","volume-title":"ICML","author":"Ghaffari","year":"2019"},{"key":"2026033014423126700_ref032","first-page":"1636","article-title":"Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation","volume-title":"SODA","author":"Ghaffari","year":"2019"},{"key":"2026033014423126700_ref033","volume-title":"Complexity Measures for MapReduce, and Comparison to Parallel Computing","author":"Goel","year":"2012"},{"key":"2026033014423126700_ref034","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","article-title":"Clustering to minimize the maximum intercluster distance","volume":"38","author":"Gonzalez","year":"1985","journal-title":"TCS"},{"key":"2026033014423126700_ref035","volume-title":"Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry","author":"Goodrich","year":"2010"},{"key":"2026033014423126700_ref036","first-page":"374","article-title":"Sorting, Searching, and Simulation in the Mapreduce Framework","volume-title":"ISAAC","author":"Goodrich","year":"2011"},{"key":"2026033014423126700_ref037","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","article-title":"Lessons from the congested clique applied to MapReduce","volume":"608","author":"Hegeman","year":"2015","journal-title":"TCS"},{"key":"2026033014423126700_ref038","first-page":"65","article-title":"Brief Announcement: Fast and Better Distributed MapReduce Algorithms for k-Center Clustering","volume-title":"SPAA","author":"Im","year":"2015"},{"key":"2026033014423126700_ref039","volume-title":"A Conditional Lower Bound on Graph Connectivity in MapReduce","author":"Im","year":"2019"},{"key":"2026033014423126700_ref040","first-page":"798","article-title":"Efficient massively parallel methods for dynamic programming","volume-title":"STOC","author":"Im","year":"2017"},{"key":"2026033014423126700_ref041","first-page":"100","article-title":"Composable core-sets for diversity and coverage maximization","volume-title":"PODS","author":"Indyk","year":"2014"},{"key":"2026033014423126700_ref042","first-page":"384","article-title":"On the complexity of list ranking in the parallel external memory model","volume-title":"MFCS","author":"Jacob","year":"2014"},{"key":"2026033014423126700_ref043","first-page":"938","article-title":"A Model of Computation for MapReduce","volume-title":"SODA","author":"Karloff","year":"2010"},{"issue":"4","key":"2026033014423126700_ref044","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1561\/1900000055","article-title":"Algorithmic Aspects of Parallel Data Processing","volume":"8","author":"Koutris","year":"2018","journal-title":"Foundations and Trends in Databases"},{"issue":"3","key":"2026033014423126700_ref045","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2809814","article-title":"Fast Greedy Algorithms in MapReduce and Streaming","volume":"2","author":"Kumar","year":"2015","journal-title":"TOPC"},{"key":"2026033014423126700_ref046","first-page":"73","article-title":"A framework for parallelizing hierarchical clustering methods","volume-title":"ECML\/PKDD","author":"Lattanzi","year":"2019"},{"key":"2026033014423126700_ref047","first-page":"85","article-title":"Filtering: a method for solving graph problems in MapReduce","volume-title":"SPAA","author":"Lattanzi","year":"2011"},{"key":"2026033014423126700_ref048","first-page":"295","article-title":"Brief announcement: exponential speed-up of local algorithms using non-local communication","volume-title":"PODC","author":"Lenzen","year":"2010"},{"key":"2026033014423126700_ref049","first-page":"331","article-title":"Distributive graph algorithms global solutions from local data","volume-title":"FOCS","author":"Linial","year":"1987"},{"key":"2026033014423126700_ref050","first-page":"1063","article-title":"Fast Distributed k-Center Clustering with Outliers on Massive Data","volume-title":"NIPS","author":"Malkomes","year":"2015"},{"issue":"1","key":"2026033014423126700_ref051","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/2627692.2627694","article-title":"Graph stream algorithms: a survey","volume":"43","author":"McGregor","year":"2014","journal-title":"SIGMOD Record"},{"key":"2026033014423126700_ref052","first-page":"2049","article-title":"Distributed Submodular Maximization: Identifying Representative Elements in Massive Data","volume-title":"NIPS","author":"Mirzasoleiman","year":"2013"},{"key":"2026033014423126700_ref053","doi-asserted-by":"crossref","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher","DOI":"10.1017\/CBO9780511813603"},{"issue":"1","key":"2026033014423126700_ref054","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An Analysis of Approximations for Maximizing Submodular Set Functions-I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Program"},{"key":"2026033014423126700_ref055","first-page":"1739","article-title":"MapReduce Triangle Enumeration With Guarantees","volume-title":"CIKM","author":"Park","year":"2014"},{"key":"2026033014423126700_ref056","first-page":"235","article-title":"Space-round Tradeoffs for MapReduce Computations","volume-title":"ICS","author":"Pietracaprina","year":"2012"},{"key":"2026033014423126700_ref057","first-page":"1236","article-title":"The Power of Randomization: Distributed Submodular Maximization on Massive Datasets","volume":"37","author":"da Ponte Barbosa","year":"2015","journal-title":"ICML"},{"key":"2026033014423126700_ref058","first-page":"645","article-title":"A New Framework for Distributed Submodular Maximization","volume-title":"FOCS","author":"da Ponte Barbosa","year":"2016"},{"key":"2026033014423126700_ref059","article-title":"Shuffles and Circuits (On Lower Bounds on Massively Parallel Computation)","volume-title":"SPAA \u201816","author":"Roughgarden","year":"2016"},{"key":"2026033014423126700_ref060","first-page":"607","article-title":"Counting triangles and the curse of the last reducer","volume-title":"WWW","author":"Suri","year":"2011"},{"issue":"8","key":"2026033014423126700_ref061","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","article-title":"A bridging model for parallel computation","volume":"33","author":"Valiant","year":"1990","journal-title":"CACM"},{"key":"2026033014423126700_ref062","doi-asserted-by":"crossref","volume-title":"The Design of Approximation Algorithms","author":"Williamson","DOI":"10.1017\/CBO9780511921735"},{"key":"2026033014423126700_ref063","first-page":"390","article-title":"SAHAD: Subgraph Analysis in Massive Networks Using Hadoop","volume-title":"IPDPS","author":"Zhao","year":"2012"}],"container-title":["Foundations and Trends\u00ae in Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/5\/4\/340\/10976024\/2400000025en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/5\/4\/340\/10976024\/2400000025en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:14:43Z","timestamp":1777486483000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftopt\/article\/5\/4\/340\/1324795\/Massively-Parallel-Computation-Algorithms-and"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,9,28]]}},"URL":"https:\/\/doi.org\/10.1561\/2400000025","relation":{},"ISSN":["2167-3888","2167-3918"],"issn-type":[{"value":"2167-3888","type":"print"},{"value":"2167-3918","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}