{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:15:00Z","timestamp":1784099700556,"version":"3.55.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p>Subgraph enumeration, which aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph, is a fundamental graph problem with a wide range of applications. However, existing sequential algorithms for subgraph enumeration fall short in handling large graphs due to the involvement of computationally intensive subgraph isomorphism operations. Thus, some recent researches focus on solving the problem using MapReduce. Nevertheless, exiting MapReduce approaches are not scalable to handle very large graphs since they either produce a huge number of partial results or consume a large amount of memory. Motivated by this, in this paper, we propose a new algorithm TwinTwigJoin based on a left-deep-join framework in MapReduce, in which the basic join unit is a TwinTwig (an edge or two incident edges of a node). We show that in the Erd\u00f6s-R\u00e9nyi random-graph model, TwinTwigJoin is instance optimal in the left-deep-join framework under reasonable assumptions, and we devise an algorithm to compute the optimal join plan. Three optimization strategies are explored to improve our algorithm. Furthermore, we discuss how our approach can be adapted in the power-law random-graph model. We conduct extensive performance studies in several real graphs, one of which contains billions of edges. Our approach significantly outperforms existing solutions in all tests.<\/jats:p>","DOI":"10.14778\/2794367.2794368","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T14:37:34Z","timestamp":1438267054000},"page":"974-985","source":"Crossref","is-referenced-by-count":94,"title":["Scalable subgraph enumeration in MapReduce"],"prefix":"10.14778","volume":"8","author":[{"given":"Longbin","family":"Lai","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia and University of Technology, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia and East China Normal University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544814"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488334"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4_7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_9_1","volume-title":"The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3)","author":"Chung F. R. K.","year":"2003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_11_1","volume-title":"Proc. of OSDI'04","author":"Dean J.","year":"2004"},{"issue":"02","key":"e_1_2_1_12_1","first-page":"145","volume":"6","author":"Eades P.","year":"1996","journal-title":"An algorithm for drawing a hierarchical graph. International Journal of Computational Geometry & Applications"},{"key":"e_1_2_1_13_1","volume-title":"Publ. Math. Inst. Hungary. Acad. Sci.","author":"Erdos P.","year":"1960"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873611"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758222.1758229"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of OSDI'12","author":"Gonzalez J.","year":"2012"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124374"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_44"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187963"},{"key":"e_1_2_1_26_1","volume-title":"Uncovering biological network function via graphlet degree signatures. Cancer Inform, 6","author":"Milenkovic T.","year":"2008"},{"key":"e_1_2_1_27_1","volume-title":"Network motifs: Simple building blocks of complex networks. Science, 298(5594)","author":"Milo R.","year":"2002"},{"key":"e_1_2_1_28_1","volume-title":"AISTATS","author":"Shervashidze N.","year":"2009"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci0100548"},{"key":"e_1_2_1_32_1","volume-title":"Optimizing join orders. Technical report","author":"Steinbrunn M.","year":"1993"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463719"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958125"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807296"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_40_1","volume-title":"Collective dynamics of 'small-world' networks. Nature, 6684(393)","author":"Watts D.","year":"1998"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350238"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2794367.2794368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:09:48Z","timestamp":1672225788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2794367.2794368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":43,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.14778\/2794367.2794368"],"URL":"https:\/\/doi.org\/10.14778\/2794367.2794368","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}