{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:27:57Z","timestamp":1779334077307,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:00:00Z","timestamp":1437609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s00453-015-0036-4","type":"journal-article","created":{"date-parts":[[2015,7,22]],"date-time":"2015-07-22T13:55:10Z","timestamp":1437573310000},"page":"259-278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Triangle Counting in Dynamic Graph Streams"],"prefix":"10.1007","volume":"76","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantin","family":"Kutzkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph Sketches: Sparsification, Spanners, and Subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"36_CR2","unstructured":"Aiello, W., Chung, F.R.K., Lu, L.: A Random Gmodel for Massive Graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21\u201323, 2000, Portland, OR, USA (STOC), 171\u2013180 (2000)"},{"key":"36_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barabasi, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47\u201397 (2002)","journal-title":"Rev. Mod. Phys."},{"issue":"3","key":"36_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"36_CR5","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23\u201326, 2010, Las Vegas, Nevada, USA, 787\u2013796 (2010)"},{"issue":"1","key":"36_CR6","first-page":"13","volume":"13","author":"L Becchetti","year":"2010","unstructured":"Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient algorithms for large-scale local triangle counting. ACM Trans. Knowl. Discov. Data 13(1), 13\u201328 (2010)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Boldi, P., Rosa, M., Ugander, J., Vigna, S.: Four degrees of separation. Web Sci. 2012, WebScience \u201912, Evanston, IL, USA, June 22\u201324, 33\u201342 (2012)","DOI":"10.1145\/2380718.2380723"},{"issue":"5","key":"36_CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1103\/PhysRevE.83.056119","volume":"83","author":"JW Berry","year":"2011","unstructured":"Berry, J.W., Hendrickson, B., LaViolette, R.A., Phillips, C.A.: Tolerating the community detection resolution limit with edge weighting. Phys. Rev. E 83(5), 56\u2013119 (2011)","journal-title":"Phys. Rev. E"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26\u201328, Chicago, Illinois, USA, 253\u2013262 (2006)","DOI":"10.1145\/1142351.1142388"},{"issue":"2","key":"36_CR10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"LJ Carter","year":"1979","unstructured":"Carter, L.J., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. In: Symposium on Computational Geometry 142\u2013149 (2005)","DOI":"10.1145\/1064092.1064116"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Ghodsi, M.: New Streaming Algorithms for Counting Triangles in Graphs. In: Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16\u201329, 710\u2013716 (2005)","DOI":"10.1007\/11533719_72"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Jha, M., Seshadhri, C., Pinar, A.: A space efficient streaming algorithm for triangle counting using the birthday paradox. In: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11\u201314, 589\u2013597 (2013)","DOI":"10.1145\/2487575.2487678"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12\u201316, Athens, Greece, 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Mehlhorn, K., Sauerwald, T., Sun, H.: Counting Arbitrary Subgraphs in Data Streams. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP: Warwick, UK, July 9\u201313, Proceedings. Part II 598\u2013609 (2012)","DOI":"10.1007\/978-3-642-31585-5_53"},{"issue":"1\u20132","key":"36_CR16","first-page":"161","volume":"8","author":"MN Kolountzakis","year":"2012","unstructured":"Kolountzakis, M.N., Miller, G.L., Peng, R., Richard, T., Charalampos, E.: Efficient triangle counting in large graphs via degree-based vertex partitioning. Int. Math. 8(1\u20132), 161\u2013185 (2012)","journal-title":"Int. Math."},{"issue":"1","key":"36_CR17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Comput. Complex. 8(1), 21\u201349 (1999)","journal-title":"Comput. Complex."},{"key":"36_CR18","unstructured":"Leonardi, S.: List of Open Problems in Sublinear Algorithms: Problem 11. http:\/\/sublinear.info\/11"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Manjunath, M., Mehlhorn, K., Panagiotou, K., Sun, H.: Approximate Counting of Cycles in Streams. In: Algorithms\u2014ESA 2011\u201419th Annual European Symposium, Saarbr\u00fccken, Germany, September 5\u20139, 677\u2013688 (2011)","DOI":"10.1007\/978-3-642-23719-5_57"},{"issue":"2","key":"36_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2), 1 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"36_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput. 38(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"36_CR22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.ipl.2011.12.007","volume":"112","author":"R Pagh","year":"2012","unstructured":"Pagh, R., Rasmus, T., Charalmpos, E.: Colorful triangle counting and a MapReduce implementation. Inf. Process. Lett. 112(7), 277\u2013281 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"14","key":"36_CR23","first-page":"1870","volume":"6","author":"A Pavan","year":"2013","unstructured":"Pavan, A., Tangwongsan, K., Tirthapura, S., Wu, K.L.: Counting and sampling triangles from a graph stream. PVLDB 6(14), 1870\u20131881 (2013)","journal-title":"PVLDB"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"Seshadhri, C., Pinar, A., Kolda, T.: Triadic Measures on Graphs: The Power of Wedge Sampling. In: Proceedings of the 13th SIAM International Conference on Data Mining, May 2\u20134. Austin, Texas, USA, 10\u201318 (2013)","DOI":"10.1137\/1.9781611972832.2"},{"issue":"3","key":"36_CR25","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/2220357.2220361","volume":"59","author":"M P\u01cetra\u015fcu","year":"2012","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: The power of simple tabulation hashing. J. ACM 59(3), 14 (2012)","journal-title":"J. ACM"},{"issue":"2","key":"36_CR26","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/100800774","volume":"41","author":"M Thorup","year":"2012","unstructured":"Thorup, M., Zhang, Y.: Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. SIAM J. Comput. 41(2), 293\u2013331 (2012)","journal-title":"SIAM J. Comput."},{"key":"36_CR27","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Kang, U., Miller, G.L., Faloutsos, C.: DOULION: Counting Triangles in Massive Graphs with a Coin. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28\u2013July 1, 837\u2013846 (2009)","DOI":"10.1145\/1557019.1557111"},{"issue":"6","key":"36_CR28","doi-asserted-by":"crossref","first-page":"703","DOI":"10.7155\/jgaa.00245","volume":"15","author":"CE Tsourakakis","year":"2011","unstructured":"Tsourakakis, C.E., Kolountzakis, M.N., Gary, G.L.: Triangle sparsifiers. J. Graph Algorithms Appl. 15(6), 703\u2013726 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"36_CR29","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying Matrices Faster than Coppersmith-Winograd. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19\u201322, 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0036-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0036-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0036-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T15:54:32Z","timestamp":1567007672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0036-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,23]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["36"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0036-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,23]]}}}