{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T18:57:10Z","timestamp":1767639430961,"version":"3.48.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T00:00:00Z","timestamp":1767571200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T00:00:00Z","timestamp":1767571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2026,12]]},"DOI":"10.1007\/s10619-025-07456-w","type":"journal-article","created":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T15:12:59Z","timestamp":1767625979000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming triangle counting: the impact of a degree oracle"],"prefix":"10.1007","volume":"44","author":[{"given":"Hossein","family":"Jowhari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arash","family":"Rahmati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,5]]},"reference":[{"issue":"2","key":"7456_CR1","first-page":"1226","volume":"8","author":"M Al Hasan","year":"2018","unstructured":"Al Hasan, M., Dave, V.S.: Triangle counting in large networks: a review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 8(2), 1226 (2018)","journal-title":"Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery"},{"key":"7456_CR2","doi-asserted-by":"publisher","unstructured":"Assadi, S., Kapralov, M., Khanna, S.: A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In: Blum, A. (ed.) 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA. LIPIcs, vol. 124, pp. 6\u20131620. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2019.6","DOI":"10.4230\/LIPICS.ITCS.2019.6"},{"issue":"3","key":"7456_CR3","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/BF02523189","journal-title":"Algorithmica"},{"key":"7456_CR4","unstructured":"Bera, S.K., Chakrabarti, A.: Towards tighter space bounds for counting triangles and other substructures in graph streams. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (2017). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik"},{"key":"7456_CR5","unstructured":"Bera, S.K.: Subgraph counting and vertex coloring in large graphs. PhD thesis, Dartmouth College, Hanover, New Hampshire (2019)"},{"issue":"1","key":"7456_CR6","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/S00453-015-0036-4","volume":"76","author":"L Bulteau","year":"2016","unstructured":"Bulteau, L., Froese, V., Kutzkov, K., Pagh, R.: Triangle counting in dynamic graph streams. Algorithmica 76(1), 259\u2013278 (2016). https:\/\/doi.org\/10.1007\/S00453-015-0036-4","journal-title":"Algorithmica"},{"key":"7456_CR7","doi-asserted-by":"publisher","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Vansummeren, S. (ed.) Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pp. 253\u2013262. ACM (2006). https:\/\/doi.org\/10.1145\/1142351.1142388","DOI":"10.1145\/1142351.1142388"},{"key":"7456_CR8","doi-asserted-by":"publisher","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential separation of quantum and classical one-way communication complexity. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 128\u2013137. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007379","DOI":"10.1145\/1007352.1007379"},{"key":"7456_CR9","doi-asserted-by":"publisher","unstructured":"Braverman, V., Ostrovsky, R., Vilenchik, D.: How hard is counting triangles in the streaming model? In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science, vol. 7965, pp. 244\u2013254. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_21","DOI":"10.1007\/978-3-642-39206-1_21"},{"key":"7456_CR10","doi-asserted-by":"publisher","unstructured":"Bera, S.K., Seshadhri, C.: How the degeneracy helps for triangle counting in graph streams. In: Suciu, D., Tao, Y., Wei, Z. (eds.) Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pp. 457\u2013467. ACM (2020). https:\/\/doi.org\/10.1145\/3375395.3387665","DOI":"10.1145\/3375395.3387665"},{"key":"7456_CR11","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA, vol. 2, pp. 623\u2013632 (2002)"},{"key":"7456_CR12","unstructured":"Chen, J.Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D.P., Zhang, M.: Triangle and four cycle counting with predictions in graph streams. In: The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net (2022). https:\/\/openreview.net\/forum?id=8in_5gN9I0"},{"key":"7456_CR13","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/J.TCS.2016.06.020","volume":"683","author":"G Cormode","year":"2017","unstructured":"Cormode, G., Jowhari, H.: A second look at counting triangles in graph streams (corrected). Theor. Comput. Sci. 683, 22\u201330 (2017). https:\/\/doi.org\/10.1016\/J.TCS.2016.06.020","journal-title":"Theor. Comput. Sci."},{"key":"7456_CR14","doi-asserted-by":"publisher","unstructured":"Eden, T., Levi, A., Ron, D., Seshadhri, C.: Approximately counting triangles in sublinear time. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 614\u2013633. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.44","DOI":"10.1109\/FOCS.2015.44"},{"issue":"5","key":"7456_CR15","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1137\/15M1054389","volume":"46","author":"T Eden","year":"2017","unstructured":"Eden, T., Levi, A., Ron, D., Seshadhri, C.: Approximately counting triangles in sublinear time. SIAM J. Comput. 46(5), 1603\u20131646 (2017). https:\/\/doi.org\/10.1137\/15M1054389","journal-title":"SIAM J. Comput."},{"key":"7456_CR16","doi-asserted-by":"crossref","unstructured":"Fichtenberger, H., Peng, P.: Approximately counting subgraphs in data streams. In: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 413\u2013425 (2022)","DOI":"10.1145\/3517804.3524145"},{"key":"7456_CR17","doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., De\u00a0Wolf, R.: Exponential separations for one-way quantum communication complexity, with applications to cryptography. In: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pp. 516\u2013525 (2007)","DOI":"10.1145\/1250790.1250866"},{"issue":"5","key":"7456_CR18","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1137\/070706550","volume":"38","author":"D Gavinsky","year":"2008","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., Wolf, R.: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput. 38(5), 1695\u20131708 (2008). https:\/\/doi.org\/10.1137\/070706550","journal-title":"SIAM J. Comput."},{"key":"7456_CR19","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\u201319, 2005 Proceedings 11, pp. 710\u2013716 (2005). Springer","DOI":"10.1007\/11533719_72"},{"key":"7456_CR20","unstructured":"Jayaram, R., Kallaugher, J.: An optimal algorithm for triangle counting in the stream. arXiv preprint arXiv:2105.01785 (2021)"},{"key":"7456_CR21","unstructured":"Jowhari, H., Rahmati, A.: On the space complexity of counting triangles using oracles. In: Proceedings of the First International Conference on Machine Learning and Knowledge Discovery (MLKD 2024), pp. 253\u2013262 (2024). https:\/\/mlkd.aut.ac.ir\/proceedings\/2024\/paper\/3A.6.pdf"},{"key":"7456_CR22","doi-asserted-by":"publisher","unstructured":"Jowhari, H., Rahmati, A.: Space-efficient algorithms for counting triangles in data streams using trained oracles. Computational Methods for Differential Equations, (2025) https:\/\/doi.org\/10.22034\/cmde.2025.65909.3060","DOI":"10.22034\/cmde.2025.65909.3060"},{"key":"7456_CR23","doi-asserted-by":"publisher","unstructured":"Kallaugher, J., McGregor, A., Price, E., Vorotnikova, S.: The complexity of counting cycles in the adjacency list streaming model. In: Suciu, D., Skritek, S., Koch, C. (eds.) Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pp. 119\u2013133. ACM (2019). https:\/\/doi.org\/10.1145\/3294052.3319706","DOI":"10.1145\/3294052.3319706"},{"key":"7456_CR24","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: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II 39, pp. 598\u2013609 (2012). Springer","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"7456_CR25","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"7456_CR26","doi-asserted-by":"publisher","unstructured":"Kallaugher, J., Price, E.: A hybrid sampling scheme for triangle counting. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 1778\u20131797. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.116","DOI":"10.1137\/1.9781611974782.116"},{"key":"7456_CR27","doi-asserted-by":"crossref","unstructured":"Kallaugher, J., Price, E.: A hybrid sampling scheme for triangle counting. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1778\u20131797 (2017). SIAM","DOI":"10.1137\/1.9781611974782.116"},{"key":"7456_CR28","doi-asserted-by":"crossref","unstructured":"Kavassery\u2013Parakkat, N., Hanjani, K.M., Pavan, A.: Improved triangle counting in graph streams: power of multi-sampling. In: 2018 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 33\u201340 (2018). IEEE","DOI":"10.1109\/ASONAM.2018.8508789"},{"key":"7456_CR29","doi-asserted-by":"crossref","unstructured":"McGregor, A., Vorotnikova, S.: Triangle and four cycle counting in the data stream model. In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 445\u2013456 (2020)","DOI":"10.1145\/3375395.3387652"},{"issue":"7","key":"7456_CR30","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3528087","volume":"65","author":"M Mitzenmacher","year":"2022","unstructured":"Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. Commun. ACM 65(7), 33\u201335 (2022). https:\/\/doi.org\/10.1145\/3528087","journal-title":"Commun. ACM"},{"key":"7456_CR31","doi-asserted-by":"crossref","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 401\u2013411 (2016)","DOI":"10.1145\/2902251.2902283"},{"key":"7456_CR32","doi-asserted-by":"crossref","unstructured":"Nash-Williams, C.: Decomposition of finite graphs into forests. J. London Math. Soc. 39(12) (1964)","DOI":"10.1112\/jlms\/s1-39.1.12"},{"issue":"7","key":"7456_CR33","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/J.IPL.2011.12.007","volume":"112","author":"R Pagh","year":"2012","unstructured":"Pagh, R., Tsourakakis, C.E.: Colorful triangle counting and a mapreduce implementation. Inf. Process. Lett. 112(7), 277\u2013281 (2012). https:\/\/doi.org\/10.1016\/J.IPL.2011.12.007","journal-title":"Inf. Process. Lett."},{"issue":"14","key":"7456_CR34","doi-asserted-by":"publisher","first-page":"1870","DOI":"10.14778\/2556549.2556569","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. Proceedings of the VLDB Endowment 6(14), 1870\u20131881 (2013)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"7456_CR35","doi-asserted-by":"publisher","unstructured":"Rivin, I.: Counting cycles and finite dimensional L$$^{\\text{ p }}$$ norms. Adv. Appl. Math. 29(4), 647\u2013662 (2002). https:\/\/doi.org\/10.1016\/S0196-8858(02)00037-4","DOI":"10.1016\/S0196-8858(02)00037-4"},{"issue":"4","key":"7456_CR36","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/3059194","volume":"11","author":"LD Stefani","year":"2017","unstructured":"Stefani, L.D., Epasto, A., Riondato, M., Upfal, E.: Tri\u00e8st: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans. Knowl. Discov. Data 11(4), 43\u201314350 (2017). https:\/\/doi.org\/10.1145\/3059194","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"7456_CR37","doi-asserted-by":"crossref","unstructured":"Shin, K.: Wrs: Waiting room sampling for accurate triangle counting in real graph streams. In: 2017 IEEE International Conference on Data Mining (ICDM), pp. 1087\u20131092 (2017). IEEE","DOI":"10.1109\/ICDM.2017.143"},{"key":"7456_CR38","doi-asserted-by":"crossref","unstructured":"Shin, K., Kim, J., Hooi, B., Faloutsos, C.: Think before you discard: Accurate triangle counting in graph streams with deletions. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 141\u2013157 (2018). Springer","DOI":"10.1007\/978-3-030-10928-8_9"},{"issue":"1","key":"7456_CR39","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS) 11(1), 37\u201357 (1985)","journal-title":"ACM Transactions on Mathematical Software (TOMS)"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-025-07456-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10619-025-07456-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-025-07456-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T15:13:03Z","timestamp":1767625983000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10619-025-07456-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,5]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["7456"],"URL":"https:\/\/doi.org\/10.1007\/s10619-025-07456-w","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"value":"0926-8782","type":"print"},{"value":"1573-7578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,5]]},"assertion":[{"value":"15 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Both authors mentioned in the paper have agreed to have their contributions published.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"3"}}