{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T18:43:18Z","timestamp":1790275398532,"version":"4.1.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2019R1F1A1059755"],"award-info":[{"award-number":["NRF-2019R1F1A1059755"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s00778-020-00624-7","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T04:09:48Z","timestamp":1597205388000},"page":"1501-1525","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Temporal locality-aware sampling for accurate triangle counting in real graph streams"],"prefix":"10.1007","volume":"29","author":[{"given":"Dongjin","family":"Lee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2872-1526","authenticated-orcid":false,"given":"Kijung","family":"Shin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"624_CR1","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: KDD, pp. 1446\u20131455 (2014)","DOI":"10.1145\/2623330.2623757"},{"issue":"11","key":"624_CR2","first-page":"1430","volume":"10","author":"NK Ahmed","year":"2017","unstructured":"Ahmed, N.K., Duffield, N., Willke, T.L., Rossi, R.A.: On sampling from massive graph streams. PVLDB 10(11), 1430\u20131441 (2017)","journal-title":"PVLDB"},{"key":"624_CR3","doi-asserted-by":"crossref","unstructured":"Arifuzzaman, S., Khan, M., Marathe, M.: Patric: A parallel algorithm for counting triangles in massive networks. In: CIKM, pp. 529\u2013538 (2013)","DOI":"10.1145\/2505515.2505545"},{"key":"624_CR4","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA, pp. 623\u2013632 (2002)"},{"issue":"5439","key":"624_CR5","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"3","key":"624_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1839490.1839494","volume":"4","author":"L Becchetti","year":"2010","unstructured":"Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient algorithms for large-scale local triangle counting. ACM Trans. Knowl. Discov. Data 4(3), 13 (2010)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"624_CR7","doi-asserted-by":"crossref","unstructured":"Brown, P.G., Haas, P.J.: Techniques for warehousing of sample data. In: ICDE, pp. 6\u20136 (2006)","DOI":"10.1109\/ICDE.2006.157"},{"issue":"4","key":"624_CR8","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/3059194","volume":"11","author":"L De Stefani","year":"2017","unstructured":"De Stefani, L., Epasto, A., Riondato, M., Upfal, E.: Tri\u00e8st: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans. Knowl. Discov. Data 11(4), 43 (2017)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"9","key":"624_CR9","doi-asserted-by":"publisher","first-page":"5825","DOI":"10.1073\/pnas.032093399","volume":"99","author":"JP Eckmann","year":"2002","unstructured":"Eckmann, J.P., Moses, E.: Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS 99(9), 5825\u20135829 (2002)","journal-title":"PNAS"},{"issue":"3","key":"624_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/BF02759702","volume":"1","author":"P Erd\u00f6s","year":"1963","unstructured":"Erd\u00f6s, P.: On the structure of linear graphs. Isr. J. Math. 1(3), 156\u2013160 (1963)","journal-title":"Isr. J. Math."},{"key":"624_CR11","doi-asserted-by":"crossref","unstructured":"Etemadi, R., Lu, J., Tsin, Y.H.: Efficient estimation of triangles in very large graphs. In: CIKM, pp. 1251\u20131260 (2016)","DOI":"10.1145\/2983323.2983849"},{"issue":"2","key":"624_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/980972.980992","volume":"5","author":"J Gehrke","year":"2003","unstructured":"Gehrke, J., Ginsparg, P., Kleinberg, J.: Overview of the 2003 kdd cup. ACM SIGKDD Explor. Newsl. 5(2), 149\u2013151 (2003)","journal-title":"ACM SIGKDD Explor. Newsl."},{"issue":"2","key":"624_CR13","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, W., Haas, P.J.: Maintaining bounded-size sample synopses of evolving datasets. VLDB J. 17(2), 173\u2013201 (2008)","journal-title":"VLDB J."},{"key":"624_CR14","doi-asserted-by":"crossref","unstructured":"Hall, B.H., Jaffe, A.B., Trajtenberg, M.: The nber patent citation data file: Lessons, insights and methodological tools. Tech. rep., National Bureau of Economic Research (2001)","DOI":"10.3386\/w8498"},{"key":"624_CR15","doi-asserted-by":"crossref","unstructured":"Han, G., Sethu, H.: Edge sample and discard: a new algorithm for counting triangles in large dynamic graphs. In: ASONAM, pp. 44\u201349 (2017)","DOI":"10.1145\/3110025.3110061"},{"issue":"4","key":"624_CR16","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/2691190.2691193","volume":"39","author":"X Hu","year":"2014","unstructured":"Hu, X., Tao, Y., Chung, C.W.: I\/O-efficient algorithms on triangle listing and counting. ACM Trans. Database Syst. 39(4), 27 (2014)","journal-title":"ACM Trans. Database Syst."},{"key":"624_CR17","doi-asserted-by":"crossref","unstructured":"Jha, M., Seshadhri, C., Pinar, A.: A space efficient streaming algorithm for triangle counting using the birthday paradox. In: KDD, pp. 589\u2013597 (2013)","DOI":"10.1145\/2487575.2487678"},{"issue":"5","key":"624_CR18","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. Knowl. Discov. 33(5), 1225\u20131253 (2019)","journal-title":"Data Min. Knowl. Discov."},{"key":"624_CR19","doi-asserted-by":"crossref","unstructured":"Kallaugher, J., Price, E.: A hybrid sampling scheme for triangle counting. In: SODA, pp. 1778\u20131797 (2017)","DOI":"10.1137\/1.9781611974782.116"},{"key":"624_CR20","doi-asserted-by":"crossref","unstructured":"Kim, J., Han, W.S., Lee, S., Park, K., Yu, H.: Opt: A new framework for overlapped and parallel triangulation in large-scale graphs. In: SIGMOD, pp. 637\u2013648 (2014)","DOI":"10.1145\/2588555.2588563"},{"key":"624_CR21","unstructured":"Klimt, B., Yang, Y.: Introducing the enron corpus. In: CEAS (2004)"},{"key":"624_CR22","first-page":"139","volume":"2","author":"DE Knuth","year":"1997","unstructured":"Knuth, D.E.: Seminumerical algorithms. Art Comput. Program. 2, 139\u2013140 (1997)","journal-title":"Art Comput. Program."},{"key":"624_CR23","doi-asserted-by":"crossref","unstructured":"Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient triangle counting in large graphs via degree-based vertex partitioning. In: WAW, pp. 15\u201324 (2010)","DOI":"10.1007\/978-3-642-18009-5_3"},{"key":"624_CR24","doi-asserted-by":"crossref","unstructured":"Kutzkov, K., Pagh, R.: On the streaming complexity of computing local clustering coefficients. In: WSDM, pp. 677\u2013686 (2013)","DOI":"10.1145\/2433396.2433480"},{"key":"624_CR25","doi-asserted-by":"crossref","unstructured":"Kutzkov, K., Pagh, R.: Triangle counting in dynamic graph streams. In: SWAT, pp. 306\u2013318 (2014)","DOI":"10.1007\/978-3-319-08404-6_27"},{"issue":"1","key":"624_CR26","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1(1), 2 (2007)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"624_CR27","doi-asserted-by":"crossref","unstructured":"Lim, Y., Kang, U.: Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In: KDD, pp. 685\u2013694 (2015)","DOI":"10.1145\/2783258.2783285"},{"issue":"1","key":"624_CR28","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1146\/annurev.soc.27.1.415","volume":"27","author":"M McPherson","year":"2001","unstructured":"McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: homophily in social networks. Annu. Rev. Sociol. 27(1), 415\u2013444 (2001)","journal-title":"Annu. Rev. Sociol."},{"key":"624_CR29","unstructured":"Mislove, A.: Online social networks: measurement, analysis, and applications to distributed information systems. Ph.D. thesis, Rice University (2009)"},{"issue":"2","key":"624_CR30","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"ME Newman","year":"2003","unstructured":"Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167\u2013256 (2003)","journal-title":"SIAM Rev."},{"key":"624_CR31","doi-asserted-by":"crossref","unstructured":"Park, H.M., Myaeng, S.H., Kang, U.: Pte: Enumerating trillion triangles on distributed systems. In: KDD, pp. 1115\u20131124 (2016)","DOI":"10.1145\/2939672.2939757"},{"key":"624_CR32","doi-asserted-by":"crossref","unstructured":"Park, H.M., Silvestri, F., Kang, U., Pagh, R.: Mapreduce triangle enumeration with guarantees. In: CIKM, pp. 1739\u20131748 (2014)","DOI":"10.1145\/2661829.2662017"},{"issue":"14","key":"624_CR33","first-page":"1870","volume":"6","author":"A Pavan","year":"2013","unstructured":"Pavan, A., Tangwongsan, K., Tirthapura, S., Wu, K.L.: Counting and sampling triangles from a graph stream. PVLDB 6(14), 1870\u20131881 (2013)","journal-title":"PVLDB"},{"key":"624_CR34","doi-asserted-by":"crossref","unstructured":"Seshadhri, C., Pinar, A., Kolda, T.G.: Triadic measures on graphs: the power of wedge sampling. In: SDM, pp. 10\u201318 (2013)","DOI":"10.1137\/1.9781611972832.2"},{"key":"624_CR35","doi-asserted-by":"crossref","unstructured":"Shin, K.: Wrs: Waiting room sampling for accurate triangle counting in real graph streams. In: ICDM, pp. 1087\u20131092 (2017)","DOI":"10.1109\/ICDM.2017.143"},{"issue":"3","key":"624_CR36","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/s10115-017-1077-6","volume":"54","author":"K Shin","year":"2018","unstructured":"Shin, K., Eliassi-Rad, T., Faloutsos, C.: Patterns and anomalies in k-cores of real-world graphs with applications. Knowl. Inf. Syst. 54(3), 677\u2013710 (2018)","journal-title":"Knowl. Inf. Syst."},{"key":"624_CR37","doi-asserted-by":"crossref","unstructured":"Shin, K., Hammoud, M., Lee, E., Oh, J., Faloutsos, C.: Tri-fly: Distributed estimation of global and local triangle counts in graph streams. In: PAKDD, pp. 651\u2013663 (2018)","DOI":"10.1007\/978-3-319-93040-4_51"},{"key":"624_CR38","doi-asserted-by":"crossref","unstructured":"Shin, K., Kim, J., Hooi, B., Faloutsos, C.: Think before you discard: accurate triangle counting in graph streams with deletions. In: ECML\/PKDD, pp. 141\u2013157 (2018)","DOI":"10.1007\/978-3-030-10928-8_9"},{"key":"624_CR39","unstructured":"Shin, K., Lee, E., Oh, J., Hammoud, M., Faloutsos, C.: Cocos: Fast and accurate distributed triangle counting in graph streams. arXiv preprint arXiv:1802.04249 (2018)"},{"issue":"2","key":"624_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3375392","volume":"14","author":"K Shin","year":"2020","unstructured":"Shin, K., Oh, S., Kim, J., Hooi, B., Faloutsos, C.: Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans. Knowl. Discov. Data 14(2), 1\u201339 (2020)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"624_CR41","doi-asserted-by":"crossref","unstructured":"Shun, J., Tangwongsan, K.: Multicore triangle computations without tuning. In: ICDE, pp. 149\u2013160 (2015)","DOI":"10.1109\/ICDE.2015.7113280"},{"issue":"1","key":"624_CR42","doi-asserted-by":"publisher","first-page":"72","DOI":"10.2307\/1412159","volume":"15","author":"C Spearman","year":"1904","unstructured":"Spearman, C.: The proof and measurement of association between two things. Am. J. Psychol. 15(1), 72\u2013101 (1904)","journal-title":"Am. J. Psychol."},{"key":"624_CR43","doi-asserted-by":"crossref","unstructured":"Suri, S., Vassilvitskii, S.: Counting triangles and the curse of the last reducer. In: WWW, pp. 607\u2013614 (2011)","DOI":"10.1145\/1963405.1963491"},{"key":"624_CR44","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E.: Fast counting of triangles in large real networks without counting: algorithms and laws. In: ICDM, pp. 608\u2013617 (2008)","DOI":"10.1109\/ICDM.2008.72"},{"key":"624_CR45","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: KDD, pp. 837\u2013846 (2009)","DOI":"10.1145\/1557019.1557111"},{"key":"624_CR46","doi-asserted-by":"crossref","unstructured":"Turk, A., T\u00fcrkoglu, D.: Revisiting wedge sampling for triangle counting. In: TheWebConf, pp. 1875\u20131885 (2019)","DOI":"10.1145\/3308558.3313534"},{"key":"624_CR47","doi-asserted-by":"crossref","unstructured":"T\u00fcrkoglu, D., Turk, A.: Edge-based wedge sampling to estimate triangle counts in very large graphs. In: ICDM, pp. 455\u2013464 (2017)","DOI":"10.1109\/ICDM.2017.55"},{"key":"624_CR48","doi-asserted-by":"crossref","unstructured":"Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in facebook. In: WOSN, pp. 37\u201342 (2009)","DOI":"10.1145\/1592665.1592675"},{"issue":"1","key":"624_CR49","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw. 11(1), 37\u201357 (1985)","journal-title":"ACM Trans. Math. Softw."},{"issue":"2","key":"624_CR50","first-page":"162","volume":"11","author":"P Wang","year":"2017","unstructured":"Wang, P., Qi, Y., Sun, Y., Zhang, X., Tao, J., Guan, X.: Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. PVLDB 11(2), 162\u2013175 (2017)","journal-title":"PVLDB"},{"key":"624_CR51","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis: Methods and Applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications, vol. 8. Cambridge University Press, Cambridge (1994)"},{"issue":"6684","key":"624_CR52","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of small-worldnetworks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00624-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-020-00624-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00624-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T16:41:22Z","timestamp":1667752882000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-020-00624-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["624"],"URL":"https:\/\/doi.org\/10.1007\/s00778-020-00624-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"11 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}