{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:20:38Z","timestamp":1771485638891,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF:SPX 1822738"],"award-info":[{"award-number":["CCF:SPX 1822738"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS:BIGDATA 1546108"],"award-info":[{"award-number":["IIS:BIGDATA 1546108"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DARPA","award":["SI3CMD"],"award-info":[{"award-number":["SI3CMD"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331609","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"481-490","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Massively Parallel Computation of Matching and MIS in Sparse Graphs"],"prefix":"10.1145","author":[{"given":"Soheil","family":"Behnezhad","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahsa","family":"Derakhshan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuela","family":"Fischer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard M.","family":"Karp","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"ETH Zurich & University of Freiburg, Zurich\/Freiburg, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_2_1","volume-title":"Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint: 1711","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab Mirrokni , and Cliff Stein . 2017 . Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint: 1711 .03076 (2017). Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. 2017. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint: 1711.03076 (2017)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_5_1","volume-title":"the Proceedings of the Conference on Neural Information Processing Systems (NIPS). 6867--6877","author":"Bateni MohammadHossein","year":"2017","unstructured":"MohammadHossein Bateni , Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Raimondas Kiveris , Silvio Lattanzi , and Vahab Mirrokni . 2017 . Affinity Clustering: Hierarchical Clustering at Scale . In the Proceedings of the Conference on Neural Information Processing Systems (NIPS). 6867--6877 . http:\/\/papers.nips.cc\/paper\/7262-affinity-clustering-hierarchical-clustering-at-scale.pdf MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. 2017. Affinity Clustering: Hierarchical Clustering at Scale. In the Proceedings of the Conference on Neural Information Processing Systems (NIPS). 6867--6877. http:\/\/papers.nips.cc\/paper\/7262-affinity-clustering-hierarchical-clustering-at-scale.pdf"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Sebastian Brandt Manuela Fischer and Jara Uitto. 2019. Breaking The Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. In the Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO). to appear.  Sebastian Brandt Manuela Fischer and Jara Uitto. 2019. Breaking The Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. In the Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO). to appear.","DOI":"10.1007\/978-3-030-24922-9_9"},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs","volume":"29","author":"Cormode Graham","year":"2017","unstructured":"Graham Cormode , Hossein Jowhari , Morteza Monemizadeh , and S. Muthukrishnan . 2017 . The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs . In the Proceedings of the Annual European Symposium on Algorithms (ESA). 29 : 1 -- 29 :15. Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. 2017. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In the Proceedings of the Annual European Symposium on Algorithms (ESA). 29:1--29:15.","journal-title":"the Proceedings of the Annual European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_12_1","volume-title":"Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 1217--1233","author":"Esfandiari Hossein","year":"2015","unstructured":"Hossein Esfandiari , Mohammad Taghi Hajiaghayi , Vahid Liaghat , Morteza Monemizadeh , and Krzysztof Onak . 2015 . Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 1217--1233 . Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. 2015. Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 1217--1233."},{"key":"e_1_3_2_1_13_1","volume-title":"An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 270--277","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari . 2016 . An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 270--277 . Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). 270--277."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_15_1","volume-title":"Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and Jara Uitto . 2019 . Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA). Mohsen Ghaffari and Jara Uitto. 2019. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In the Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_15"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_18_1","volume-title":"Estimating Weighted Matchings in o(n) Space. CoRR","author":"Grigorescu Elena","year":"2016","unstructured":"Elena Grigorescu , Morteza Monemizadeh , and Samson Zhou . 2016. Estimating Weighted Matchings in o(n) Space. CoRR , Vol. abs\/ 1604 .07467 ( 2016 ). arxiv: 1604.07467 http:\/\/arxiv.org\/abs\/1604.07467 Elena Grigorescu, Morteza Monemizadeh, and Samson Zhou. 2016. Estimating Weighted Matchings in o(n) Space. CoRR, Vol. abs\/1604.07467 (2016). arxiv: 1604.07467 http:\/\/arxiv.org\/abs\/1604.07467"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0174-8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835772"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_3_2_1_29_1","first-page":"1","article-title":"Fully Dynamic MIS in Uniformly Sparse Graphs","volume":"92","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak , Baruch Schieber , Shay Solomon , and Nicole Wein . 2018 . Fully Dynamic MIS in Uniformly Sparse Graphs . In the Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). 92 : 1 -- 92 :14. Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. 2018. Fully Dynamic MIS in Uniformly Sparse Graphs. In the Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). 92:1--92:14.","journal-title":"the Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_31_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Pemmaraju Sriram V.","unstructured":"Sriram V. Pemmaraju . 2001. Equitable Coloring Extends Chernoff-Hoeffding Bounds . In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques . Springer , 285--296. Sriram V. Pemmaraju. 2001. Equitable Coloring Extends Chernoff-Hoeffding Bounds. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Springer, 285--296."},{"key":"e_1_3_2_1_32_1","volume-title":"Hadoop: The Definitive Guide.","author":"White Tom","year":"2012","unstructured":"Tom White . 2012 . Hadoop: The Definitive Guide. Tom White. 2012. Hadoop: The Definitive Guide."},{"key":"e_1_3_2_1_33_1","first-page":"95","article-title":"Spark","volume":"10","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark : Cluster Computing with Working Sets. HotCloud , Vol. 10 (2010), 95 . Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. HotCloud, Vol. 10 (2010), 95.","journal-title":"Cluster Computing with Working Sets. HotCloud"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331609","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:02Z","timestamp":1750208522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":33,"alternative-id":["10.1145\/3293611.3331609","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331609","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}