{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:18:42Z","timestamp":1773825522084,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>This paper presents a new space-efficient algorithm for counting and sampling triangles--and more generally, constant-sized cliques--in a massive graph whose edges arrive as a stream. Compared to prior work, our algorithm yields significant improvements in the space and time complexity for these fundamental problems. Our algorithm is simple to implement and has very good practical performance on large graphs.<\/jats:p>","DOI":"10.14778\/2556549.2556569","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1870-1881","source":"Crossref","is-referenced-by-count":134,"title":["Counting and sampling triangles from a graph stream"],"prefix":"10.14778","volume":"6","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, Iowa State University"}]},{"given":"Kanat","family":"Tangwongsan","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights"}]},{"given":"Srikanta","family":"Tirthapura","sequence":"additional","affiliation":[{"name":"Dept. of Electrical and Computer Engineering, Iowa State University"}]},{"given":"Kun-Lung","family":"Wu","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545465"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778638"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_2_1_8_1","volume-title":"From the birthday paradox to a practical sublinear space streaming algorithm for triangle counting. CoRR, abs\/1212.2264","author":"Jha M.","year":"2012","unstructured":"M. Jha, C. Seshadhri, and A. Pinar. From the birthday paradox to a practical sublinear space streaming algorithm for triangle counting. CoRR, abs\/1212.2264, 2012."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958158"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/264772"},{"key":"e_1_2_1_12_1","unstructured":"J. Leskovec. Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data\/index.html. Accessed Dec 5 2012."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040646"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.012582999"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00108"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_20_1","volume-title":"CIKM","author":"Tangwongsan K.","year":"2013","unstructured":"K. Tangwongsan, A. Pavan, and S. Tirthapura. Parallel triangle counting in massive streaming graphs. In CIKM, 2013."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:35:01Z","timestamp":1729722901000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":24,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556569"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556569","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}