{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T11:35:50Z","timestamp":1780659350580,"version":"3.54.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62020106013 and 61572113"],"award-info":[{"award-number":["62020106013 and 61572113"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Sichuan Science and Technology Program","award":["2020JDTD0007 and 2020YFG0298"],"award-info":[{"award-number":["2020JDTD0007 and 2020YFG0298"]}]},{"name":"The Science and Technology Achievements Transformation Demonstration Project of Sichuan Province of China","award":["2018CC0094"],"award-info":[{"award-number":["2018CC0094"]}]},{"name":"The Fundamental Research Funds for the Central Universities","award":["ZYGX2019J075 and 2082604401036"],"award-info":[{"award-number":["ZYGX2019J075 and 2082604401036"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, the problem of counting global and local triangles in a graph stream has been widely studied, and numerous triangle counting steaming algorithms have emerged. To improve the throughput and scalability of streaming algorithms, many researches of distributed streaming algorithms on multiple machines are studied. In this article, we first propose a framework of distributed streaming algorithm based on the Master-Worker-Aggregator architecture. The two core parts of this framework are an edge distribution strategy, which plays a key role to affect the performance, including the communication overhead and workload balance, and aggregation method, which is critical to obtain the unbiased estimations of the global and local triangle counts in a graph stream. Then, we extend the state-of-the-art centralized algorithm TRI\u00c8ST into four distributed algorithms under our framework. Compared to their competitors, experimental results show that DVHT-i is excellent in accuracy and speed, performing better than the best existing distributed streaming algorithm. DEHT-b is the fastest algorithm and has the least communication overhead. What\u2019s more, it almost achieves absolute workload balance.<\/jats:p>","DOI":"10.1145\/3494562","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T20:51:00Z","timestamp":1641675060000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0094-6245","authenticated-orcid":false,"given":"Xu","family":"Yang","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Xi\u2019an Jiaotong University and School of Computer Science and Engineering, University of Electronic Science and Technology of China, Xi\u2019an, Shaanxi, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4830-1860","authenticated-orcid":false,"given":"Chao","family":"Song","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3124-6834","authenticated-orcid":false,"given":"Mengdi","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8602-3996","authenticated-orcid":false,"given":"Jiqing","family":"Gu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1114-1728","authenticated-orcid":false,"given":"Ming","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137651"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.051"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366424.3385773"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958158"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00630-6"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433480"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3022186"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00016"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.06.050"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1003243"},{"issue":"1","key":"e_1_3_3_24_2","first-page":"28:1\u201328:12","article-title":"Spark\u2019s graphx-based link prediction for social communication using triangle counting","volume":"9","author":"Ramesh Dharavath","year":"2019","unstructured":"Dharavath Ramesh and Navaljeet Singh Arora. 2019. Spark\u2019s graphx-based link prediction for social communication using triangle counting. Social Network Analysis and Mining 9, 1 (2019), 28:1\u201328:12.","journal-title":"Social Network Analysis and Mining"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-09123-y"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1177\/0038038588022001007"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_51"},{"key":"e_1_3_3_28_2","unstructured":"Kijung Shin Euiwoong Lee Jinoh Oh Mohammad Hammoud and Christos Faloutsos. 2018. DiSLR: Distributed sampling with limited redundancy for triangle counting in graph streams. arXiv:1802.04249. Retrieved from https:\/\/arxiv.org\/abs\/1802.04249."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3441487"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375392"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-75075-6_9"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453165"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00073"},{"issue":"2","key":"e_1_3_3_39_2","first-page":"1","article-title":"Visualizing the signatures of social roles in online discussion groups","volume":"8","author":"Welser Howard T.","year":"2007","unstructured":"Howard T. Welser, Eric Gleave, Danyel Fisher, and Marc A. Smith. 2007. Visualizing the signatures of social roles in online discussion groups. Journal of Social Structure 8, 2 (2007), 1\u201332.","journal-title":"Journal of Social Structure"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556663"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556609"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS47876.2019.00049"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494562","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3494562"],"URL":"https:\/\/doi.org\/10.1145\/3494562","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}