{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T06:09:41Z","timestamp":1764828581340,"version":"3.41.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T00:00:00Z","timestamp":1495497600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s13278-017-0443-4","type":"journal-article","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T06:53:48Z","timestamp":1495522428000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Toward query-friendly compression of rapid graph streams"],"prefix":"10.1007","volume":"7","author":[{"given":"Arijit","family":"Khan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charu","family":"Aggarwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,23]]},"reference":[{"key":"443_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal C (ed) (2007) Data streams\u2014models and algorithms, vol 31 of advances in database systems. Springer: Berlin","DOI":"10.1007\/978-0-387-47534-9"},{"key":"443_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal C (2011) On classification of graph streams. In: SDM","DOI":"10.1137\/1.9781611972818.56"},{"key":"443_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal C, Han J, Wang J, Yu P (2003) A framework for clustering evolving data streams. In: VLDB","DOI":"10.1016\/B978-012722442-8\/50016-1"},{"key":"443_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal C, Li Y, Yu PS, Jin R (2010) On dense pattern mining in graph streams. In: VLDB","DOI":"10.14778\/1920841.1920964"},{"key":"443_CR5","doi-asserted-by":"crossref","unstructured":"Aggarwal C, Zhao Y, Yu PS (2010) On clustering graph streams. In: SDM","DOI":"10.1137\/1.9781611972801.42"},{"key":"443_CR6","doi-asserted-by":"crossref","unstructured":"Ahn KJ, Guha S, McGregor A (2012) Analyzing graph structure via linear measurements. In: SODA","DOI":"10.1137\/1.9781611973099.40"},{"key":"443_CR7","doi-asserted-by":"crossref","unstructured":"Ahn KJ, Guha S, McGregor A (2012) Graph sketches: sparsification, spanners, and subgraphs. In: PODS","DOI":"10.1145\/2213556.2213560"},{"key":"443_CR8","doi-asserted-by":"crossref","unstructured":"Aho AV, Garey MR, Ullman JD (1972) The transitive reduction of a directed graph. In: SICOMP 1(2)","DOI":"10.1137\/0201008"},{"key":"443_CR9","doi-asserted-by":"crossref","unstructured":"Anicic D, Fodor P, Rudolph S, Stojanovic N (2011) EP-SPARQL: a unified language for event processing and stream reasoning. In: WWW","DOI":"10.1145\/1963405.1963495"},{"key":"443_CR10","unstructured":"Yossef ZB, Kumar R, Sivakumar D (2002) Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA"},{"key":"443_CR11","doi-asserted-by":"crossref","unstructured":"Bandyopadhyay B, Fuhry D, Chakrabarti A, Parthasarathy S (2016) Topological graph sketching for incremental and scalable analytics. In: CIKM, pp 1231\u20131240","DOI":"10.1145\/2983323.2983735"},{"key":"443_CR12","doi-asserted-by":"crossref","unstructured":"Boldi P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: WWW","DOI":"10.1145\/1963405.1963488"},{"key":"443_CR13","doi-asserted-by":"crossref","unstructured":"Buneman P, Grohe M, Koch C (2003) Path queries on compressed XML. In: VLDB","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"key":"443_CR14","doi-asserted-by":"crossref","unstructured":"Charikar M, Chen K, Farach-Colton M (2002) Finding frequent items in data streams. In: ICALP","DOI":"10.1007\/3-540-45465-9_59"},{"key":"443_CR15","doi-asserted-by":"crossref","unstructured":"Chierichetti F, Kumar R, Lattanzi S, Mitzenmacher M, Panconesi A, Raghavan P (2009) On compressing social networks. In: KDD","DOI":"10.1145\/1557019.1557049"},{"key":"443_CR16","doi-asserted-by":"crossref","unstructured":"Choudhury S, Holder L, Chin G, Ray A, Beus S, Feo J (2013) StreamWorks: a system for dynamic graph search. In: SIGMOD","DOI":"10.1145\/2463676.2463697"},{"key":"443_CR17","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Section 31.2: greatest common divisor. In: Introduction to algorithms, second edition, pp 859\u2013861. MIT Press, McGraw-Hill"},{"issue":"1\u20133","key":"443_CR18","first-page":"1","volume":"4","author":"G Cormode","year":"2012","unstructured":"Cormode G, Garofalakis M, Haas PJ, Jermaine C (2012) Synopses for massive data: samples, histograms, wavelets, sketches. Found Trends Databases 4(1\u20133):1\u2013294","journal-title":"Found Trends Databases"},{"key":"443_CR19","doi-asserted-by":"crossref","unstructured":"Cormode G, Hadjieleftheriou M (2008) Finding frequent items in data streams. In: VLDB","DOI":"10.14778\/1454159.1454225"},{"key":"443_CR20","doi-asserted-by":"crossref","unstructured":"Cormode G, Johnson T, Korn F, Muthukrishnan S, Spatscheck O, Srivastava D (2004) Holistic UDAFs at streaming speeds. In: SIGMOD","DOI":"10.1145\/1007568.1007575"},{"key":"443_CR21","doi-asserted-by":"crossref","unstructured":"Cormode G, Muthukrishnan S (2005) An improved data-stream summary: the count-min sketch and its applications. J Algorithms 55(1)","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"443_CR22","doi-asserted-by":"crossref","unstructured":"Cormode G, Muthukrishnan S (2005) Space efficient mining of multigraph streams. In: PODS","DOI":"10.1145\/1065167.1065201"},{"key":"443_CR23","doi-asserted-by":"crossref","unstructured":"Fan W, Li J, Wang X, Wu Y (2012) Query preserving graph compression. In: SIGMOD","DOI":"10.1145\/2213836.2213855"},{"key":"443_CR24","doi-asserted-by":"crossref","unstructured":"Feigenbaum J, Kannan S, McGregor A, Suri S, Zhang J (2005) Graph distances in the data stream model. SIAM J Comput 38(5)","DOI":"10.1137\/070683155"},{"issue":"2\u20133","key":"443_CR25","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum J, Kannan S, McGregor A, Suri S, Zhang J (2005) On graph problems in a semi-streaming model. Theor Comput Sci 348(2\u20133):207\u2013216","journal-title":"Theor Comput Sci"},{"key":"443_CR26","doi-asserted-by":"crossref","unstructured":"Jin R, Liu L, Ding B, Wang H (2011) Distance-constraint reachability computation in uncertain graphs. In: VLDB","DOI":"10.14778\/2002938.2002941"},{"key":"443_CR27","doi-asserted-by":"crossref","unstructured":"Khan A, Aggarwal C (2016) Query-friendly compression of graph streams. In: ASONAM","DOI":"10.1109\/ASONAM.2016.7752224"},{"key":"443_CR28","doi-asserted-by":"crossref","unstructured":"LeFevre K, Terzi E (2010) GraSS: graph structure summarization. In: SDM","DOI":"10.1137\/1.9781611972801.40"},{"issue":"4","key":"443_CR29","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/j.datak.2008.11.001","volume":"68","author":"N Manerikar","year":"2009","unstructured":"Manerikar N, Palpanas T (2009) Frequent items in streaming data: an experimental evaluation of the state-of-the-art. Data Knowl Eng 68(4):415\u2013430","journal-title":"Data Knowl Eng"},{"key":"443_CR30","doi-asserted-by":"crossref","unstructured":"McGregor A (2014) Graph stream algorithms: a survey. SIGMOD Rec 43(1)","DOI":"10.1145\/2627692.2627694"},{"key":"443_CR31","doi-asserted-by":"crossref","unstructured":"Metwally A, Agrawal D, Abbadi AE (2005) Efficient computation of frequent and top-k elements in data streams. In: ICDT","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"443_CR32","volume-title":"Stream querying and reasoning on social data: encyclopedia of social network analysis and mining","author":"J Mondal","year":"2014","unstructured":"Mondal J, Deshpande A (2014) Stream querying and reasoning on social data: encyclopedia of social network analysis and mining. Springer, Berlin"},{"key":"443_CR33","doi-asserted-by":"crossref","unstructured":"Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In: SIGMOD","DOI":"10.1145\/1376616.1376661"},{"key":"443_CR34","unstructured":"Pan S, Zhu X, Zhang C, Yu P (2013) Graph stream classification using labeled and unlabeled graphs. In: ICDE"},{"key":"443_CR35","doi-asserted-by":"crossref","unstructured":"Polyzotis N, Garofalakis M (2006) Xsketch synopses for XML data graphs. TODS 3(31)","DOI":"10.1145\/1166074.1166082"},{"key":"443_CR36","unstructured":"Qun C, Lin A, Ong KW (2003) D(k)-index: an adaptive structural summary for graph structured data. In: SIGMOD"},{"key":"443_CR37","unstructured":"Raghavan S, Garcia-Molina H (2003) Representing web graphs. In: ICDE"},{"issue":"2","key":"443_CR38","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/s10618-016-0468-8","volume":"31","author":"M Riondato","year":"2017","unstructured":"Riondato M, Garc\u00eda-Soriano D, Bonchi F (2017) Graph summarization with quality guarantees. Data Min Knowl Discov 31(2):314\u2013349","journal-title":"Data Min Knowl Discov"},{"issue":"4","key":"443_CR39","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1109\/TNET.2013.2272604","volume":"22","author":"O Rottenstreich","year":"2014","unstructured":"Rottenstreich O, Kanizo Y, Keslassy I (2014) The variable-increment counting bloom filter. IEEE\/ACM Trans Netw 22(4):1092\u20131105","journal-title":"IEEE\/ACM Trans Netw"},{"key":"443_CR40","doi-asserted-by":"crossref","unstructured":"Roy P, Khan A, Alonso G (2016) Augmented sketch: faster and more accurate stream processing. In: SIGMOD","DOI":"10.1145\/2882903.2882948"},{"key":"443_CR41","unstructured":"Sarma AD, Gollapudi S, Panigrahy R (2008) Estimating pagerank on graph streams. In: PODS"},{"issue":"5","key":"443_CR42","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1109\/TNET.2007.896150","volume":"15","author":"R Schweller","year":"2007","unstructured":"Schweller R, Li Z, Chen Y, Gao Y, Gupta A, Zhang Y, Dinda PA, Kao M-Y, Memik G (2007) Reversible sketches: enabling monitoring and analysis over high-speed data streams. IEEE\/ACM Trans Netw 15(5):1059\u20131072","journal-title":"IEEE\/ACM Trans Netw"},{"key":"443_CR43","doi-asserted-by":"crossref","unstructured":"Shah N, Koutra D, Zou T, Gallagher B, Faloutsos C (2015) TimeCrunch: interpretable dynamic graph summarization. In: KDD","DOI":"10.1145\/2783258.2783321"},{"key":"443_CR44","doi-asserted-by":"crossref","unstructured":"Stanton I, Kliot G (2012) Streaming graph partitioning for large distributed graphs. In: KDD","DOI":"10.1145\/2339530.2339722"},{"key":"443_CR45","doi-asserted-by":"crossref","unstructured":"Suel T, Yuan J (2001) Compressing the graph structure of the web. In: Data compression conference","DOI":"10.1109\/DCC.2001.917152"},{"key":"443_CR46","doi-asserted-by":"crossref","unstructured":"Tang N, Chen Q, Mitra P (2016) Graph stream summarization: from big bang to big crunch. In: SIGMOD","DOI":"10.1145\/2882903.2915223"},{"key":"443_CR47","doi-asserted-by":"crossref","unstructured":"Tsalouchidou I, Morales GDF, Bonchi F, Baeza-Yates RA (2016) Scalable dynamic graph summarization. In: IEEE big data","DOI":"10.1109\/BigData.2016.7840704"},{"issue":"3","key":"443_CR48","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3):410\u2013421","journal-title":"SIAM J Comput"},{"key":"443_CR49","doi-asserted-by":"crossref","unstructured":"Zhao P, Aggarwal C, Wang M (2012) gSketch: on query estimation in graph streams. In: VLDB","DOI":"10.14778\/2078331.2078335"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-017-0443-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-017-0443-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-017-0443-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:11:25Z","timestamp":1750273885000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-017-0443-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,23]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["443"],"URL":"https:\/\/doi.org\/10.1007\/s13278-017-0443-4","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"type":"print","value":"1869-5450"},{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2017,5,23]]},"article-number":"23"}}