{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:14Z","timestamp":1775638454351,"version":"3.50.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,2]]},"abstract":"<jats:p>We study the problem of finding and monitoring fixed-size subgraphs in a continually changing large-scale graph. We present the first approach that (i) performs worst-case optimal computation and communication, (ii) maintains a total memory footprint linear in the number of input edges, and (iii) scales down per-worker computation, communication, and memory requirements linearly as the number of workers increases, even on adversarially skewed inputs.<\/jats:p>\n          <jats:p>\n            Our approach is based on worst-case optimal join algorithms, recast as a data-parallel dataflow computation. We describe the general algorithm and modifications that make it robust to skewed data, prove theoretical bounds on its resource requirements in the\n            <jats:italic>massively parallel computing<\/jats:italic>\n            model, and implement and evaluate it on graphs containing as many as 64 billion edges. The underlying algorithm and ideas generalize from finding and monitoring subgraphs to the more general problem of computing and maintaining relational equi-joins over dynamic relations.\n          <\/jats:p>","DOI":"10.14778\/3184470.3184473","type":"journal-article","created":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T19:50:53Z","timestamp":1581882653000},"page":"691-704","source":"Crossref","is-referenced-by-count":53,"title":["Distributed evaluation of subgraph queries using worst-case optimal low-memory dataflows"],"prefix":"10.14778","volume":"11","author":[{"given":"Khaled","family":"Ammar","sequence":"first","affiliation":[{"name":"University of Waterloo"}]},{"given":"Frank","family":"McSherry","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich"}]},{"given":"Semih","family":"Salihoglu","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Manas","family":"Joglekar","sequence":"additional","affiliation":[{"name":"Google, Inc"}]}],"member":"320","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824091"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488334"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_6_1","volume-title":"ICDT","author":"Afrati Foto N.","year":"2017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_2_1_9_1","author":"Atserias A.","year":"2013","journal-title":"Size Bounds and Query Plans for Relational Joins. SIAM Journal on Computing"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/16856.16861"},{"key":"e_1_2_1_14_1","first-page":"38","author":"Carbone Paris","year":"2015","journal-title":"Single Engine. IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_16_1","volume-title":"EDBT","author":"Choudhury Sutanay","year":"2015"},{"key":"e_1_2_1_17_1","volume-title":"OSDI","author":"Dean J.","year":"2004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.989932"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816681"},{"key":"e_1_2_1_21_1","unstructured":"Apache Incubator Giraph. http:\/\/incubator.apache.org\/giraph\/.  Apache Incubator Giraph. http:\/\/incubator.apache.org\/giraph\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170066"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056110"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.103"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Manas Joglekar and Christopher R\u00e9. It's All a Matter of Degree. Theory of Computing Systems Sep 2017.  Manas Joglekar and Christopher R\u00e9. It's All a Matter of Degree. Theory of Computing Systems Sep 2017.","DOI":"10.1007\/s00224-017-9811-8"},{"key":"e_1_2_1_29_1","unstructured":"Dataflow Join. https:\/\/github.com\/frankmcsherry\/timely-dataflow.  Dataflow Join. https:\/\/github.com\/frankmcsherry\/timely-dataflow."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"K. Ammar and F. McSherry and S. Salihoglu and M. Joglekar. Distributed Evaluation of Subgraph Queries Using Worst-case Optimal and Low-Memory Dataflows. CoRR abs\/1802.03760 2018.  K. Ammar and F. McSherry and S. Salihoglu and M. Joglekar. Distributed Evaluation of Subgraph Queries Using Worst-case Optimal and Low-Memory Dataflows. CoRR abs\/1802.03760 2018.","DOI":"10.14778\/3184470.3184473"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_32_1","volume-title":"ICDT","author":"Koutris Paraschos","year":"2016"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0459-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926534.2926544"},{"key":"e_1_2_1_35_1","unstructured":"The Laboratory for Web Algorithmics. http:\/\/law.dsi.unimi.it\/datasets.php.  The Laboratory for Web Algorithmics. http:\/\/law.dsi.unimi.it\/datasets.php."},{"key":"e_1_2_1_36_1","unstructured":"Jure Leskovec and Andrej Krevl. SNAP: Stanford Network Analysis Project. http:\/\/snap.stanford.edu June 2014.  Jure Leskovec and Andrej Krevl. SNAP: Stanford Network Analysis Project. http:\/\/snap.stanford.edu June 2014."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_39_1","volume-title":"HOTOS","author":"McSherry Frank","year":"2015"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_41_1","unstructured":"Neo4j Home Page. http:\/\/neo4j.com\/.  Neo4j Home Page. http:\/\/neo4j.com\/."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594547"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Rada Chirkova and Jun Yang. Materialized Views. Foundations and Trends in Databases 4(4) 2012.   Rada Chirkova and Jun Yang. Materialized Views. Foundations and Trends in Databases 4(4) 2012.","DOI":"10.1561\/1900000020"},{"key":"e_1_2_1_49_1","unstructured":"Rust. https:\/\/www.rust-lang.org.  Rust. https:\/\/www.rust-lang.org."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_51_1","unstructured":"SPARQL Specification. http:\/\/www.w3.org\/TR\/rdf-sparql-query.  SPARQL Specification. http:\/\/www.w3.org\/TR\/rdf-sparql-query."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505741"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_55_1","unstructured":"Timely Dataflow. https:\/\/github.com\/frankmcsherry\/timely-dataflow.  Timely Dataflow. https:\/\/github.com\/frankmcsherry\/timely-dataflow."},{"key":"e_1_2_1_56_1","unstructured":"Titan Home Page. http:\/\/thinkaurelius.github.io\/titan\/.  Titan Home Page. http:\/\/thinkaurelius.github.io\/titan\/."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595641"},{"key":"e_1_2_1_58_1","unstructured":"Todd L. Veldhuizen. Leapfrog Triejoin: a worst-case optimal join algorithm. CoRR abs\/1210.0481 2012.  Todd L. Veldhuizen. Leapfrog Triejoin: a worst-case optimal join algorithm. CoRR abs\/1210.0481 2012."},{"key":"e_1_2_1_59_1","unstructured":"Todd L. Veldhuizen. Incremental Maintenance for Leapfrog Triejoin. CoRR abs\/1303.5313 2013.  Todd L. Veldhuizen. Incremental Maintenance for Leapfrog Triejoin. CoRR abs\/1303.5313 2013."},{"key":"e_1_2_1_60_1","unstructured":"Web Data Commons. http:\/\/www.webdatacommons.org\/hyperlinkgraph.  Web Data Commons. http:\/\/www.webdatacommons.org\/hyperlinkgraph."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/1927730.1927748"},{"key":"e_1_2_1_62_1","first-page":"94","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981"},{"key":"e_1_2_1_63_1","volume-title":"ICDE","author":"Yi Ke","year":"2003"},{"key":"e_1_2_1_64_1","volume-title":"Spark: Cluster Computing with Working Sets. In HotCloud","author":"Chowdhury M.","year":"2010"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488333"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002974.2002976"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3184470.3184473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:57:26Z","timestamp":1672225046000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3184470.3184473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":67,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.14778\/3184470.3184473"],"URL":"https:\/\/doi.org\/10.14778\/3184470.3184473","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}