{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T04:55:35Z","timestamp":1783832135942,"version":"3.55.0"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61932001"],"award-info":[{"award-number":["61932001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00778-023-00783-3","type":"journal-article","created":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T13:03:07Z","timestamp":1678366987000},"page":"1087-1110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Sliding window-based approximate triangle counting with bounded memory usage"],"prefix":"10.1007","volume":"32","author":[{"given":"Xiangyang","family":"Gou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8586-4400","authenticated-orcid":false,"given":"Lei","family":"Zou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"issue":"5","key":"783_CR1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119","volume":"83","author":"JW Berry","year":"2011","unstructured":"Berry, J.W., Hendrickson, B., LaViolette, R.A., Phillips, C.A.: Tolerating the community detection resolution limit with edge weighting. Phys. Rev. E 83(5), 056119 (2011)","journal-title":"Phys. Rev. E"},{"issue":"9","key":"783_CR2","doi-asserted-by":"publisher","first-page":"5825","DOI":"10.1073\/pnas.032093399","volume":"99","author":"E Jean-Pierre","year":"2002","unstructured":"Jean-Pierre, E., Elisha, Moses: Curvature of co-links uncovers hidden thematic layers in the world wide web. Proc. Natl. Acad. Sci. USA 99(9), 5825\u20135829 (2002)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"3","key":"783_CR3","first-page":"13","volume":"4","author":"L Becchetti","year":"2010","unstructured":"Becchetti, L., Boldi, Paolo, Castillo, C., Gionis, A.: Efficient algorithms for large-scale local triangle counting. ACM Trans. Know. Dis. Data (TKDD) 4(3), 13 (2010)","journal-title":"ACM Trans. Know. Dis. Data (TKDD)"},{"issue":"5594","key":"783_CR4","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R., Shen-Orr, Shai, Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, Uri: Network motifs: simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2002)","journal-title":"Science"},{"issue":"2","key":"783_CR5","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1109\/TKDE.2012.244","volume":"26","author":"U Kang","year":"2012","unstructured":"Kang, U., Meeder, B., Papalexakis, Evangelos E., Faloutsos, C.: Heigen: Spectral analysis for billion-scale graphs. IEEE Trans. Know. Data Eng. 26(2), 350\u2013362 (2012)","journal-title":"IEEE Trans. Know. Data Eng."},{"issue":"1","key":"783_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2556609","volume":"8","author":"Z Yang","year":"2014","unstructured":"Yang, Z., Wilson, C., Wang, X., Gao, T., Zhao, B.Y., Dai, Y.: Uncovering social network sybils in the wild. ACM Trans. Know. Dis. Data (TKDD) 8(1), 1\u201329 (2014)","journal-title":"ACM Trans. Know. Dis. Data (TKDD)"},{"issue":"2","key":"783_CR7","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/s41019-018-0068-2","volume":"3","author":"Z Li","year":"2018","unstructured":"Li, Z., Yunting, Lu., Zhang, W.-P., Li, R.-H., Guo, J., Huang, X., Mao, Rui: Discovering hierarchical subgraphs of k-core-truss. Data Sci. Eng. 3(2), 136\u2013149 (2018)","journal-title":"Data Sci. Eng."},{"issue":"14","key":"783_CR8","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., Kun Lung, Wu.: Counting and sampling triangles from a graph stream. Proc. Vldb Endowment 6(14), 1870\u20131881 (2013)","journal-title":"Proc. Vldb Endowment"},{"key":"783_CR9","doi-asserted-by":"crossref","unstructured":"Ahmed, N. K., Duffield, N., Neville, J., & Kompella, R.: Graph sample and hold: A framework for big-graph analytics. In: Acm Sigkdd International Conference on Knowledge Discovery & Data Mining, (2014)","DOI":"10.1145\/2623330.2623757"},{"issue":"2","key":"783_CR10","doi-asserted-by":"publisher","first-page":"162","DOI":"10.14778\/3149193.3149197","volume":"11","author":"P Wang","year":"2017","unstructured":"Wang, P., Qi, Y., Sun, Yu., Zhang, X., Guan, X.: Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. Proc. Vldb Endowment 11(2), 162\u2013175 (2017)","journal-title":"Proc. Vldb Endowment"},{"issue":"4","key":"783_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/MC.2005.132","volume":"38","author":"PO Boykin","year":"2005","unstructured":"Boykin, P.O., Roychowdhury, Vwani P.: Leveraging social networks to fight spam. Computer 38(4), 61\u201368 (2005)","journal-title":"Computer"},{"issue":"6","key":"783_CR12","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. Siam J. Comput. 31(6), 1794\u20131813 (2002)","journal-title":"Siam J. Comput."},{"key":"783_CR13","doi-asserted-by":"crossref","unstructured":"Li, Y., Zou, L., \u00d6zsu, M.T., Dongyan, Z.: Time constrained continuous subgraph search over streaming graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 1082\u20131093. IEEE, (2019)","DOI":"10.1109\/ICDE.2019.00100"},{"key":"783_CR14","doi-asserted-by":"crossref","unstructured":"Crouch, M.S., McGregor, A., Stubbs, D.: Dynamic graphs in the sliding-window model. In European Symposium on Algorithms, pages 337\u2013348. Springer, (2013)","DOI":"10.1007\/978-3-642-40450-4_29"},{"issue":"12","key":"783_CR15","doi-asserted-by":"publisher","first-page":"1876","DOI":"10.14778\/3229863.3229874","volume":"11","author":"X Qiu","year":"2018","unstructured":"Qiu, X., Cen, W., Qian, Z., Peng, Y., Zhang, Y., Lin, X., Zhou, J.: Real-time constrained cycle detection in large dynamic graphs. Proc. VLDB Endowment 11(12), 1876\u20131888 (2018)","journal-title":"Proc. VLDB Endowment"},{"issue":"5","key":"783_CR16","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1007\/s10618-019-00630-6","volume":"33","author":"M Jung","year":"2019","unstructured":"Jung, M., Lim, Y., Lee, S., Kang, U.: Furl: fixed-memory and uncertainty reducing local triangle counting for multigraph streams. Data Min. Know. Dis. 33(5), 1225\u20131253 (2019)","journal-title":"Data Min. Know. Dis."},{"issue":"4","key":"783_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3059194","volume":"11","author":"Lorenzo De Stefani","year":"2017","unstructured":"De Stefani, Lorenzo, Epasto, Alessandro, Riondato, Matteo, Upfal, Eli: Triest: counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans. Know. Dis. Data (TKDD) 11(4), 1\u201350 (2017)","journal-title":"ACM Trans. Know. Dis. Data (TKDD)"},{"issue":"2","key":"783_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3375392","volume":"14","author":"Kijung Shin","year":"2020","unstructured":"Shin, Kijung, Sejoon, Oh., Kim, Jisu, Hooi, Bryan, Faloutsos, Christos: Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans. Know. Dis. Data (TKDD) 14(2), 1\u201339 (2020)","journal-title":"ACM Trans. Know. Dis. Data (TKDD)"},{"key":"783_CR19","doi-asserted-by":"crossref","unstructured":"Gemulla, R., Lehner, W.: Sampling time-based sliding windows in bounded space. In: Acm Sigmod International Conference on Management of Data, (2008)","DOI":"10.1145\/1376616.1376657"},{"key":"783_CR20","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Fusy, \u00c9., Gandouet, O., Meunier, F.: Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science, pages 137\u2013156. Discrete Mathematics and Theoretical Computer Science, (2007)","DOI":"10.46298\/dmtcs.3545"},{"key":"783_CR21","doi-asserted-by":"crossref","unstructured":"Ting, D.: Streamed approximate counting of distinct elements: Beating optimal batch methods. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 442\u2013451 (2014)","DOI":"10.1145\/2623330.2623669"},{"key":"783_CR22","unstructured":"Dongjin, L., Kijung, S., Christos, F.: Temporal locality-aware sampling for accurate triangle counting in real graph streams. The VLDB Journal, pages 1\u201325 (2020)"},{"key":"783_CR23","unstructured":"Source code of swtc and the baseline method. https:\/\/github.com\/StreamingTriangleCounting\/TriangleCounting.git"},{"key":"783_CR24","unstructured":"Brian, B., Mayur, D., Rajeev, M.: Sampling from a moving window over streaming data. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 633\u2013634. Society for Industrial and Applied Mathematics (2002)"},{"issue":"4","key":"783_CR25","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R Seidel","year":"1996","unstructured":"Seidel, R., Aragon, Cecilia R.: Randomized search trees. Algorithmica 16(4), 464\u2013497 (1996)","journal-title":"Algorithmica"},{"key":"783_CR26","volume-title":"Statistical Independence in Probability","author":"Mark Kac","year":"2018","unstructured":"Kac, Mark: Statistical Independence in Probability. Courier Dover Publications, Analysis and Number, New York (2018)"},{"issue":"3","key":"783_CR27","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1109\/90.929851","volume":"9","author":"NG Duffield","year":"2001","unstructured":"Duffield, N.G., Grossglauser, M.: Trajectory sampling for direct traffic observation. IEEE\/ACM Trans. Netw. 9(3), 280\u2013292 (2001)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"3","key":"783_CR28","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1214\/088342304000000206","volume":"19","author":"Nick Duffield","year":"2004","unstructured":"Duffield, Nick: Sampling for passive internet measurement: A review. Stat. Sci. 19(3), 472\u2013498 (2004)","journal-title":"Stat. Sci."},{"key":"783_CR29","doi-asserted-by":"crossref","unstructured":"Aggarwal, C.C., Yuchen, Z., Yu, P.S.: Outlier detection in graph streams. In 2011 IEEE 27th international conference on data engineering, pages 399\u2013409. IEEE, (2011)","DOI":"10.1109\/ICDE.2011.5767885"},{"key":"783_CR30","unstructured":"Ashish, T., Sen, S.J., Namit, J., Zheng, S., Prasad, C., Ning, Z., Suresh, A., Hao, L., Raghotham, M.: Hive-a petabyte scale data warehouse using hadoop. In: 2010 IEEE 26th international conference on data engineering (ICDE 2010), pages 996\u20131005. IEEE (2010)"},{"key":"783_CR31","unstructured":"Maurizio, M., Saverio, N., Duffield, N.G.: A comparative experimental study of hash functions applied to packet sampling. In: Proc. of International Teletraffic Congress (ITC) (2005)"},{"issue":"7","key":"783_CR32","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"GM Slota","year":"1970","unstructured":"Slota, G.M., Madduri, Kamesh: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"783_CR33","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Kamesh, M.: Complex network analysis using parallel approximate motif counting. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pages 405\u2013414. IEEE, (2014)","DOI":"10.1109\/IPDPS.2014.50"},{"issue":"4","key":"783_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186586","volume":"12","author":"M Bressan","year":"2018","unstructured":"Bressan, M., Chierichetti, F., Kumar, R., Leucci, S., Panconesi, A.: Motif counting beyond five nodes. ACM Trans. Know. Dis. Data (TKDD) 12(4), 1\u201325 (2018)","journal-title":"ACM Trans. Know. Dis. Data (TKDD)"},{"key":"783_CR35","unstructured":"Bobhash function. http:\/\/burtleburtle.net\/bob\/hash\/doobs.html"},{"key":"783_CR36","unstructured":"Murmurhash function. Published by Austin Appleby at https:\/\/github.com\/aappleby\/smhasher"},{"key":"783_CR37","unstructured":"Sedgewick, R.:. Algorithms in c. Pearson Education, (2001)"},{"key":"783_CR38","unstructured":"Aphash and collection of other hash functions. http:\/\/www.partow.net\/programming\/hashfunctions\/#RSHashFunction"},{"issue":"3","key":"783_CR39","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)","journal-title":"Algorithmica"},{"key":"783_CR40","unstructured":"Shaikh, A., Maleq, K., Madhav, M.: Patric: a parallel algorithm for counting triangles in massive networks. In Acm International Conference on Information & Knowledge Management, (2013)"},{"key":"783_CR41","unstructured":"Xiaocheng, H., Yufei, T., Chung, C.W.: Massive graph triangulation. In: Acm Sigmod International Conference on Management of Data, (2013)"},{"key":"783_CR42","unstructured":"Jinha, K., Wook, S.H., Sangyeon, L., Kyungyeol, P., Yu, H.: Opt:a new framework for overlapped and parallel triangulation in large-scale graphs. (2014)"},{"key":"783_CR43","doi-asserted-by":"crossref","unstructured":"Ha-Myung, P., Sung-Hyon, M., Kang, U.: Pte: Enumerating trillion triangles on distributed systems. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1115\u20131124 (2016)","DOI":"10.1145\/2939672.2939757"},{"key":"783_CR44","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 623\u2013632. Society for Industrial and Applied Mathematics (2002)"},{"key":"783_CR45","doi-asserted-by":"crossref","unstructured":"Buriol, S.L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In Acm Sigmod-sigact-sigart Symposium on Principles of Database Systems, (2006)","DOI":"10.1145\/1142351.1142388"},{"key":"783_CR46","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Ghodsi, M.: New streaming algorithms for counting triangles in graphs. In International Computing and Combinatorics Conference, pages 710\u2013716. Springer, (2005)","DOI":"10.1007\/11533719_72"},{"key":"783_CR47","doi-asserted-by":"crossref","unstructured":"Lim, Y., Kang, U.: 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, pages 685\u2013694. ACM (2015)","DOI":"10.1145\/2783258.2783285"},{"key":"783_CR48","doi-asserted-by":"crossref","unstructured":"Jha, M., Seshadhri, C., Pinar, A.: A space efficient streaming algorithm for triangle counting using the birthday paradox. (2013)","DOI":"10.1145\/2487575.2487678"},{"key":"783_CR49","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Kang, U., Miller, G.L., Faloutsos, C.: Doulion: counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 837\u2013846, (2009)","DOI":"10.1145\/1557019.1557111"},{"issue":"1","key":"783_CR50","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"Jeffrey S Vitter","year":"1985","unstructured":"Vitter, Jeffrey S.: Random sampling with a reservoir. ACM Trans. Math. Soft. (TOMS) 11(1), 37\u201357 (1985)","journal-title":"ACM Trans. Math. Soft. (TOMS)"},{"issue":"2","key":"783_CR51","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00778-007-0065-y","volume":"17","author":"R Gemulla","year":"2008","unstructured":"Gemulla, R., Lehner, Wolfgang, Haas, P.J.: Maintaining bounded-size sample synopses of evolving datasets. The VLDB J. 17(2), 173\u2013201 (2008)","journal-title":"The VLDB J."},{"key":"783_CR52","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R., Zaniolo, C.: Optimal sampling from sliding windows. In Twenty-eighth Acm Sigmod-sigact-sigart Symposium on Principles of Database Systems, (2009)","DOI":"10.1145\/1559795.1559818"},{"key":"783_CR53","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K., Zhang, Q.: Optimal sampling from distributed streams. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 77\u201386, (2010)","DOI":"10.1145\/1807085.1807099"},{"key":"783_CR54","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Trans. Know. Dis. Data (TKDD), 1(1):2\u2013es, (2007)","DOI":"10.1145\/1217299.1217301"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00783-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00783-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00783-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T01:55:47Z","timestamp":1729043747000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00783-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":54,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["783"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00783-3","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"assertion":[{"value":"6 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}