{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T18:19:02Z","timestamp":1761157142615,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["RI-NSF 1813444, CCF-NSF 1740741"],"award-info":[{"award-number":["RI-NSF 1813444, CCF-NSF 1740741"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We introduce\n            <jats:sc>Tiered Sampling<\/jats:sc>\n            , a novel technique for estimating the count of sparse motifs in massive graphs whose edges are observed in a stream. Our technique requires only a single pass on the data and uses a memory of fixed size\n            <jats:italic>M<\/jats:italic>\n            , which can be magnitudes smaller than the number of edges.\n          <\/jats:p>\n          <jats:p>\n            Our methods address the challenging task of counting sparse motifs\u2014sub-graph patterns\u2014that have a low probability of appearing in a sample of\n            <jats:italic>M<\/jats:italic>\n            edges in the graph, which is the maximum amount of data available to the algorithms in each step. To obtain an unbiased and low variance estimate of the count, we partition the available memory into tiers (layers) of reservoir samples. While the base layer is a standard reservoir sample of edges, other layers are reservoir samples of sub-structures of the desired motif. By storing more frequent sub-structures of the motif, we increase the probability of detecting an occurrence of the sparse motif we are counting, thus decreasing the variance and error of the estimate.\n          <\/jats:p>\n          <jats:p>\n            While we focus on the designing and analysis of algorithms for counting 4-cliques, we present a method which allows generalizing\n            <jats:sc>Tiered Sampling<\/jats:sc>\n            to obtain high-quality estimates for the number of occurrence of any sub-graph of interest, while reducing the analysis effort due to specific properties of the pattern of interest.\n          <\/jats:p>\n          <jats:p>We present a complete analytical analysis and extensive experimental evaluation of our proposed method using both synthetic and real-world data. Our results demonstrate the advantage of our method in obtaining high-quality approximations for the number of 4 and 5-cliques for large graphs using a very limited amount of memory, significantly outperforming the single edge sample approach for counting sparse motifs in large scale graphs.<\/jats:p>","DOI":"10.1145\/3441299","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T22:24:14Z","timestamp":1620685454000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Tiered Sampling"],"prefix":"10.1145","volume":"15","author":[{"given":"Lorenzo De","family":"Stefani","sequence":"first","affiliation":[{"name":"Brown University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erisa","family":"Terolli","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Stuhlsatzenhausweg, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the VLDB Endowment 10","author":"Ahmed Nesreen K.","year":"2017","unstructured":"Nesreen K. Ahmed , Nick Duffield , Theodore Willke , and Ryan A. Rossi . 2017. On sampling from massive graph streams . Proceedings of the VLDB Endowment 10 , 11 ( 2017 ). Nesreen K. Ahmed, Nick Duffield, Theodore Willke, and Ryan A. Rossi. 2017. On sampling from massive graph streams. Proceedings of the VLDB Endowment 10, 11 (2017)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.24963\/ijcai.2018\/456"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/ICDM.2015.141"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_6_1","volume-title":"Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3","author":"Becchetti Luca","year":"2010","unstructured":"Luca Becchetti , Paolo Boldi , Carlos Castillo , and Aristides Gionis . 2010. Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3 ( 2010 ), 1--28. Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2010. Efficient algorithms for large-scale local triangle counting. ACM Transactions on Knowledge Discovery from Data 4, 3 (2010), 1--28."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1103\/PhysRevE.83.056119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1963405.1963488"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/ICDM.2008.109"},{"key":"e_1_2_1_10_1","volume-title":"Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data 12, 4","author":"Bressan Marco","year":"2018","unstructured":"Marco Bressan , Flavio Chierichetti , Ravi Kumar , Stefano Leucci , and Alessandro Panconesi . 2018. Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data 12, 4 ( 2018 ), 1--25. Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2018. Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data 12, 4 (2018), 1--25."},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.14778\/3342263.3342640"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/BigData.2017.8257993"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1073\/pnas.032093399"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/3219819.3220040"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/2794080"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1016\/j.ijforecast.2006.03.001"},{"volume-title":"Proceedings of the 26th International Conference on World Wide Web. 441--449","author":"Jain Shweta","unstructured":"Shweta Jain and C. Seshadhri . 2017. A fast and provable method for estimating clique counts using Tur\u00e1n\u2019s theorem . In Proceedings of the 26th International Conference on World Wide Web. 441--449 . Shweta Jain and C. Seshadhri. 2017. A fast and provable method for estimating clique counts using Tur\u00e1n\u2019s theorem. In Proceedings of the 26th International Conference on World Wide Web. 441--449.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_19_1","volume-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","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 ( 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 (2015), 1--21."},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/978-3-319-08404-6_27"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/1241540.1241551"},{"volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 685--694","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--694 . 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--694.","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/3289600.3290988"},{"key":"e_1_2_1_24_1","volume-title":"Network motifs: Simple building blocks of complex networks. Science 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo , Shai Shen-Orr , Shalev Itzkovitz , Nadav Kashtan , Dmitri Chklovskii , and Uri Alon . 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 ( 2002 ), 824--827. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824--827."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/1298306.1298311"},{"volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press.","key":"e_1_2_1_26_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1016\/j.ipl.2011.12.007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/3292500.3330995"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2505515.2505563"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.14778\/2556549.2556569"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/TKDE.2013.2297929"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/3219819.3220097"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/3059194"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/3147.3165"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441299","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:04Z","timestamp":1750197784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441299"}},"subtitle":["An Efficient Method for Counting Sparse Motifs in Massive Graph Streams"],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3441299"],"URL":"https:\/\/doi.org\/10.1145\/3441299","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"2019-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-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}