{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T18:43:18Z","timestamp":1790275398338,"version":"4.1.0"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Triangle counting in hypergraph streams-including both hyper-vertex and hyper-edge triangles-is a fundamental problem in hypergraph analytics, with broad applications. However, existing methods face two key limitations: (i) an incomplete classification of hyper-vertex triangle structures, typically considering only inner or outer triangles; and (ii) inflexible sampling schemes that predefine the number of sampled hyperedges, which is impractical under strict memory constraints due to highly variable hyperedge sizes. To address these challenges, we first introduce a complete classification of hyper-vertex triangles, including inner, hybrid, and outer triangles. Based on this, we develop HTCount, a reservoir-based algorithm that dynamically adjusts the sample size based on the available memory M. To further improve memory utilization and reduce estimation error, we develop HTCount-P, a partition-based variant that adaptively partitions unused memory into independent sample subsets. We provide theoretical analysis of the unbiasedness and variance bounds of the proposed algorithms. Case studies demonstrate the expressiveness of our triangle structures in revealing meaningful interaction patterns. Extensive experiments on real-world hypergraphs show that both our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors that are 1 to 2 orders of magnitude lower than those of existing methods and consistently high throughput.<\/jats:p>","DOI":"10.1145\/3769837","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-28","source":"Crossref","is-referenced-by-count":4,"title":["Triangle Counting in Hypergraph Streams: A Complete and Practical Approach"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7961-9131","authenticated-orcid":false,"given":"Lingkai","family":"Meng","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3351-9119","authenticated-orcid":false,"given":"Long","family":"Yuan","sequence":"additional","affiliation":[{"name":"Wuhan University of Technology, Wuhan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.29"},{"key":"e_1_2_1_3_1","volume-title":"Advances in Neural Information Processing Systems","volume":"28","author":"Alistarh Dan","year":"2015","unstructured":"Dan Alistarh, Jennifer Iglesias, and Milan Vojnovic. 2015. Streaming min-max hypergraph partitioning. Advances in Neural Information Processing Systems, Vol. 28 (2015)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380152"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2735405"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00031"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00032"},{"key":"e_1_2_1_10_1","first-page":"263","article-title":"Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks. Data Sci","volume":"8","author":"Chen Zi","year":"2023","unstructured":"Zi Chen, Bo Feng, Long Yuan, Xuemin Lin, and Liping Wang. 2023. Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks. Data Sci. Eng., Vol. 8, 3 (2023), 263-278.","journal-title":"Eng."},{"key":"e_1_2_1_11_1","volume-title":"Science Advances","volume":"7","author":"Chodrow Philip S","year":"2021","unstructured":"Philip S Chodrow, Nate Veldt, and Austin R Benson. 2021. Generative hypergraph clustering: From blockmodels to modularity. Science Advances, Vol. 7, 28 (2021), eabh1303."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1086\/681213"},{"key":"e_1_2_1_13_1","volume-title":"Approximately Counting Triangles in Sublinear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. 614-633","author":"Eden Talya","unstructured":"Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. 2015. Approximately Counting Triangles in Sublinear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. 614-633."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Song Feng Emily Heath Brett Jefferson Cliff Joslyn Henry Kvinge Hugh D Mitchell Brenda Praggastis Amie J Eisfeld Amy C Sims Larissa B Thackray et al. 2021. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinformatics Vol. 22 1 (2021) 287.","DOI":"10.1186\/s12859-021-04197-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3312319"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0460-y"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3539597.3570403"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30675-4_16"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"TriCore: parallel triangle counting on GPUs","volume":"14","author":"Hu Yang","year":"2018","unstructured":"Yang Hu, Hang Liu, and H. Howie Huang. 2018. TriCore: parallel triangle counting on GPUs. In Proceedings of SC. IEEE \/ ACM, 14:1-14:12.","journal-title":"Proceedings of SC. IEEE \/ ACM"},{"key":"e_1_2_1_21_1","first-page":"3067","article-title":"textdollarTC-StreamtextdollarTC-Stream: Large-Scale Graph Triangle Counting on a Single Machine Using GPUs","volume":"33","author":"Huang Jianqiang","year":"2022","unstructured":"Jianqiang Huang, Haojie Wang, Xiang Fei, Xiaoying Wang, and Wenguang Chen. 2022. textdollarTC-StreamtextdollarTC-Stream: Large-Scale Graph Triangle Counting on a Single Machine Using GPUs. IEEE Trans. Parallel Distributed Syst., Vol. 33, 11 (2022), 3067-3078.","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3143612"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_24_1","volume-title":"PostMan: A Productive System for Spatio-temporal Data Management and Analysis. Data Science and Engineering","author":"Jin Jiaqi","year":"2025","unstructured":"Jiaqi Jin, Ziquan Fang, Lu Chen, and Yunjun Gao. 2025. PostMan: A Productive System for Spatio-temporal Data Management and Analysis. Data Science and Engineering (2025), 1-24."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2023.1301994"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00059"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.116"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-022-01739-9"},{"key":"e_1_2_1_29_1","volume-title":"SM Shamimul Hasan, and Ramakrishnan Kannan","author":"Kurte Kuldeep","year":"2021","unstructured":"Kuldeep Kurte, Neena Imam, SM Shamimul Hasan, and Ramakrishnan Kannan. 2021. Phoenix: A scalable streaming hypergraph analysis framework. In Advances in data science and information engineering: proceedings from ICDATA 2020 and IKE 2020. Springer, 3-25."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3719002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407823"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-023-01837-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557505"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487802"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_2_1_38_1","volume-title":"2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 909-921","author":"Liu Qing","year":"2023","unstructured":"Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2023. Distributed (\u03b1, \u03b2)-core decomposition over bipartite graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 909-921."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00086"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42005-022-00858-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa768"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627673.3679765"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-025-00915-x"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3694966"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725345"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00257"},{"key":"e_1_2_1_48_1","volume-title":"Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges. arXiv preprint arXiv:2412.11488","author":"Meng Lingkai","year":"2024","unstructured":"Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, and Wenjie Zhang. 2024b. Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges. arXiv preprint arXiv:2412.11488 (2024)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3064892"},{"key":"e_1_2_1_50_1","first-page":"61","article-title":"Hypergraph Partitioning and Clustering","volume":"20073547","author":"Papa David A","year":"2007","unstructured":"David A Papa and Igor L Markov. 2007. Hypergraph Partitioning and Clustering. Handbook of Approximation Algorithms and Metaheuristics, Vol. 20073547 (2007), 61-1.","journal-title":"Handbook of Approximation Algorithms and Metaheuristics"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00226"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00226"},{"key":"e_1_2_1_53_1","volume-title":"Clustering with hypergraphs: the case for large hyperedges","author":"Purkait Pulak","year":"2016","unstructured":"Pulak Purkait, Tat-Jun Chin, Alireza Sadri, and David Suter. 2016. Clustering with hypergraphs: the case for large hyperedges. IEEE transactions on pattern analysis and machine intelligence, Vol. 39, 9 (2016), 1697-1711."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/bs.adcom.2021.10.003"},{"key":"e_1_2_1_55_1","volume-title":"Semi-streaming algorithms for hypergraph matching. arXiv preprint arXiv:2502.13636","author":"Reinst\u00e4dtler Henrik","year":"2025","unstructured":"Henrik Reinst\u00e4dtler, SM Ferdous, Alex Pothen, Bora U\u00e7ar, and Christian Schulz. 2025. Semi-streaming algorithms for hypergraph matching. arXiv preprint arXiv:2502.13636 (2025)."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3495011"},{"key":"e_1_2_1_58_1","volume-title":"accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Shin Kijung","year":"2020","unstructured":"Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos. 2020. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 14, 2 (2020), 1-39."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742839"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_61_1","volume-title":"Streaming hypergraph partitioning algorithms on limited memory environments. arXiv preprint arXiv:2103.05394","author":"Ta\u015fyaran Fatih","year":"2021","unstructured":"Fatih Ta\u015fyaran, Berkay Demireller, Kamer Kaya, and Bora U\u00e7ar. 2021. Streaming hypergraph partitioning algorithms on limited memory environments. arXiv preprint arXiv:2103.05394 (2021)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Charalampos E Tsourakakis U Kang Gary L Miller and Christos Faloutsos. 2009. Doulion: counting triangles in massive graphs with a coin. 837-846 pages.","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_63_1","first-page":"1875","article-title":"Revisiting Wedge Sampling for Triangle Counting","author":"Turk Ata","year":"2019","unstructured":"Ata Turk and Duru T''''u, rkoglu. 2019. Revisiting Wedge Sampling for Triangle Counting. In Proceedings of WWW. ACM, 1875-1885.","journal-title":"Proceedings of WWW. ACM"},{"key":"e_1_2_1_64_1","volume-title":"Structural folds: Generative disruption in overlapping groups. American journal of sociology","author":"Vedres Balazs","year":"2010","unstructured":"Balazs Vedres and David Stark. 2010. Structural folds: Generative disruption in overlapping groups. American journal of sociology, Vol. 115, 4 (2010), 1150-1190."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149197"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20891-1_21"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.48"},{"key":"e_1_2_1_69_1","first-page":"1","volume-title":"TCIM: Triangle Counting Acceleration With Processing-In-MRAM Architecture. In 57th ACM\/IEEE Design Automation Conference, DAC","author":"Wang Xueyan","year":"2020","unstructured":"Xueyan Wang, Jianlei Yang, Yinglin Zhao, Yingjie Qi, Meichen Liu, Xingzhou Cheng, Xiaotao Jia, Xiaoming Chen, Gang Qu, and Weisheng Zhao. 2020. TCIM: Triangle Counting Acceleration With Processing-In-MRAM Architecture. In 57th ACM\/IEEE Design Automation Conference, DAC 2020. IEEE, 1-6."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556663"},{"key":"e_1_2_1_71_1","first-page":"3245","article-title":"Hypergraph collaborative network on vertices and hyperedges","volume":"45","author":"Wu Hanrui","year":"2022","unstructured":"Hanrui Wu, Yuguang Yan, and Michael Kwok-Po Ng. 2022. Hypergraph collaborative network on vertices and hyperedges. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 45, 3 (2022), 3245-3258.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_72_1","first-page":"824","article-title":"Scan: a structural clustering algorithm for networks","author":"Xu Xiaowei","year":"2007","unstructured":"Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas AJ Schweiger. 2007. Scan: a structural clustering algorithm for networks. In Proceedings of SIGKDD. 824-833.","journal-title":"Proceedings of SIGKDD."},{"key":"e_1_2_1_73_1","volume-title":"DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams. In 2024 43rd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 198-209","author":"Xuan Wei","year":"2024","unstructured":"Wei Xuan, Yan Liang, Huawei Cao, Ning Lin, Xiaochun Ye, and Dongrui Fan. 2024. DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams. In 2024 43rd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 198-209."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2023.110878"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494562"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00160"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3093240"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3712221.3712238"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59416-9_31"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE65448.2025.00028"},{"key":"e_1_2_1_81_1","volume-title":"GPUSCAN: Efficient Structural Graph Clustering on GPUs","author":"Yuan Long","year":"2025","unstructured":"Long Yuan, Zeyu Zhou, Zi Chen, Xuemin Lin, Xiang Zhao, and Fan Zhang. 2025b. GPUSCAN: Efficient Structural Graph Clustering on GPUs. IEEE Transactions on Parallel and Distributed Systems (2025)."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3139111"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3236335"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645438"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709656"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2018.2873759"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769837","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:49:40Z","timestamp":1781326180000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769837"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":86,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769837"],"URL":"https:\/\/doi.org\/10.1145\/3769837","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}