{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T23:35:47Z","timestamp":1791588947355,"version":"4.3.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T00:00:00Z","timestamp":1618963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            <jats:italic>Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage? Specifically, how should edges be processed and sampled across the machines for rapid and accurate estimation?<\/jats:italic>\n          <\/jats:p>\n          <jats:p>The count of triangles (i.e., cliques of size three) has proven useful in numerous applications, including anomaly detection, community detection, and link recommendation. For triangle counting in large and dynamic graphs, recent work has focused largely on streaming algorithms and distributed algorithms but little on their combinations for \u201cthe best of both worlds.\u201d<\/jats:p>\n          <jats:p>\n            In this work, we propose\n            <jats:sc>CoCoS<\/jats:sc>\n            , a fast and accurate distributed streaming algorithm for estimating the counts of global triangles (i.e., all triangles) and local triangles incident to each node. Making one pass over the input stream,\n            <jats:sc>CoCoS<\/jats:sc>\n            carefully processes and stores the edges across multiple machines so that the redundant use of computational and storage resources is minimized. Compared to baselines,\n            <jats:sc>CoCoS<\/jats:sc>\n            is:\n            <jats:italic>(a) accurate:<\/jats:italic>\n            giving up to\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            smaller estimation error;\n            <jats:italic>(b) fast<\/jats:italic>\n            : up to\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            faster, scaling linearly with the size of the input stream; and\n            <jats:italic>(c) theoretically sound<\/jats:italic>\n            : yielding unbiased estimates.\n          <\/jats:p>","DOI":"10.1145\/3441487","type":"journal-article","created":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T15:42:54Z","timestamp":1619019774000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2872-1526","authenticated-orcid":false,"given":"Kijung","family":"Shin","sequence":"first","affiliation":[{"name":"KAIST, Daejeon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinoh","family":"Oh","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Hammoud","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University in Qatar, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,21]]},"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.14778\/3137628.3137651"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 623\u2013632","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef , Ravi Kumar , and D. Sivakumar . 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 623\u2013632 . Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 623\u2013632."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_6_1","volume-title":"Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3","author":"Becchetti Luca","year":"2010","unstructured":"Luca Becchetti , Paolo Boldi , Carlos Castillo , and Aristides Gionis . 2010. Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3 ( 2010 ), 13. Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2010. Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3 (2010), 13."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856327"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/980972.980992"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.116"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588563"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196915"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433480"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Yongsub Lim Minsoo Jung and U. Kang. 2018. Memory-efficient and accurate sampling for counting local triangles in graph streams: From simple to multigraphs. ACM Transactions on Knowledge Discovery from Data 12 1 (2018) 4.  Yongsub Lim Minsoo Jung and U. Kang. 2018. Memory-efficient and accurate sampling for counting local triangles in graph streams: From simple to multigraphs. ACM Transactions on Knowledge Discovery from Data 12 1 (2018) 4.","DOI":"10.1145\/3022186"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1115\u20131124","author":"Park Ha-Myung","unstructured":"Ha-Myung Park , Sung-Hyon Myaeng , and U. Kang . 2016. PTE: Enumerating trillion triangles on distributed systems . In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1115\u20131124 . Ha-Myung Park, Sung-Hyon Myaeng, and U. Kang. 2016. PTE: Enumerating trillion triangles on distributed systems. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1115\u20131124."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Ha-Myung Park Francesco Silvestri Rasmus Pagh Chin-Wan Chung Sung-Hyon Myaeng and U. Kang. 2018. Enumerating trillion subgraphs on distributed systems. ACM Transactions on Knowledge Discovery from Data 12 6 (2018) 71.  Ha-Myung Park Francesco Silvestri Rasmus Pagh Chin-Wan Chung Sung-Hyon Myaeng and U. Kang. 2018. Enumerating trillion subgraphs on distributed systems. ACM Transactions on Knowledge Discovery from Data 12 6 (2018) 71.","DOI":"10.1145\/3237191"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691744"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.143"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1077-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_51"},{"key":"e_1_2_1_34_1","volume-title":"accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data 14, 2","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 14, 2 ( 2020 ), 1\u201339. 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 14, 2 (2020), 1\u201339."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/1412159"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505741"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 2nd ACM Workshop on Online Social Networks. ACM, 37\u201342","author":"Viswanath Bimal","unstructured":"Bimal Viswanath , Alan Mislove , Meeyoung Cha , and Krishna P. Gummadi . 2009. On the evolution of user interaction in Facebook . In Proceedings of the 2nd ACM Workshop on Online Social Networks. ACM, 37\u201342 . Bimal Viswanath, Alan Mislove, Meeyoung Cha, and Krishna P. Gummadi. 2009. On the evolution of user interaction in Facebook. In Proceedings of the 2nd ACM Workshop on Online Social Networks. ACM, 37\u201342."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00073"},{"key":"e_1_2_1_45_1","volume-title":"Social Network Analysis: Methods and Applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust . 1994. Social Network Analysis: Methods and Applications . Vol. 8 . Cambridge University Press . Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press."},{"key":"e_1_2_1_46_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H . Strogatz . 1998 . Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 6684 (1998), 440\u2013442. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 6684 (1998), 440\u2013442."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441487","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441487","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:05Z","timestamp":1750197785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,21]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3441487"],"URL":"https:\/\/doi.org\/10.1145\/3441487","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,21]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}