{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T00:11:22Z","timestamp":1781050282958,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Fundamental Research Funds for the Central Universities"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3524145","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"413-425","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximately Counting Subgraphs in Data Streams"],"prefix":"10.1145","author":[{"given":"Hendrik","family":"Fichtenberger","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pan","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_2_2_1","volume-title":"ITCS","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , Michael Kapralov , and Sanjeev Khanna . 2019 . A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In 10th Innovations in Theoretical Computer Science , ITCS 2019. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 6. Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. 2019. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In 10th Innovations in Theoretical Computer Science, ITCS 2019. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 6."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_3_2_2_5_1","volume-title":"34th Symposium on Theoretical Aspects of Computer Science.","author":"Bera Suman K","year":"2017","unstructured":"Suman K Bera and Amit Chakrabarti . 2017 . Towards tighter space bounds for counting triangles and other substructures in graph streams . In 34th Symposium on Theoretical Aspects of Computer Science. Suman K Bera and Amit Chakrabarti. 2017. Towards tighter space bounds for counting triangles and other substructures in graph streams. In 34th Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_3_2_2_6_1","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems (PODS'20)","author":"Bera Suman K.","unstructured":"Suman K. Bera and C. Seshadhri . 2020. How the Degeneracy Helps for Triangle Counting in Graph Streams . In Proceedings of the 39th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems (PODS'20) . Association for Computing Machinery, New York, NY, USA, 457--467. https:\/\/doi.org\/10.1145\/3375395.3387665 10.1145\/3375395.3387665 Suman K. Bera and C. Seshadhri. 2020. How the Degeneracy Helps for Triangle Counting in Graph Streams. In Proceedings of the 39th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems (PODS'20). Association for Computing Machinery, New York, NY, USA, 457--467. https:\/\/doi.org\/10.1145\/3375395.3387665"},{"key":"e_1_3_2_2_7_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Braverman Vladimir","unstructured":"Vladimir Braverman , Rafail Ostrovsky , and Dan Vilenchik . 2013. How hard is counting triangles in the streaming model? . In International Colloquium on Automata, Languages, and Programming . Springer , 244--254. Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. 2013. How hard is counting triangles in the streaming model?. In International Colloquium on Automata, Languages, and Programming. Springer, 244--254."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0036-4"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_3_2_2_10_1","volume-title":"Canonne and Tom Gur","author":"Cl\u00e9ment","year":"2018","unstructured":"Cl\u00e9ment L. Canonne and Tom Gur . 2018 . An Adaptivity Hierarchy Theorem for Property Testing . computational complexity 27, 4 (Dec. 2018), 671--716. https:\/\/doi.org\/10.1007\/s00037-018-0168--4 10.1007\/s00037-018-0168--4 Cl\u00e9ment L. Canonne and Tom Gur. 2018. An Adaptivity Hierarchy Theorem for Property Testing. computational complexity 27, 4 (Dec. 2018), 671--716. https:\/\/doi.org\/10.1007\/s00037-018-0168--4"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.025"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.020"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.89"},{"key":"e_1_3_2_2_15_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Fichtenberger Hendrik","year":"2020","unstructured":"Hendrik Fichtenberger , Mingze Gao , and Pan Peng . 2020 . Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Hendrik Fichtenberger, Mingze Gao, and Pan Peng. 2020. Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_3_2_2_17_1","volume-title":"An Optimal Algorithm for Triangle Counting. arXiv preprint arXiv:2105.01785","author":"Jayaram Rajesh","year":"2021","unstructured":"Rajesh Jayaram and John Kallaugher . 2021. An Optimal Algorithm for Triangle Counting. arXiv preprint arXiv:2105.01785 ( 2021 ). Rajesh Jayaram and John Kallaugher. 2021. An Optimal Algorithm for Triangle Counting. arXiv preprint arXiv:2105.01785 (2021)."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_72"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00059"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319706"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.116"},{"key":"e_1_3_2_2_22_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Kane Daniel M","unstructured":"Daniel M Kane , Kurt Mehlhorn , Thomas Sauerwald , and He Sun . 2012. Counting arbitrary subgraphs in data streams . In International Colloquium on Automata, Languages, and Programming . Springer , 598--609. Daniel M Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. 2012. Counting arbitrary subgraphs in data streams. In International Colloquium on Automata, Languages, and Programming. Springer, 598--609."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_57"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387652"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_3_2_2_30_1","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial optimization: polyhedra and efficiency . Vol. 24 . Springer Science & Business Media . Alexander Schrijver. 2003. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer Science & Business Media."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524145","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3524145","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:04Z","timestamp":1750182544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":31,"alternative-id":["10.1145\/3517804.3524145","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3524145","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}