{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T03:42:10Z","timestamp":1784950930577,"version":"3.55.0"},"reference-count":41,"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"}],"funder":[{"name":"Academy of Finland projects","award":["286211, 313927, and 317085"],"award-info":[{"award-number":["286211, 313927, and 317085"]}]},{"name":"EC H2020 RIA project \u201cSoBigData\u201d","award":["654024"],"award-info":[{"award-number":["654024"]}]},{"name":"National Science Foundation project","award":["2006765"],"award-info":[{"award-number":["2006765"]}]}],"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:disp-quote>\n              <jats:p>\u201cPerhaps he could dance first and think afterwards, if it isn\u2019t too much to ask him.\u201d<\/jats:p>\n            <\/jats:disp-quote>\n          <\/jats:p>\n          <jats:p>\n            S.\u00a0Beckett,\n            <jats:italic>Waiting for Godot<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            Given a labeled graph, the collection of\n            <jats:italic>k<\/jats:italic>\n            -vertex induced connected subgraph patterns that appear in the graph more frequently than a user-specified minimum threshold provides a compact summary of the characteristics of the graph, and finds applications ranging from biology to network science. However, finding these patterns is challenging, even more so for dynamic graphs that evolve over time, due to the streaming nature of the input and the exponential time complexity of the problem.\n          <\/jats:p>\n          <jats:p>\n            We study this task in both incremental and fully-dynamic streaming settings, where arbitrary edges can be added or removed from the graph. We present\n            <jats:sc>TipTap<\/jats:sc>\n            , a suite of algorithms to compute high-quality approximations of the frequent\n            <jats:italic>k<\/jats:italic>\n            -vertex subgraphs w.r.t.\u00a0a given threshold, at any time (i.e., point of the stream), with high probability. In contrast to existing state-of-the-art solutions that require iterating over the entire set of subgraphs in the vicinity of the updated edge,\n            <jats:sc>TipTap<\/jats:sc>\n            operates by efficiently maintaining a uniform sample of connected\n            <jats:italic>k<\/jats:italic>\n            -vertex subgraphs, thanks to an optimized neighborhood-exploration procedure. We provide a theoretical analysis of the proposed algorithms in terms of their unbiasedness and of the sample size needed to obtain a desired approximation quality. Our analysis relies on sample-complexity bounds that use Vapnik\u2013Chervonenkis dimension, a key concept from statistical learning theory, which allows us to derive a sufficient sample size that is independent from the size of the graph. The results of our empirical evaluation demonstrates that\n            <jats:sc>TipTap<\/jats:sc>\n            returns high-quality results more efficiently and accurately than existing baselines.\n          <\/jats:p>","DOI":"10.1145\/3442590","type":"journal-article","created":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T15:42:54Z","timestamp":1619019774000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["TipTap: Approximate Mining of Frequent\n            <i>k<\/i>\n            -Subgraph Patterns in Evolving Graphs"],"prefix":"10.1145","volume":"15","author":[{"given":"Muhammad Anis Uddin","family":"Nasir","sequence":"first","affiliation":[{"name":"King Digital Entertainment Ltd, Stockholm, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5556-8977","authenticated-orcid":false,"given":"Cigdem","family":"Aslay","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2415-494X","authenticated-orcid":false,"given":"Gianmarco De Francisci","family":"Morales","sequence":"additional","affiliation":[{"name":"ISI Foundation, Turin, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2523-4420","authenticated-orcid":false,"given":"Matteo","family":"Riondato","sequence":"additional","affiliation":[{"name":"Amherst College, Amherst, MA, USA"}],"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.1109\/TKDE.2017.2743075"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271772"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 684\u2013697","author":"Babai L\u00e1szl\u00f3","year":"2016","unstructured":"L\u00e1szl\u00f3 Babai . 2016 . Graph isomorphism in quasipolynomial time . In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 684\u2013697 . L\u00e1szl\u00f3 Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 684\u2013697."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020501"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.109"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.124"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2014.08.114"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68125-0_84"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.36"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110042"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS.2008.32"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257993"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. 595\u2013606","author":"Gemulla Rainer","unstructured":"Rainer Gemulla , Wolfgang Lehner , and Peter J. Haas . 2006. A dip in the reservoir: Maintaining sample synopses of evolving datasets . In Proceedings of the 32nd International Conference on Very Large Data Bases. 595\u2013606 . Rainer Gemulla, Wolfgang Lehner, and Peter J. Haas. 2006. A dip in the reservoir: Maintaining sample synopses of evolving datasets. In Proceedings of the 32nd International Conference on Very Large Data Bases. 595\u2013606."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0065-y"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2313\u20132314","author":"Gionis Aristides","unstructured":"Aristides Gionis and Charalampos E. Tsourakakis . 2015. Dense subgraph discovery: Kdd 2015 tutorial . In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2313\u20132314 . Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense subgraph discovery: Kdd 2015 tutorial. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2313\u20132314."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116271.3116497"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05151-7_33"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45372-5_2"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Transactions on Knowledge Discovery from Data 9, 3","volume":"15","author":"Jha Madhav","year":"2015","unstructured":"Madhav Jha , C. Seshadhri , and Ali Pinar . 2015 . A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Transactions on Knowledge Discovery from Data 9, 3 , Article 15 (2015), 1 -- 21 . Madhav Jha, C. Seshadhri, and Ali Pinar. 2015. A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Transactions on Knowledge Discovery from Data 9, 3, Article 15 (2015), 1--21.","journal-title":"Article"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000331"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807261"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2001.989534"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 685\u2013694","author":"Lim Yongsub","unstructured":"Yongsub Lim and U. Kang . 2015. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams . In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 685\u2013694 . Yongsub Lim and U. Kang. 2015. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 685\u2013694."},{"key":"e_1_2_1_30_1","volume-title":"Phillips","author":"L\u00f6ffler Maarten","year":"2009","unstructured":"Maarten L\u00f6ffler and Jeff M . Phillips . 2009 . Shape fitting on point sets with probability distributions. In Proceedings of the European Symposium on Algorithms, Amos Fiat and Peter Sanders (Eds.). Lecture Notes in Computer Science, Vol. 5757 . Springer , Berlin, 313\u2013324. DOI:https:\/\/doi.org\/10.1007\/978-3-642-04128-0_29 10.1007\/978-3-642-04128-0_29 Maarten L\u00f6ffler and Jeff M. Phillips. 2009. Shape fitting on point sets with probability distributions. In Proceedings of the European Symposium on Algorithms, Amos Fiat and Peter Sanders (Eds.). Lecture Notes in Computer Science, Vol. 5757. Springer, Berlin, 313\u2013324. DOI:https:\/\/doi.org\/10.1007\/978-3-642-04128-0_29"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 3rd International Conference on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications. 166\u2013181","author":"Ray Abhik","year":"2014","unstructured":"Abhik Ray , Larry Holder , and Sutanay Choudhury . 2014 . Frequent subgraph discovery in large attributed streaming graphs . In Proceedings of the 3rd International Conference on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications. 166\u2013181 . Abhik Ray, Larry Holder, and Sutanay Choudhury. 2014. Frequent subgraph discovery in large attributed streaming graphs. In Proceedings of the 3rd International Conference on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications. 166\u2013181."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2018.2826529"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2169090.2169092"},{"key":"e_1_2_1_36_1","volume-title":"Miller","author":"Tsourakakis Charalampos E.","year":"2011","unstructured":"Charalampos E. Tsourakakis , Mihail N. Kolountzakis , and Gary L . Miller . 2011 . Triangle sparsifiers.Journal of Graph Algorithms and Applications 15, 6 (2011), 703\u2013726. Charalampos E. Tsourakakis, Mihail N. Kolountzakis, and Gary L. Miller. 2011. Triangle sparsifiers.Journal of Graph Algorithms and Applications 15, 6 (2011), 703\u2013726."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 8th Workshop on Mining and Learning with Graphs. ACM, 155\u2013162","author":"Wackersreuther Bianca","unstructured":"Bianca Wackersreuther , Peter Wackersreuther , Annahita Oswald , Christian B\u00f6hm , and Karsten M. Borgwardt . 2010. Frequent subgraph discovery in dynamic networks . In Proceedings of the 8th Workshop on Mining and Learning with Graphs. ACM, 155\u2013162 . Bianca Wackersreuther, Peter Wackersreuther, Annahita Oswald, Christian B\u00f6hm, and Karsten M. Borgwardt. 2010. Frequent subgraph discovery in dynamic networks. In Proceedings of the 8th Workshop on Mining and Learning with Graphs. ACM, 155\u2013162."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498312"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jneumeth.2009.04.021"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Data Mining (ICDM\u201902)","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han . 2002 . gSpan: Graph-based substructure pattern mining . In Proceedings of the International Conference on Data Mining (ICDM\u201902) . 721\u2013724. Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings of the International Conference on Data Mining (ICDM\u201902). 721\u2013724."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:02Z","timestamp":1750197782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,21]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442590"],"URL":"https:\/\/doi.org\/10.1145\/3442590","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":"2020-03-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"}}]}}