{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:37:44Z","timestamp":1787503064319,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617955,CCF- 1740833,CCF-1714818,CCF-1822809,CCF-1703925"],"award-info":[{"award-number":["CCF-1617955,CCF- 1740833,CCF-1714818,CCF-1822809,CCF-1703925"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Google Research Award, Google PhD Fellowship"],"award-info":[{"award-number":["Google Research Award, Google PhD Fellowship"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014155","name":"Simons Foundation","doi-asserted-by":"publisher","award":["#491119 to Alexandr Andoni"],"award-info":[{"award-number":["#491119 to Alexandr Andoni"]}],"id":[{"id":"10.13039\/100014155","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384321","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"322-335","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Parallel approximate undirected shortest paths via low hop emulators"],"prefix":"10.1145","author":[{"given":"Alexandr","family":"Andoni","sequence":"first","affiliation":[{"name":"Columbia University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Clifford","family":"Stein","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peilin","family":"Zhong","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105815"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni Clifford Stein and Peilin Zhong. 2019. Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. arXiv preprint arXiv:1911.01956.  Alexandr Andoni Clifford Stein and Peilin Zhong. 2019. Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators. arXiv preprint arXiv:1911.01956.","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582120"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_8_1","volume-title":"Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC","author":"Becker Ruben","year":"2017","unstructured":"Ruben Becker , Andreas Karrenbauer , Sebastian Krinninger , and Christoph Lenzen . 2017 . Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017). Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017)."},{"key":"e_1_3_2_1_9_1","volume-title":"Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, abs\/1802.10297","author":"Behnezhad Soheil","year":"2018","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , and MohammadTaghi Hajiaghayi . 2018 . Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, abs\/1802.10297 , 2018. arXiv preprint arXiv:1802.10297. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. 2018. Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, abs\/1802.10297, 2018. arXiv preprint arXiv:1802.10297."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.16"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935765"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1425"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331633"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195089"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0813"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039734"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_22_1","volume-title":"Brief Announcement: Massively Parallel Approximate Distance Sketches. In 33rd International Symposium on Distributed Computing (DISC","author":"Dinitz Michael","year":"2019","unstructured":"Michael Dinitz and Yasamin Nazari . 2019 . Brief Announcement: Massively Parallel Approximate Distance Sketches. In 33rd International Symposium on Distributed Computing (DISC 2019). Michael Dinitz and Yasamin Nazari. 2019. Brief Announcement: Massively Parallel Approximate Distance Sketches. In 33rd International Symposium on Distributed Computing (DISC 2019)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.22"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824786"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00071"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231591"},{"key":"e_1_3_2_1_29_1","first-page":"374","article-title":"Sorting, Searching, and Simulation in the MapReduce Framework","volume":"7074","author":"Goodrich Michael T","year":"2011","unstructured":"Michael T Goodrich , Nodari Sitchinava , and Qin Zhang . 2011 . Sorting, Searching, and Simulation in the MapReduce Framework .. In ISAAC. 7074 , 374 \u2013 383 . Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework.. In ISAAC. 7074, 374\u2013383.","journal-title":"ISAAC."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Thomas Dueholm Hansen Haim Kaplan Robert E Tarjan and Uri Zwick. 2015. Hollow Heaps. In International Colloquium on Automata Languages and Programming. 689\u2013700.  Thomas Dueholm Hansen Haim Kaplan Robert E Tarjan and Uri Zwick. 2015. Hollow Heaps. In International Colloquium on Automata Languages and Programming. 689\u2013700.","DOI":"10.1007\/978-3-662-47672-7_56"},{"key":"e_1_3_2_1_31_1","volume-title":"Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science.","author":"Henzinger Monika","year":"2014","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . 2014 . Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2014. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_1_32_1","volume-title":"An almost-tight distributed algorithm for computing single-source shortest paths","author":"Henzinger Monika","year":"2016","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . 2016. An almost-tight distributed algorithm for computing single-source shortest paths . 2016 . Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. An almost-tight distributed algorithm for computing single-source shortest paths. 2016."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Monika Henzinger Sebastian Krinninger and Danupon Nanongkai. 2019. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM J. Comput. STOC16\u201398.  Monika Henzinger Sebastian Krinninger and Danupon Nanongkai. 2019. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM J. Comput. STOC16\u201398.","DOI":"10.1137\/16M1097808"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.10.001"},{"key":"e_1_3_2_1_35_1","volume-title":"Workshop on Statistical and Computational Theories of Vision (at ICCV).","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk and Nitin Thaper . 2003 . Fast image retrieval via embeddings . In Workshop on Statistical and Computational Theories of Vision (at ICCV). Piotr Indyk and Nitin Thaper. 2003. Fast image retrieval via embeddings. In Workshop on Statistical and Computational Theories of Vision (at ICCV)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Michael Isard Mihai Budiu Yuan Yu Andrew Birrell and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review. 41 59\u201372.  Michael Isard Mihai Budiu Yuan Yu Andrew Birrell and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review. 41 59\u201372.","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_3_2_1_39_1","unstructured":"Andrey Boris Khesin Aleksandar Nikolov and Dmitry Paramonov. 2019. Preconditioning for the Geometric Transportation Problem. arXiv preprint arXiv:1902.08384.  Andrey Boris Khesin Aleksandar Nikolov and Dmitry Paramonov. 2019. Preconditioning for the Geometric Transportation Problem. arXiv preprint arXiv:1902.08384."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722157"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129785"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/120888843"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806698"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.28"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039735"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0968"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265923"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_61_1","first-page":"10","article-title":"Spark: Cluster computing with working sets","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 , 10 , 10 - 10 (2010), 95. Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets.. HotCloud, 10, 10-10 (2010), 95.","journal-title":"HotCloud"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:56Z","timestamp":1750185176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":61,"alternative-id":["10.1145\/3357713.3384321","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384321","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}