{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T15:07:23Z","timestamp":1777475243960,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>Many dynamic applications are built upon large network infrastructures, such as social networks, communication networks, biological networks and the Web. Such applications create data that can be naturally modeled as<jats:italic>graph streams<\/jats:italic>, in which edges of the underlying graph are received and updated sequentially in a form of a stream. It is often necessary and important to summarize the behavior of graph streams in order to enable effective query processing. However, the sheer size and dynamic nature of graph streams present an enormous challenge to existing graph management techniques. In this paper, we propose a new graph sketch method, gSketch, which combines well studied synopses for traditional data streams with a sketch partitioning technique, to estimate and optimize the responses to basic queries on graph streams. We consider two different scenarios for query estimation: (1) A graph stream sample is available; (2) Both a graph stream sample and a query workload sample are available. Algorithms for different scenarios are designed respectively by partitioning a global sketch to a group of localized sketches in order to optimize the query estimation accuracy. We perform extensive experimental studies on both real and synthetic data sets and demonstrate the power and robustness of gSketch in comparison with the state-of-the-art global sketch method.<\/jats:p>","DOI":"10.14778\/2078331.2078335","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"193-204","source":"Crossref","is-referenced-by-count":65,"title":["gSketch"],"prefix":"10.14778","volume":"5","author":[{"given":"Peixiang","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charu C.","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Res. Ctr., Hawthorne, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Wang","sequence":"additional","affiliation":[{"name":"HP Labs, China, Beijing, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Data Streams: Models and Algorithms","author":"Aggarwal C. C.","year":"2006","unstructured":"C. C. Aggarwal . Data Streams: Models and Algorithms . Springer, Inc. , 2006 . C. C. Aggarwal. Data Streams: Models and Algorithms. Springer, Inc., 2006."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8462-3","volume-title":"Social Network Data Analytics","author":"Aggarwal C. C.","year":"2011","unstructured":"C. C. Aggarwal . Social Network Data Analytics . Springer Inc ., 2011 . C. C. Aggarwal. Social Network Data Analytics. Springer Inc., 2011."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"975","DOI":"10.14778\/1920841.1920964","article-title":"On dense pattern mining in graph streams","volume":"3","author":"Aggarwal C. C.","year":"2010","unstructured":"C. C. Aggarwal , Y. Li , P. S. Yu , and R. Jin . On dense pattern mining in graph streams . Proc. VLDB Endow. , 3 : 975 -- 984 , 2010 . C. C. Aggarwal, Y. Li, P. S. Yu, and R. Jin. On dense pattern mining in graph streams. Proc. VLDB Endow., 3:975--984, 2010.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-6045-0","volume-title":"Managing and Mining Graph Data","author":"Aggarwal C. C.","year":"2010","unstructured":"C. C. Aggarwal and H. Wang . Managing and Mining Graph Data . Springer Inc ., 2010 . C. C. Aggarwal and H. Wang. Managing and Mining Graph Data. Springer Inc., 2010."},{"key":"e_1_2_1_5_1","first-page":"20","volume-title":"STOC","author":"Alon N.","year":"1996","unstructured":"N. Alon , Y. Matias , and M. Szegedy . The space complexity of approximating the frequency moments . In STOC , pages 20 -- 29 , Philadelphia, PA, USA , 1996 . 10.1145\/237814.237823 N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. In STOC, pages 20--29, Philadelphia, PA, USA, 1996. 10.1145\/237814.237823"},{"key":"e_1_2_1_6_1","first-page":"623","volume-title":"SODA","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , R. Kumar , and D. Sivakumar . Reductions in streaming algorithms, with an application to counting triangles in graphs . In SODA , pages 623 -- 632 , San Francisco, CA, USA , 2002 . Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623--632, San Francisco, CA, USA, 2002."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/988672.988752","volume-title":"WWW","author":"Boldi P.","year":"2004","unstructured":"P. Boldi and S. Vigna . The webgraph framework I: compression techniques . In WWW , pages 595 -- 602 , New York, NY, USA , 2004 . 10.1145\/988672.988752 P. Boldi and S. Vigna. The webgraph framework I: compression techniques. In WWW, pages 595--602, New York, NY, USA, 2004. 10.1145\/988672.988752"},{"key":"e_1_2_1_8_1","first-page":"253","volume-title":"PODS","author":"Buriol L. S.","year":"2006","unstructured":"L. S. Buriol , G. Frahling , S. Leonardi , A. Marchetti-Spaccamela , and C. Sohler . Counting triangles in data streams . In PODS , pages 253 -- 262 , Chicago, IL, USA , 2006 . 10.1145\/1142351.1142388 L. S. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela, and C. Sohler. Counting triangles in data streams. In PODS, pages 253--262, Chicago, IL, USA, 2006. 10.1145\/1142351.1142388"},{"key":"e_1_2_1_9_1","first-page":"442","volume-title":"SDM","author":"Chakrabarti D.","year":"2004","unstructured":"D. Chakrabarti , Y. Zhan , and C. Faloutsos . R-MAT: A recursive model for graph mining . In SDM , pages 442 -- 446 , Lake Buena Visa, FL, USA , 2004 . D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In SDM, pages 442--446, Lake Buena Visa, FL, USA, 2004."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/1557019.1557049","volume-title":"KDD","author":"Chierichetti F.","year":"2009","unstructured":"F. Chierichetti , R. Kumar , S. Lattanzi , M. Mitzenmacher , A. Panconesi , and P. Raghavan . On compressing social networks . In KDD , pages 219 -- 228 , Paris, France , 2009 . 10.1145\/1557019.1557049 F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan. On compressing social networks. In KDD, pages 219--228, Paris, France, 2009. 10.1145\/1557019.1557049"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.14778\/1453856.1453884","article-title":"Tighter estimation using bottom k sketches","volume":"1","author":"Cohen E.","year":"2008","unstructured":"E. Cohen and H. Kaplan . Tighter estimation using bottom k sketches . Proc. VLDB Endow. , 1 : 213 -- 224 , 2008 . E. Cohen and H. Kaplan. Tighter estimation using bottom k sketches. Proc. VLDB Endow., 1:213--224, 2008.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","DOI":"10.1002\/0470073047","volume-title":"Mining Graph Data","author":"Cook D. J.","year":"2006","unstructured":"D. J. Cook and L. B. Holder . Mining Graph Data . John Wiley & Sons , 2006 . D. J. Cook and L. B. Holder. Mining Graph Data. John Wiley & Sons, 2006."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"1530","DOI":"10.14778\/1454159.1454225","article-title":"Finding frequent items in data streams","volume":"1","author":"Cormode G.","year":"2008","unstructured":"G. Cormode and M. Hadjieleftheriou . Finding frequent items in data streams . Proc. VLDB Endow. , 1 : 1530 -- 1541 , 2008 . G. Cormode and M. Hadjieleftheriou. Finding frequent items in data streams. Proc. VLDB Endow., 1:1530--1541, 2008.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_15_1","first-page":"271","volume-title":"PODS","author":"Cormode G.","year":"2005","unstructured":"G. Cormode and S. Muthukrishnan . Space efficient mining of multigraph streams . In PODS , pages 271 -- 282 , Baltimore, Maryland, USA , 2005 . 10.1145\/1065167.1065201 G. Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In PODS, pages 271--282, Baltimore, Maryland, USA, 2005. 10.1145\/1065167.1065201"},{"key":"e_1_2_1_16_1","first-page":"69","volume-title":"PODS","author":"Sarma A. Das","year":"2008","unstructured":"A. Das Sarma , S. Gollapudi , and R. Panigrahy . Estimating pagerank on graph streams . In PODS , pages 69 -- 78 , Vancouver, BC, Canada , 2008 . 10.1145\/1376916.1376928 A. Das Sarma, S. Gollapudi, and R. Panigrahy. Estimating pagerank on graph streams. In PODS, pages 69--78, Vancouver, BC, Canada, 2008. 10.1145\/1376916.1376928"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/564691.564699","volume-title":"SIGMOD","author":"Dobra A.","year":"2002","unstructured":"A. Dobra , M. Garofalakis , J. Gehrke , and R. Rastogi . Processing complex aggregate queries over data streams . In SIGMOD , pages 61 -- 72 , Madison, WI, USA , 2002 . 10.1145\/564691.564699 A. Dobra, M. Garofalakis, J. Gehrke, and R. Rastogi. Processing complex aggregate queries over data streams. In SIGMOD, pages 61--72, Madison, WI, USA, 2002. 10.1145\/564691.564699"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_20_1","first-page":"163","volume-title":"ISAAC","author":"Ganguly S.","year":"2006","unstructured":"S. Ganguly and B. Saha . On estimating path aggregates over streaming graphs . In ISAAC , pages 163 -- 172 , Kolkata, India , 2006 . 10.1007\/11940128_18 S. Ganguly and B. Saha. On estimating path aggregates over streaming graphs. In ISAAC, pages 163--172, Kolkata, India, 2006. 10.1007\/11940128_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1090\/dimacs\/050\/05","volume-title":"Computing on data streams. External memory algorithms","author":"Henzinger M. R.","year":"1999","unstructured":"M. R. Henzinger , P. Raghavan , and S. Rajagopalan . Computing on data streams. External memory algorithms , pages 107 -- 118 , 1999 . M. R. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. External memory algorithms, pages 107--118, 1999."},{"key":"e_1_2_1_22_1","volume-title":"Speech and Language Processing","author":"Jurafsky D.","year":"2008","unstructured":"D. Jurafsky and J. H. Martin . Speech and Language Processing . Prentice Hall , 2008 . D. Jurafsky and J. H. Martin. Speech and Language Processing. Prentice Hall, 2008."},{"key":"e_1_2_1_23_1","first-page":"346","volume-title":"VLDB","author":"Manku G. S.","year":"2002","unstructured":"G. S. Manku and R. Motwani . Approximate frequency counts over data streams . In VLDB , pages 346 -- 357 , Hong Kong, China , 2002 . G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In VLDB, pages 346--357, Hong Kong, China, 2002."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"1271","DOI":"10.1007\/978-0-387-39940-9_184","volume-title":"Graph mining on streams. Encyclopedia of Database Systems","author":"McGregor A.","year":"2009","unstructured":"A. McGregor . Graph mining on streams. Encyclopedia of Database Systems , pages 1271 -- 1275 , 2009 . A. McGregor. Graph mining on streams. Encyclopedia of Database Systems, pages 1271--1275, 2009."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and combinatorial optimization","author":"Nemhauser G. L.","year":"1988","unstructured":"G. L. Nemhauser and L. A. Wolsey . Integer and combinatorial optimization . Wiley-Interscience , 1988 . G. L. Nemhauser and L. A. Wolsey. Integer and combinatorial optimization. Wiley-Interscience, 1988."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Network: An Introduction","author":"Newman M. E. J.","year":"2010","unstructured":"M. E. J. Newman . Network: An Introduction . Oxford University Press , 2010 . M. E. J. Newman. Network: An Introduction. Oxford University Press, 2010."},{"key":"e_1_2_1_28_1","first-page":"405","volume-title":"ICDE","author":"Raghavan S.","year":"2003","unstructured":"S. Raghavan and H. Garcia-Molina . Representing web graphs . In ICDE , pages 405 -- 416 , Atlanta, GA, USA , 2003 . S. Raghavan and H. Garcia-Molina. Representing web graphs. In ICDE, pages 405--416, Atlanta, GA, USA, 2003."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2078331.2078335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T23:59:22Z","timestamp":1716854362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2078331.2078335"}},"subtitle":["on query estimation in graph streams"],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.14778\/2078331.2078335"],"URL":"https:\/\/doi.org\/10.14778\/2078331.2078335","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}