{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T07:24:22Z","timestamp":1780817062773,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>\n            The number of triangles of a streaming graph is a crucial metric with various applications, such as network evolution analysis, community detection, and anomaly detection. A practical solution for triangle counting in streaming graphs is the sampling-based approximation. Although a lot of research efforts have been devoted to the fixed-sized memory based algorithms, they suffer from the accuracy and the efficiency issues. To tackle these issues, we first propose the generalized reservoir sampling (GRS), which stores less edges for reducing the computational cost and can still generate uniformly random edge sample in the streaming graph. Then, we propose the GREAT algorithm based on GRS for efficient and accurate triangle counting estimation. To further improve the estimation accuracy, we propose the GREAT\n            <jats:sup>+<\/jats:sup>\n            algorithm for considering the dynamic timestamp interval distribution in real-world streaming graphs so that triangles with short and long timestamp intervals will be sampled following the ground-truth distribution. Extensive evaluations on real datasets demonstrate the efficiency and the accuracy of our algorithms. The relative error of our algorithm GREAT\n            <jats:sup>+<\/jats:sup>\n            is significantly (an order of magnitude) better than the competitors.\n          <\/jats:p>","DOI":"10.14778\/3734839.3734842","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:06Z","timestamp":1756483266000},"page":"2031-2043","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["GREAT: Generalized Reservoir Sampling Based Triangle Counting Estimation over Streaming Graphs"],"prefix":"10.14778","volume":"18","author":[{"given":"Siyue","family":"Wu","sequence":"first","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dingming","family":"Wu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sinhong","family":"Cheuk","sequence":"additional","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsz Nam","family":"Chan","sequence":"additional","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kezhong","family":"Lu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Software Engineering, Shenzhen University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Nesreen K. Ahmed Nick G. Duffield Jennifer Neville and Ramana Rao Kompella. 2014. Graph sample and hold: a framework for big-graph analytics. In KDD. 1446\u20131455.","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","volume-title":"Network Sampling: From Static to Streaming Graphs. TKDD 8, 2","author":"Ahmed Nesreen K.","year":"2013","unstructured":"Nesreen K. Ahmed, Jennifer Neville, and Ramana Rao Kompella. 2013. Network Sampling: From Static to Streaming Graphs. TKDD 8, 2 (2013), 7:1\u20137:56."},{"key":"e_1_2_1_3_1","volume-title":"Oliver Alvarado Rodriguez, and Zhihui Du","author":"Bader David A.","year":"2023","unstructured":"David A. Bader, Fuhuan Li, Anya Ganeshan, Ahmet G\u00fcndogdu, Jason Lew, Oliver Alvarado Rodriguez, and Zhihui Du. 2023. Triangle Counting Through Cover-Edges. In HPEC. 1\u20137."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The webgraph framework I: compression techniques. In WWW. 595\u2013602.","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Luciana S. Buriol Gereon Frahling Stefano Leonardi Alberto Marchetti-Spaccamela and Christian Sohler. 2006. Counting triangles in data streams. In PODS. 253\u2013262.","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Don Coppersmith and Shmuel Winograd. 1987. Matrix Multiplication via Arithmetic Progressions. In STOC. 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"e_1_2_1_7_1","volume-title":"Datastream clustering over tilted windows through sampling. Knowledge discovery from data streams","author":"Csernel Baptiste","year":"2006","unstructured":"Baptiste Csernel, Fabrice Clerot, and Georges H\u00e9brail. 2006. Datastream clustering over tilted windows through sampling. Knowledge discovery from data streams (2006), 127."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Rainer Gemulla and Wolfgang Lehner. 2008. Sampling time-based sliding windows in bounded space. In SIGMOD. 379\u2013392.","DOI":"10.1145\/1376616.1376657"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0065-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Sayan Ghosh and Mahantesh Halappanavar. 2020. TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure. In HPEC. 1\u20136.","DOI":"10.1109\/HPEC43674.2020.9286167"},{"key":"e_1_2_1_11_1","volume-title":"Gibbons and Yossi Matias","author":"Phillip","year":"1998","unstructured":"Phillip B. Gibbons and Yossi Matias. 1998. New Sampling-Based Summary Statistics for Improving Approximate Query Answers. In SIGMOD. 331\u2013342."},{"key":"e_1_2_1_12_1","volume-title":"Gibbons and Srikanta Tirthapura","author":"Phillip","year":"2001","unstructured":"Phillip B. Gibbons and Srikanta Tirthapura. 2001. Estimating simple functions on the union of data streams. In SPAA. 281\u2013291."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Xiangyang Gou and Lei Zou. 2021. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. In SIGMOD. 645\u2013657.","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00783-3"},{"key":"e_1_2_1_15_1","unstructured":"Shenyang Huang Farimah Poursafaei Jacob Danovitch Matthias Fey Weihua Hu Emanuele Rossi Jure Leskovec Michael M. Bronstein Guillaume Rabusseau and Reihaneh Rabbany. 2023. Temporal Graph Benchmark for Machine Learning on Temporal Graphs. In NIPS."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Madhav Jha C. Seshadhri and Ali Pinar. 2013. A space efficient streaming algorithm for triangle counting using the birthday paradox. In SIGKDD. 589\u2013597.","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_17_1","volume-title":"A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox. TKDD 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. TKDD 9, 3 (2015), 15:1\u201315:21."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00630-6"},{"key":"e_1_2_1_19_1","volume-title":"Kiana Mousavi Hanjani, and A. Pavan","author":"Kavassery-Parakkat Neeraj","year":"2018","unstructured":"Neeraj Kavassery-Parakkat, Kiana Mousavi Hanjani, and A. Pavan. 2018. Improved Triangle Counting in Graph Streams: Power of Multi-Sampling. In ASONAM. 33\u201340."},{"key":"e_1_2_1_20_1","volume-title":"The art of computer programming","author":"Knuth Donald E","unstructured":"Donald E Knuth. 1973. The art of computer programming, vol. 2:Seminumerical Algorithms. Reading MA: Addison-Wisley (1973), 144."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW. 1343\u20131350.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Bibudh Lahiri and Srikanta Tirthapura. 2009. Stream Sampling. Springer US 2838\u20132842.","DOI":"10.1007\/978-0-387-39940-9_372"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/198429.198435"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022186"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_29_1","first-page":"121","article-title":"Fraud Detection Using the Fraud Triangle Theory and Data Mining Techniques","volume":"10","author":"S\u00e1nchez-Aguayo Marco","year":"2021","unstructured":"Marco S\u00e1nchez-Aguayo, Luis Urquiza-Aguiar, and Jos\u00e9 Estrada-Jim\u00e9nez. 2021. Fraud Detection Using the Fraud Triangle Theory and Data Mining Techniques: A Literature Review. Comput. 10, 10 (2021), 121.","journal-title":"A Literature Review. Comput."},{"key":"e_1_2_1_30_1","volume-title":"Ahmet Erdem Sariy\u00fcce, and Srikanta Tirthapura","author":"Sanei-Mehri Seyed-Vahid","year":"2019","unstructured":"Seyed-Vahid Sanei-Mehri, Yu Zhang, Ahmet Erdem Sariy\u00fcce, and Srikanta Tirthapura. 2019. FLEET: Butterfly Estimation from a Bipartite Graph Stream. In CIKM. 1201\u20131210."},{"key":"e_1_2_1_31_1","volume-title":"WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. In ICDM. 1087\u20131092.","author":"Shin Kijung","year":"2017","unstructured":"Kijung Shin. 2017. WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. In ICDM. 1087\u20131092."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Kijung Shin Mohammad Hammoud Euiwoong Lee Jinoh Oh and Christos Faloutsos. 2018. Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams. In PAKDD. 651\u2013663.","DOI":"10.1007\/978-3-319-93040-4_51"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Kijung Shin Jisu Kim Bryan Hooi and Christos Faloutsos. 2018. Think Before You Discard: Accurate Triangle Counting in Graph Streams with Deletions. In PKDD. 141\u2013157.","DOI":"10.1007\/978-3-030-10928-8_9"},{"key":"e_1_2_1_34_1","volume-title":"CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. TKDD 15, 3","author":"Shin Kijung","year":"2021","unstructured":"Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, and Christos Faloutsos. 2021. CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. TKDD 15, 3 (2021), 38:1\u201338:30."},{"key":"e_1_2_1_35_1","unstructured":"Rayane El Sibai Yousra Chabchoub Jacques Demerjian Zakia Kazi-Aoul and Kablan Barbar. [n.d.]. Sampling algorithms in data stream environments. In ICDEc. 29\u201336."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Paramvir Singh Venkatesh Srinivasan and Alex Thomo. 2021. Fast and Scalable Triangle Counting in Graph Streams: The Hybrid Approach. In AINA. 107\u2013119.","DOI":"10.1007\/978-3-030-75075-6_9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081079.2020.1863394"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Lorenzo De Stefani Alessandro Epasto Matteo Riondato and Eli Upfal. 2016. TRI\u00c8ST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size. In SIGKDD. 825\u2013834.","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Kanat Tangwongsan A. Pavan and Srikanta Tirthapura. 2013. Parallel triangle counting in massive streaming graphs. In CIKM. 781\u2013786.","DOI":"10.1145\/2505515.2505741"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Charalampos E. Tsourakakis. 2008. Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws. In ICDM. 608\u2013617.","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Charalampos E. Tsourakakis U Kang Gary L. Miller and Christos Faloutsos. 2009. DOULION: counting triangles in massive graphs with a coin. In KDD. 837\u2013846.","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_44_1","volume-title":"REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel. In ICDE. 758\u2013769.","author":"Wang Pinghui","year":"2019","unstructured":"Pinghui Wang, Peng Jia, Yiyan Qi, Yu Sun, Jing Tao, and Xiaohong Guan. 2019. REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel. In ICDE. 758\u2013769."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149197"},{"key":"e_1_2_1_46_1","volume-title":"Social Network Analysis: Methods and Applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press."},{"key":"e_1_2_1_47_1","volume-title":"Tsz Nam Chan, and Kezhong Lu","author":"Wu Siyue","year":"2025","unstructured":"Siyue Wu, Dingming Wu, Sinhong Cheuk, Tsz Nam Chan, and Kezhong Lu. 2025. Supplementary material for \"GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs\". https:\/\/github.com\/sinhong-cheuk\/GREAT-Generalized-Reservoir-Sampling-based-Triangle-Counting-Estimation-over-Streaming-Graphs."},{"key":"e_1_2_1_48_1","first-page":"110878","article-title":"A distributed streaming framework for edge-cloud triangle counting in graph streams","volume":"278","author":"Yang Xu","year":"2023","unstructured":"Xu Yang, Chao Song, Jiqing Gu, Ke Li, and Hongwei Li. 2023. A distributed streaming framework for edge-cloud triangle counting in graph streams. KBS 278 (2023), 110878.","journal-title":"KBS"},{"key":"e_1_2_1_49_1","volume-title":"Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream. TKDD 16, 4","author":"Yang Xu","year":"2022","unstructured":"Xu Yang, Chao Song, Mengdi Yu, Jiqing Gu, and Ming Liu. 2022. Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream. TKDD 16, 4 (2022), 79:1\u201379:43."},{"key":"e_1_2_1_50_1","first-page":"14079","article-title":"Global triangle estimation based on first edge sampling in large graph streams","volume":"79","author":"Yu Changyong","year":"2023","unstructured":"Changyong Yu, Huimin Liu, Fazal Wahab, Zihan Ling, Tianmei Ren, Haitao Ma, and Yuhai Zhao. 2023. Global triangle estimation based on first edge sampling in large graph streams. TJS 79, 13 (2023), 14079\u201314116.","journal-title":"TJS"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Mengdi Yu Chao Song Jiqing Gu and Ming Liu. 2019. Distributed Triangle Counting Algorithms in Simple Graph Stream. In ICPADS. 294\u2013301.","DOI":"10.1109\/ICPADS47876.2019.00049"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Lingling Zhang Hong Jiang Fang Wang Dan Feng and Yanwen Xie. 2019. T-Sample: A Dual Reservoir-Based Sampling Method for Characterizing Large Graph Streams. In ICDE. 1674\u20131677.","DOI":"10.1109\/ICDE.2019.00170"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2020.02.077"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3236335"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3734839.3734842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:37Z","timestamp":1756483297000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3734839.3734842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":54,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.14778\/3734839.3734842"],"URL":"https:\/\/doi.org\/10.14778\/3734839.3734842","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}