{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:31:22Z","timestamp":1765960282752,"version":"3.41.0"},"reference-count":82,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100030932","name":"ArmaSuisse","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100030932","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Swiss State Secretariat for 1498 Education (SERI) - SmartEDGE","award":["grant 1499 agreement No. 101092908"],"award-info":[{"award-number":["grant 1499 agreement No. 101092908"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Graph Pattern Mining (GPM) is a class of algorithms that identifies given shapes within a graph, e.g., cliques of a certain size. Any area of a graph can contain a shape of interest, but in real-world graphs, these shapes tend to be concentrated in areas deemed skewed. Because mining skewed areas can dominate GPM computations, the overwhelming majority of state-of-the-art GPM techniques break such areas into many small parts and load balance them across servers. This paper takes a diametrically opposite approach: we suggest a framework that concentrates rather than divides the skewed areas.<\/jats:p>\n          <jats:p>Our framework, called GraphINC, relies on two key innovations. First, it introduces a new graph partitioning scheme capable of separating the skewed area from the rest of the graph. Second, it offloads the skewed part onto a new class of hardware accelerator, a programmable network switch. We implemented our framework to leverage a commercial 100 Gbps switch and obtained results 6.5 to 52.4\u00d7 faster thanks to our novel offloading technique.<\/jats:p>","DOI":"10.1145\/3589329","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-28","source":"Crossref","is-referenced-by-count":6,"title":["GraphINC: Graph Pattern Mining at Network Speed"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2572-859X","authenticated-orcid":false,"given":"Rana","family":"Hussein","sequence":"first","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4252-0648","authenticated-orcid":false,"given":"Alberto","family":"Lerner","sequence":"additional","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2204-4691","authenticated-orcid":false,"given":"Andre","family":"Ryser","sequence":"additional","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7214-2568","authenticated-orcid":false,"given":"Lucas David","family":"B\u00fcrgi","sequence":"additional","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1525-0315","authenticated-orcid":false,"given":"Albert","family":"Blarer","sequence":"additional","affiliation":[{"name":"ArmaSuisse, Bern, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-4212","authenticated-orcid":false,"given":"Philippe","family":"Cudre-Mauroux","sequence":"additional","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_2_2_1","unstructured":"Arista. 2020. High Performance Multi-function Programmable Platforms. https:\/\/www.arista.com\/en\/products\/7170-series."},{"key":"e_1_2_2_3_1","unstructured":"Arista. 2022. 400G Solutions. https:\/\/www.arista.com\/en\/products\/400g-solutions."},{"key":"e_1_2_2_4_1","volume-title":"Higher-order organization of complex networks. Science 353, 6295","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480133"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486011"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3439724"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2014.19"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"volume-title":"Efficient and Scalable Graph Pattern Mining on GPUs. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)","author":"Xuhao","key":"e_1_2_2_11_1","unstructured":"Xuhao Chen et al . 2022. Efficient and Scalable Graph Pattern Mining on GPUs. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 857--877."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00052"},{"key":"e_1_2_2_14_1","series-title":"SIAM Journal on computing 14, 1","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210--223."},{"key":"e_1_2_2_15_1","unstructured":"Cisco 2020. Cisco Nexus 34180YC and 3464C Programmable Switches Data Sheet. https:\/\/www.cisco.com\/c\/en\/us\/products\/collateral\/switches\/nexus-3000-series-switches\/datasheet-c78--740836.html."},{"key":"e_1_2_2_16_1","unstructured":"Cisco. 2022. 400G Data Center Networking. https:\/\/www.cisco.com\/c\/en\/us\/solutions\/data-center\/high-capacity-400g-data-center-networking\/index.html."},{"volume-title":"Internetworking con TCP\/IP","author":"Comer Douglas E","key":"e_1_2_2_17_1","unstructured":"Douglas E Comer. 2006. Internetworking con TCP\/IP. Vol. 1. Pearson."},{"key":"e_1_2_2_18_1","unstructured":"Ethernet Technology Consortium. 2020. 800G Specification. https:\/\/ethernettechnologyconsortium.org\/wp-content\/uploads\/2021\/10\/Ethernet-Technology-Consortium_800G-Specification_r1.1.pdf."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2992106"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_2_21_1","volume-title":"Clique percolation in random networks. Physical review letters 94, 16","author":"Der\u00e9nyi Imre","year":"2005","unstructured":"Imre Der\u00e9nyi, Gergely Palla, and Tam\u00e1s Vicsek. 2005. Clique percolation in random networks. Physical review letters 94, 16 (2005), 160202."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-011-9250-x"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_2_27_1","first-page":"829","article-title":"In-network aggregation for shared machine learning clusters","volume":"3","author":"Gebara Nadeen","year":"2021","unstructured":"Nadeen Gebara, Manya Ghobadi, and Paolo Costa. 2021. In-network aggregation for shared machine learning clusters. Proceedings of Machine Learning and Systems 3 (2021), 829--844.","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422604.3425928"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98720"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_2_31_1","unstructured":"Bronwyn H Hall Adam B Jaffe and Manuel Trajtenberg. 2001. The NBER patent citation data file: Lessons insights and methodological tools."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783759"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_15"},{"key":"e_1_2_2_34_1","unstructured":"Infiniband Architecture Specification Annex A16 [n. d.]. Infiniband Architecture Specification--Annex A16: RoCE. https:\/\/www.infinibandta.org\/ibta-specifications-download\/."},{"key":"e_1_2_2_35_1","unstructured":"Infiniband Architecture Specifications [n. d.]. Infiniband Architecture Specification. https:\/\/www.infinibandta.org\/ibta-specifications-download\/."},{"key":"e_1_2_2_36_1","unstructured":"Intel. 2020. Intel Xeon Platinum 8380HL Processor. https:\/\/ark.intel.com\/content\/www\/us\/en\/ark\/products\/205684\/intel-xeon-platinum-8380hl-processor-38--5m-cache-2--90-ghz.html."},{"key":"e_1_2_2_37_1","unstructured":"Intel. 2022. Intel\u00ae Tofino 2: Second-generation P4-programmable Ethernet switch. https:\/\/www.intel.com\/content\/www\/us\/en\/products\/network-io\/programmable-ethernet-switch\/tofino-2-series.html."},{"key":"e_1_2_2_38_1","unstructured":"Inventec. 2018. Invente D10064 Programmable Switch Data Sheet. https:\/\/productline.inventec.com\/Switch\/Download\/D10064.pdf."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517825"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461551"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185467.3185494"},{"key":"e_1_2_2_43_1","volume-title":"15th USENIX Symposium on Networked Systems Design and Implementation ({NSDI} 18)","author":"Jin Xin","year":"2018","unstructured":"Xin Jin, Xiaozhou Li, Haoyu Zhang, Nate Foster, Jeongkeun Lee, Robert Soul\u00e9, Changhoon Kim, and Ion Stoica. 2018. Netchain: Scale-free sub-rtt coordination. In 15th USENIX Symposium on Networked Systems Design and Implementation ({NSDI} 18). 35--49."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132764"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378524"},{"key":"e_1_2_2_46_1","volume-title":"ATP: In-network Aggregation for Multi-tenant Learning. In NSDI. 741--761.","author":"Lao ChonLam","year":"2021","unstructured":"ChonLam Lao, Yanfang Le, Kshiteej Mahajan, Yixi Chen, Wenfei Wu, Aditya Akella, and Michael M Swift. 2021. ATP: In-network Aggregation for Multi-tenant Learning. In NSDI. 741--761."},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the 9th Conference on Innovative Data System Research.","author":"Lerner Alberto","year":"2019","unstructured":"Alberto Lerner, Rana Hussein, and Philippe Cudr\u00e9-Mauroux. 2019. The Case for Network Accelerated Query Processing. In Proceedings of the 9th Conference on Innovative Data System Research."},{"key":"e_1_2_2_48_1","first-page":"60","article-title":"Networking and Storage: The Next Computing Elements in Exascale Systems","volume":"43","author":"Lerner Alberto","year":"2020","unstructured":"Alberto Lerner, Rana Hussein, Andr\u00e9 Ryser, Sangjin Lee, and Philippe Cudr\u00e9-Mauroux. 2020. Networking and Storage: The Next Computing Elements in Exascale Systems? IEEE Data Engineering Bulletin 43, 1 (2020), 60--71.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554874"},{"key":"e_1_2_2_50_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford large network dataset collection."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132751"},{"volume-title":"Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation.","author":"Li Jialin","key":"e_1_2_2_52_1","unstructured":"Jialin Li, Jacob Nelson, Ellis Michael, Xin Jin, and Dan R. K. Ports. 2020. Pegasus: Tolerating Skewed Workloads in Distributed Storage with in-Network Coherence Directories. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation."},{"key":"e_1_2_2_53_1","volume-title":"Graphzero: Breaking symmetry for efficient graph mining. arXiv preprint arXiv:1911.12877","author":"Mawhirter Daniel","year":"2019","unstructured":"Daniel Mawhirter, Sam Reinehr, Connor Holmes, Tongping Liu, and Bo Wu. 2019. Graphzero: Breaking symmetry for efficient graph mining. arXiv preprint arXiv:1911.12877 (2019)."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_2_55_1","volume-title":"Network motifs: simple building blocks of complex networks. Science 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824--827."},{"key":"e_1_2_2_56_1","unstructured":"Netronome. 2017. Programming NFP with P4 and C. https:\/\/www.netronome.com\/media\/redactor_files\/WP_Programming_with_P4_and_C.pdf."},{"key":"e_1_2_2_57_1","unstructured":"Network Programming Language [n. d.]. Network Programming Language. https:\/\/nplang.org\/."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_2_59_1","unstructured":"Ben Pfaff Debnil Sur Leonid Ryzhyk and Mihai Budiu. 2022. P4 in open vswitch with ofp4. In P4 Workshop."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0405-2"},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of the 9th Conference on Innovative Data System Research.","author":"Ryser Andr\u00e9","year":"2022","unstructured":"Andr\u00e9 Ryser, Alberto Lerner, Alex Forencich, and Philippe Cudr\u00e9-Mauroux. 2022. D-RDMA: Bringing Zero-Copy RDMA to Database Systems. In Proceedings of the 9th Conference on Innovative Data System Research."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3152434.3152461"},{"key":"e_1_2_2_63_1","volume-title":"Scaling Distributed Machine Learning with In-Network Aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Sapio Amedeo","year":"2021","unstructured":"Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtarik. 2021. Scaling Distributed Machine Learning with In-Network Aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00104"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387519"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934900"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491185.2491190"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0466-x"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389698"},{"key":"e_1_2_2_73_1","volume-title":"LaKe: The Power of In-Network Computing. In International Conference on ReConFigurable Computing and FPGAs (ReConFig). 1--8.","author":"Tokusashi Yuta","year":"2018","unstructured":"Yuta Tokusashi, Hiroki Matsutani, and Noa Zilberman. 2018. LaKe: The Power of In-Network Computing. In International Conference on ReConFigurable Computing and FPGAs (ReConFig). 1--8."},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_2_75_1","volume-title":"Leapfrog triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481","author":"Veldhuizen Todd L","year":"2012","unstructured":"Todd L Veldhuizen. 2012. Leapfrog triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481 (2012)."},{"key":"e_1_2_2_76_1","volume-title":"RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). 763--782."},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00122"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544216.3544262"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938548"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00077"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368301"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589329","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:14Z","timestamp":1750178774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":82,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589329"],"URL":"https:\/\/doi.org\/10.1145\/3589329","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}