{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:17:59Z","timestamp":1780766279056,"version":"3.54.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Leading-edge Technology Program of Jiangsu NSF","award":["BK20202001"],"award-info":[{"award-number":["BK20202001"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62272215"],"award-info":[{"award-number":["62272215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2020YFB1005900"],"award-info":[{"award-number":["2020YFB1005900"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I\/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of the kind cannot guarantee I\/O optimality. Observing that in order to count butterflies, it suffices to \"witness\" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound \u00d8mega(|E|2\/MB) of a witnessing algorithm, and give a new bound of \u00d8mega(min(|E|2\/MB, |E|\/|V| \u221aM B)). We further develop the IOBufs algorithm that manages to approach the I\/O lower bound, and thus claim its optimality. Finally, we make efforts to parallelize IOBufs to further improve the performance and scalability. We show in the experiment that IOBufs significantly outperforms the state-of-the-art algorithms EMRC and BFC-EM. In addition, IOBufs can scale to conducting butterfly counting on the Clueweb graph with 37 billion edges and quintillions (10^18 ) of butterflies.<\/jats:p>","DOI":"10.1145\/3588714","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-27","source":"Crossref","is-referenced-by-count":12,"title":["I\/O-Efficient Butterfly Counting at Scale"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9204-4075","authenticated-orcid":false,"given":"Zhibin","family":"Wang","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4735-3835","authenticated-orcid":false,"given":"Longbin","family":"Lai","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0388-5194","authenticated-orcid":false,"given":"Yixue","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8610-7946","authenticated-orcid":false,"given":"Bing","family":"Shui","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2710-7628","authenticated-orcid":false,"given":"Chen","family":"Tian","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6581-8730","authenticated-orcid":false,"given":"Sheng","family":"Zhong","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_2_2_2_1","volume-title":"Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. arXiv preprint arXiv:1802.03760","author":"Ammar Khaled","year":"2018","unstructured":"Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018. Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. arXiv preprint arXiv:1802.03760 (2018)."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi Andrea Marino Massimo Santini and Sebastiano Vigna. 2014. BUbiNG: Massive Crawling for the Masses. In WWW. 227--228.","DOI":"10.1145\/2567948.2577304"},{"key":"e_1_2_2_6_1","volume-title":"Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks","author":"Boldi Paolo","unstructured":"Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. In WWW. ACM Press, 587--596."},{"key":"e_1_2_2_7_1","volume-title":"The WebGraph Framework I: Compression Techniques","author":"Boldi Paolo","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In WWW. ACM Press, 595--601."},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 5th ACM\/IEEE-CS Joint Conference on Digital Libraries (JCDL'05)","author":"Chen Hsinchun","year":"2005","unstructured":"Hsinchun Chen, Xin Li, and Zan Huang. 2005. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM\/IEEE-CS Joint Conference on Digital Libraries (JCDL'05). IEEE, 141--142."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453947"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502550"},{"key":"e_1_2_2_13_1","unstructured":"DIMACS. [n.d.]. DIMACS Challenge. http:\/\/dimacs.rutgers.edu\/Challenges\/."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317802"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916438"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653736"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_2_2_22_1","volume-title":"Tricore: Parallel Triangle Counting on GPUs","author":"Hu Yang","year":"2018","unstructured":"Yang Hu, Hang Liu, and H Howie Huang. 2018. Tricore: Parallel Triangle Counting on GPUs. In SC. IEEE, 171--182."},{"key":"e_1_2_2_23_1","volume-title":"Triangle Counting and Truss Decomposition using FPGA","author":"Huang Sitao","unstructured":"Sitao Huang, Mohamed El-Hadedy, Cong Hao, Qin Li, Vikram S Mailthody, Ketan Date, Jinjun Xiong, Deming Chen, Rakesh Nagi, and Wen-mei Hwu. 2018. Triangle Counting and Truss Decomposition using FPGA. In HPEC. IEEE, 1--7."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Haewoon Kwak Changhyun Lee Hosung Park and Sue Moon. 2010. What is Twitter a Social Network or a News Media?. In WWW. 591--600.","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_2_29_1","article-title":"Kronecker graphs: an approach to modeling networks","volume":"11","author":"Leskovec Jure","year":"2010","unstructured":"Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, Vol. 11, 2 (2010).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2021.3138103"},{"key":"e_1_2_2_31_1","volume-title":"Cycles and clustering in bipartite networks. Physical review E","author":"Lind Pedro G","year":"2005","unstructured":"Pedro G Lind, Marta C Gonzalez, and Hans J Herrmann. 2005. Cycles and clustering in bipartite networks. Physical review E, Vol. 72, 5 (2005), 056127."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439463"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_2_34_1","volume-title":"NeuGraph: Parallel Deep Neural Network Computation on Large Graphs. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Ma Lingxiao","year":"2019","unstructured":"Lingxiao Ma, Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. 2019. NeuGraph: Parallel Deep Neural Network Computation on Large Graphs. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, 443--458. https:\/\/www.usenix.org\/conference\/atc19\/presentation\/ma"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.94"},{"key":"e_1_2_2_36_1","volume-title":"Yves Van De Peer, Didier Colle, and Mario Pickavet.","author":"Melckenbeeck Ine","year":"2019","unstructured":"Ine Melckenbeeck, Pieter Audenaert, Thomas Van Parys, Yves Van De Peer, Didier Colle, and Mario Pickavet. 2019. Optimising orbit counting of arbitrary order by equation selection. BMC bioinformatics, Vol. 20, 1 (2019), 1--13."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173180"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3064892"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_2_43_1","volume-title":"18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Qian Zhengping","year":"2021","unstructured":"Zhengping Qian, Chenqiang Min, Longbin Lai, Yong Fang, Gaofeng Li, Youyang Yao, Bingqing Lyu, Xiaoli Zhou, Zhimin Chen, and Jingren Zhou. 2021. GAIA: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). USENIX Association, 321--335. https:\/\/www.usenix.org\/conference\/nsdi21\/presentation\/qian-zhengping"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CMOT.0000032580.12184.c0"},{"key":"e_1_2_2_45_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https:\/\/networkrepository.com"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.2"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1155\/2009"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_2_51_1","volume-title":"Building An Elastic Query Engine on Disaggregated Storage. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Vuppalapati Midhul","year":"2020","unstructured":"Midhul Vuppalapati, Justin Miron, Rachit Agarwal, Dan Truong, Ashish Motivala, and Thierry Cruanes. 2020. Building An Elastic Query Engine on Disaggregated Storage. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). USENIX Association, Santa Clara, CA, 449--462. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/vuppalapati"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481963"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_2_55_1","volume-title":"Accelerated butterfly counting with vertex priority on bipartite graphs. The VLDB Journal","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2022a. Accelerated butterfly counting with vertex priority on bipartite graphs. The VLDB Journal (2022), 1--25."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00658-5"},{"key":"e_1_2_2_57_1","volume-title":"Discovering significant communities on bipartite graphs: An index-based approach","author":"Wang Kai","year":"2021","unstructured":"Kai Wang, Wenjie Zhang, Ying Zhang, Lu Qin, and Yuting Zhang. 2021b. Discovering significant communities on bipartite graphs: An index-based approach. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3016078.2851145"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_2_60_1","unstructured":"Abdurrahman Yacs ar Sivasankaran Rajamanickam Jonathan Berry Michael Wolf Jeffrey S Young and \u00dcmit V cC ataly\u00dcrek. 2019. Linear Algebra-Based Triangle Counting via Fine-Grained Tasking on Heterogeneous Environments: (Update on Static Graph Challenge). In HPEC. 1--4."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407840"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174245"},{"key":"e_1_2_2_63_1","volume-title":"Advances in Digital Forensics XI","author":"Zhao Chen","unstructured":"Chen Zhao and Yong Guan. 2015. A GRAPH-BASED INVESTIGATION OF BITCOIN TRANSACTIONS. In Advances in Digital Forensics XI, Gilbert Peterson and Sujeet Shenoi (Eds.). Springer International Publishing, Cham, 79--95."},{"key":"e_1_2_2_64_1","volume-title":"Efficient Computation of Cohesive Subgraphs in Uncertain Bipartite Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2333--2345","author":"Zhao Gengda","year":"2022","unstructured":"Gengda Zhao, Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Yizhang He. 2022. Efficient Computation of Cohesive Subgraphs in Uncertain Bipartite Graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2333--2345."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489502"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400903.3400916"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00100"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:35Z","timestamp":1750178855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588714"],"URL":"https:\/\/doi.org\/10.1145\/3588714","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}