{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T04:06:28Z","timestamp":1769832388350,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"project SID2017 of the University of Padova"},{"name":"Institute for Information 8 communications Technology Promotio"},{"name":"the Korea governmen","award":["R0190-15-2012"],"award-info":[{"award-number":["R0190-15-2012"]}]},{"name":"Chongqing Liangjiang KAIST International Program"},{"DOI":"10.13039\/501100013223","name":"Chongqing Research Program of Basic Research and Frontier Technology","doi-asserted-by":"crossref","award":["cstc2017jcyjAX0089"],"award-info":[{"award-number":["cstc2017jcyjAX0089"]}],"id":[{"id":"10.13039\/501100013223","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time.<\/jats:p>\n          <jats:p>\n            In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE (\n            <jats:italic>Pre-partitioned Triangle Enumeration<\/jats:italic>\n            ), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE (\n            <jats:italic>Pre-partitioned Subgraph Enumeration<\/jats:italic>\n            ), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3\n            <jats:italic>trillion<\/jats:italic>\n            triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algorithm.\n          <\/jats:p>","DOI":"10.1145\/3237191","type":"journal-article","created":{"date-parts":[[2018,10,2]],"date-time":"2018-10-02T12:09:22Z","timestamp":1538482162000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Enumerating Trillion Subgraphs On Distributed Systems"],"prefix":"10.1145","volume":"12","author":[{"given":"Ha-Myung","family":"Park","sequence":"first","affiliation":[{"name":"KAIST"}]},{"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[{"name":"University of Padova"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen"}]},{"given":"Chin-Wan","family":"Chung","sequence":"additional","affiliation":[{"name":"Chongqing University of Technology and KAIST"}]},{"given":"Sung-Hyon","family":"Myaeng","sequence":"additional","affiliation":[{"name":"KAIST"}]},{"given":"U","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"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.1145\/2505515.2505545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bin-Hui Chou and Einoshin Suzuki. 2010. Discovering community-oriented roles of nodes in a social network. In DaWaK. 52--64.   Bin-Hui Chou and Einoshin Suzuki. 2010. Discovering community-oriented roles of nodes in a social network. In DaWaK. 52--64.","DOI":"10.1007\/978-3-642-15105-7_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_9_1","unstructured":"Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In OSDI. 137--150.   Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In OSDI. 137--150."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.46"},{"key":"e_1_2_1_12_1","unstructured":"Joseph E. Gonzalez Yucheng Low Haijie Gu Danny Bickson and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30.   Joseph E. Gonzalez Yucheng Low Haijie Gu Danny Bickson and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.229"},{"key":"e_1_2_1_14_1","volume-title":"Grochow and Manolis Kellis","author":"Joshua","year":"2007","unstructured":"Joshua A. Grochow and Manolis Kellis . 2007 . Network motif discovery using subgraph enumeration and symmetry-breaking. In RECOMB. 92--106. Joshua A. Grochow and Manolis Kellis. 2007. Network motif discovery using subgraph enumeration and symmetry-breaking. In RECOMB. 92--106."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"ByungSoo Jeon Inah Jeon Lee Sael and U. Kang. 2016. SCouT: Scalable coupled matrix-tensor factorization -- algorithm and discoveries. In ICDE.  ByungSoo Jeon Inah Jeon Lee Sael and U. Kang. 2016. SCouT: Scalable coupled matrix-tensor factorization -- algorithm and discoveries. In ICDE.","DOI":"10.1109\/ICDE.2016.7498292"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0427-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124374"},{"key":"e_1_2_1_20_1","volume-title":"Net-ray: Visualizing and mining billion-scale graphs. In PAKDD.","author":"Kang U.","year":"2014","unstructured":"U. Kang , Jay-Yoon Lee , Danai Koutra , and Christos Faloutsos . 2014 . Net-ray: Visualizing and mining billion-scale graphs. In PAKDD. U. Kang, Jay-Yoon Lee, Danai Koutra, and Christos Faloutsos. 2014. Net-ray: Visualizing and mining billion-scale graphs. In PAKDD."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.244"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339583"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0283-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225632.3225755"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588563"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_2_1_32_1","volume-title":"ICDM","author":"Park Ha-Myung","year":"2016","unstructured":"Ha-Myung Park , Namyong Park , Sung-Hyon Myaeng , and U. Kang . 2016. Partition aware connected component computation in distributed systems . In ICDM 2016 , December 12-15, Barcelona, Spain. 420--429. Ha-Myung Park, Namyong Park, Sung-Hyon Myaeng, and U. Kang. 2016. Partition aware connected component computation in distributed systems. In ICDM 2016, December 12-15, Barcelona, Spain. 420--429."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Ha-Myung Park Chiwan Park and U. Kang. 2018. PegasusN: A scalable and versatile graph mining system. In AAAI.  Ha-Myung Park Chiwan Park and U. Kang. 2018. PegasusN: A scalable and versatile graph mining system. In AAAI.","DOI":"10.1609\/aaai.v32i1.11372"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662017"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983332"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bdr.2015.01.004"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2610420"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556609"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3237191","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3237191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:34Z","timestamp":1750210774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3237191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3237191"],"URL":"https:\/\/doi.org\/10.1145\/3237191","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}