{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:11:46Z","timestamp":1784099506284,"version":"3.55.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p>Subgraph enumeration aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph. As the subgraph isomorphism operation is computationally intensive, researchers have recently focused on solving this problem in distributed environments, such as MapReduce and Pregel. Among them, the state-of-the-art algorithm, Twin TwigJoin, is proven to be instance optimal based on a left-deep join framework. However, it is still not scalable to large graphs because of the constraints in the left-deep join framework and that each decomposed component (join unit) must be a star. In this paper, we propose SEED - a scalable sub-graph enumeration approach in the distributed environment. Compared to Twin TwigJoin, SEED returns optimal solution in a generalized join framework without the constraints in Twin TwigJoin. We use both star and clique as the join units, and design an effective distributed graph storage mechanism to support such an extension. We develop a comprehensive cost model, that estimates the number of matches of any given pattern graph by considering power-law degree distribution in the data graph. We then generalize the left-deep join framework and develop a dynamic-programming algorithm to compute an optimal bushy join plan. We also consider overlaps among the join units. Finally, we propose clique compression to further improve the algorithm by reducing the number of the intermediate results. Extensive performance studies are conducted on several real graphs, one containing billions of edges. The results demonstrate that our algorithm outperforms all other state-of-the-art algorithms by more than one order of magnitude.<\/jats:p>","DOI":"10.14778\/3021924.3021937","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T15:29:41Z","timestamp":1485271781000},"page":"217-228","source":"Crossref","is-referenced-by-count":88,"title":["Scalable distributed subgraph enumeration"],"prefix":"10.14778","volume":"10","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"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia and University of Technology, Sydney, Australia"}],"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"}]},{"given":"Shiyu","family":"Yang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,11]]},"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.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"issue":"1","key":"e_1_2_1_4_1","first-page":"21","volume":"7","author":"Chung F.","year":"2003","journal-title":"Eigenvalues of random power law graphs. Annals of Combinatorics"},{"key":"e_1_2_1_5_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_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_7_1","volume-title":"Proc. of OSDI'04","author":"Dean J.","year":"2004"},{"key":"e_1_2_1_8_1","volume-title":"Publ. Math. Inst. Hungary. Acad. Sci.","author":"Erdos P.","year":"1960"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873611"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758222.1758229"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594530"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115813"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356928"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124374"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_1_20_1","volume-title":"Scalable distributed subgraph enumeration. Technical report","author":"Lai L.","year":"2016"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_44"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_23_1","volume-title":"Uncovering biological network function via graphlet degree signatures. Cancer Inform, 6","author":"Milenkovic T.","year":"2008"},{"key":"e_1_2_1_24_1","volume-title":"Network motifs: Simple building blocks of complex networks. Science, 298(5594)","author":"Milo R.","year":"2002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci0100548"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_29_1","volume-title":"AISTATS","author":"Shervashidze N.","year":"2009"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_31_1","volume-title":"COCOON'05","author":"Viger F."},{"key":"e_1_2_1_32_1","volume-title":"Hadoop: The Definitive Guide","author":"White T.","year":"2009"},{"key":"e_1_2_1_33_1","first-page":"10","volume-title":"HotCloud'10","author":"Zaharia M."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_35_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\/3021924.3021937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:29:00Z","timestamp":1672219740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3021924.3021937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.14778\/3021924.3021937"],"URL":"https:\/\/doi.org\/10.14778\/3021924.3021937","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}