{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,18]],"date-time":"2025-09-18T14:32:00Z","timestamp":1758205920519,"version":"3.44.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972446"],"award-info":[{"award-number":["61972446"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Graph stream is the model used to represent evolving graph data over time, which can be represented as a sequence of edge streams containing temporal information. To effectively manage an ultra large scale graph stream, existing designs usually use summarization structures based on compressed matrices to support approximate storage and querying of graph streams. However, the state-of-the-art structures are based on limited-sized compressed matrix. When dealing with dynamical graph stream data, they either use an extra adjacency list outside the compressed matrix to store left-over edges whose expected buckets in the matrix have been occupied by other previously inserted edges, or allocate new building blocks of compressed matrices to provide more space capacity. Such designs suffer from linear lookup time caused by the adjacency list or long system blocking time caused by data movement during structure scaling. Moreover, in graph stream applications with dynamically growing data sizes, recent data commonly carries greater significance and value. Existing designs fail to store the time information of items of graph streams in a space efficient way and leave recent data management over graph streams an unsolved problem. To address the dynamically expanding graph stream with the ability to accentuate the importance of recent data, in this work, we propose Sliding-ITeM, a novel adaptive-size graph stream summarization structure with a sliding window model. Two factors contribute to the efficiency of Sliding-ITeM. First, Sliding-ITeM proposes a novel <jats:italic>fingerprint suffix index tree<\/jats:italic> (FSIT) structure to efficiently manage the items assigned to a same bucket of a compressed matrix in a fine-grained and scalable way. It thus achieves time and space efficiency for graph stream management as well as avoiding costly blocking time for structure extending. Second, Sliding-ITeM divides continuous time into discrete time slices and stores items belong to different time slices in separate ITeM compressed matrices. Sliding-ITeM organizes the compressed matrices into a chain style chronologically and achieves efficient obtaining of value from recent data as well as removal of expired data following a sliding-window model. We conduct comprehensive experiments over large-scale graph stream data collected from real world systems to evaluate the performance of Sliding-ITeM. Experimental results show that it significantly reduces the operation latency by more than 67% in sliding window queries compared to state-of-the-art designs, while greatly reducing the system blocking duration by three orders of magnitude.<\/jats:p>","DOI":"10.1007\/s41019-024-00279-2","type":"journal-article","created":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T06:53:04Z","timestamp":1744786384000},"page":"428-454","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sliding-ITeM: An Adaptive-Size Graph Stream Summarization Structure Based on Sliding Windows"],"prefix":"10.1007","volume":"10","author":[{"given":"Yacheng","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0164-6853","authenticated-orcid":false,"given":"Hanhua","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,16]]},"reference":[{"key":"279_CR1","doi-asserted-by":"crossref","unstructured":"Tang N, Chen Q, Mitra P (2016) Graph stream summarization: From big bang to big crunch. In: Proceedings of the international conference on management of data (SIGMOD), San Francisco, California, USA, June 26 - July 01, pp. 1481\u20131496","DOI":"10.1145\/2882903.2915223"},{"key":"279_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2021.108403","volume":"198","author":"C Hou","year":"2021","unstructured":"Hou C, Hou B, Zhou T, Cai Z (2021) Dmatrix: toward fast and accurate queries in graph stream. Comput Netw 198:108403","journal-title":"Comput Netw"},{"key":"279_CR3","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.ins.2019.07.019","volume":"503","author":"C Song","year":"2019","unstructured":"Song C, Ge T, Ge Y, Zhang H, Yuan X (2019) Labeled graph sketches: keeping up with real-time graph streams. Inf Sci 503:469\u2013492","journal-title":"Inf Sci"},{"key":"279_CR4","doi-asserted-by":"crossref","unstructured":"Gou X, Zou L, Zhao C, Yang T (2019) Fast and accurate graph stream summarization. In: Proceedings of the 35th international conference on data engineering (ICDE), Macao, China, April 8-11, pp. 1118\u20131129","DOI":"10.1109\/ICDE.2019.00103"},{"key":"279_CR5","doi-asserted-by":"crossref","unstructured":"Khan A, Aggarwal C (2016) Query-friendly compression of graph streams. In: Proceedings of the international conference on advances in social networks analysis and mining (ASONAM), CA, USA, August 18-21, pp. 130\u2013137","DOI":"10.1109\/ASONAM.2016.7752224"},{"key":"279_CR6","doi-asserted-by":"crossref","unstructured":"Pacaci A, Bonifati A, \u00d6zsu MT (2022) Evaluating complex queries on streaming graphs. In: Proceedings of the 38th international conference on data engineering (ICDE), Kuala Lumpur, Malaysia, May 9-12, pp. 272\u2013285","DOI":"10.1109\/ICDE53745.2022.00025"},{"key":"279_CR7","doi-asserted-by":"crossref","unstructured":"Hassan MS, Ribeiro B, Aref WG (2018) Sbg-sketch: A self-balanced sketch for labeled-graph stream summarization. In: Proceedings of the 30th international conference on scientific and statistical database management (SSDBM), Bozen-Bolzano, Italy, July 09-11, pp. 1\u201312","DOI":"10.1145\/3221269.3223030"},{"key":"279_CR8","doi-asserted-by":"crossref","unstructured":"Li Y, Zou L, \u00d6zsu MT, Zhao D (2019) Time constrained continuous subgraph search over streaming graphs. In: Proceedings of the 35th international conference on data engineering (ICDE), Macao, China, April 8-11, pp. 1082\u20131093","DOI":"10.1109\/ICDE.2019.00100"},{"key":"279_CR9","doi-asserted-by":"crossref","unstructured":"Chen M, Zhou R, Chen H, Jin H (2022) Scube: Efficient summarization for skewed graph streams. In: Proceedings of the 42nd international conference on distributed computing systems (ICDCS), Bologna, Italy, July 10-13, pp. 100\u2013110","DOI":"10.1109\/ICDCS54860.2022.00019"},{"key":"279_CR10","doi-asserted-by":"crossref","unstructured":"Chen M, Zhou R, Chen H, Xiao J, Jin H, Li B (2022) Horae: A graph stream summarization structure for efficient temporal range query. In: Proceedings of the 38th international conference on data engineering (ICDE), Kuala Lumpur, Malaysia, May 9-12, pp. 2792\u20132804","DOI":"10.1109\/ICDE53745.2022.00254"},{"issue":"6","key":"279_CR11","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.14778\/3583140.3583154","volume":"16","author":"Z Jiang","year":"2023","unstructured":"Jiang Z, Chen H, Jin H (2023) Auxo: a scalable and efficient graph stream summarization structure. Proceedings of the VLDB Endowment 16(6):1386\u20131398","journal-title":"Proceedings of the VLDB Endowment"},{"key":"279_CR12","doi-asserted-by":"crossref","unstructured":"Gou X, He L, Zhang Y, Wang K, Liu X, Yang T, Wang Y, Cui B (2020) Sliding sketches: a framework using time zones for data stream processing in sliding windows. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), San Diego, CA, USA, August 22-27, pp. 1015\u20131025","DOI":"10.1145\/3394486.3403144"},{"key":"279_CR13","doi-asserted-by":"crossref","unstructured":"Vombatkere K, Mousavi S, Zannettou S, Roesner F, Gummadi KP (2024) Tiktok and the art of personalization: investigating exploration and exploitation on social media feeds. In: Proceedings of the ACM on web conference 2024, Singapore, Singapore, May 13 - 17, pp. 3789\u20133797","DOI":"10.1145\/3589334.3645600"},{"key":"279_CR14","doi-asserted-by":"crossref","unstructured":"Ftaimi S, Mazri T (2021) Data stream clustering for detecting misbehavior in an intelligent transportation system. In: Proceedings of the 4th international conference on networking, information systems & security, KENITRA, AA, Morocco, April 1 - 2, pp. 1\u20138","DOI":"10.1145\/3454127.3456574"},{"key":"279_CR15","doi-asserted-by":"crossref","unstructured":"Huang X, Vitak J, Tausczik Y (2020) \u201dyou don\u2019t have to know my past\u201d: how wechat moments users manage their evolving self-presentation. In: Proceedings of the 2020 CHI conference on human factors in computing systems, Honolulu, Hawai\u2019i, USA, April 25-30","DOI":"10.1145\/3313831.3376595"},{"key":"279_CR16","doi-asserted-by":"crossref","unstructured":"Papapetrou O, Garofalakis M, Deligiannakis A (2012) Sketch-based querying of distributed sliding-window data streams. arXiv preprint arXiv:1207.0139","DOI":"10.14778\/2336664.2336672"},{"key":"279_CR17","doi-asserted-by":"crossref","unstructured":"Shrivastava A, Konig AC, Bilenko M (2016) Time adaptive sketches (ada-sketches) for summarizing data streams. In: Proceedings of the international conference on management of data (SIGMOD), San Francisco, CA, USA, June 26 - July 01, pp. 1417\u20131432","DOI":"10.1145\/2882903.2882946"},{"issue":"1","key":"279_CR18","first-page":"1","volume":"1","author":"R Yang","year":"2023","unstructured":"Yang R, Zhang Z, Zheng W, Yu JX (2023) Fast continuous subgraph matching over streaming graphs via backtracking reduction. Proceed ACM Manag Data 1(1):1\u201326","journal-title":"Proceed ACM Manag Data"},{"key":"279_CR19","doi-asserted-by":"crossref","unstructured":"Wang X, Zhang Q, Guo D, Zhao X (2023) Mining top-k frequent patterns over streaming graphs. In: Proceedings of the 28th international conference on database systems for advanced applications (DASFAA), Tianjin, China, April 17\u201320, pp. 199\u2013216","DOI":"10.1007\/978-3-031-30675-4_14"},{"key":"279_CR20","doi-asserted-by":"crossref","unstructured":"Kim K, Seo I, Han W-S, Lee J-H, Hong S, Chafi H, Shin H, Jeong G (2018) Turboflux: a fast continuous subgraph matching system for streaming graph data. In: Proceedings of the international conference on management of data (SIGMOD), Houston, TX, USA, June 10-15, pp. 411\u2013426","DOI":"10.1145\/3183713.3196917"},{"issue":"2","key":"279_CR21","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 Y, Zhang X, Tao J, Guan X (2017) Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. Proceed VLDB Endowment 11(2):162\u2013175","journal-title":"Proceed VLDB Endowment"},{"issue":"2","key":"279_CR22","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 (2020) Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans Knowl Discovery Data (TKDD) 14(2):1\u201339","journal-title":"ACM Trans Knowl Discovery Data (TKDD)"},{"key":"279_CR23","doi-asserted-by":"crossref","unstructured":"Xiao Y, Huang H, Zhao F, Jin H (2019) Tplp: Two-phase selection link prediction for vertex in graph streams. In: Proceedings of the Pacific-Asia conference on knowledge discovery and data mining (PAKDD), Macao, China, April 14-17, pp. 514\u2013525","DOI":"10.1007\/978-3-030-16145-3_40"},{"key":"279_CR24","doi-asserted-by":"crossref","unstructured":"Zhao P, Aggarwal C, He G (2016) Link prediction in graph streams. In: Proceedings of the 32nd international conference on data engineering (ICDE), Helsinki, Finland, May 16-20, pp. 553\u2013564","DOI":"10.1109\/ICDE.2016.7498270"},{"issue":"2","key":"279_CR25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00778-022-00750-4","volume":"32","author":"TT Nguyen","year":"2023","unstructured":"Nguyen TT, Huynh TT, Yin H, Weidlich M, Nguyen TT, Mai TS, Nguyen QVH (2023) Detecting rumours with latency guarantees using massive streaming data. VLDB J 32(2):369\u2013387","journal-title":"VLDB J"},{"key":"279_CR26","doi-asserted-by":"crossref","unstructured":"Namaki MH, Sasani K, Wu Y, Ge T (2017) Beams: bounded event detection in graph streams. In: Proceedings of the 33rd international conference on data engineering (ICDE), San Diego, CA, USA, April 19-22, pp. 1387\u20131388","DOI":"10.1109\/ICDE.2017.189"},{"key":"279_CR27","doi-asserted-by":"crossref","unstructured":"Bhatia S, Wadhwa M, Kawaguchi K, Shah N, Yu PS, Hooi B (2023) Sketch-based anomaly detection in streaming graphs. In: Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining (KDD), Long Beach, CA, USA, August 6-10, pp. 93\u2013104","DOI":"10.1145\/3580305.3599504"},{"key":"279_CR28","doi-asserted-by":"crossref","unstructured":"Pacaci A, Bonifati A, \u00d6zsu MT (2020) Regular path query evaluation on streaming graphs. In: Proceedings of the international conference on management of data (SIGMOD), online conference, June 14-19, pp. 1415\u20131430","DOI":"10.1145\/3318464.3389733"},{"key":"279_CR29","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1007\/s00778-019-00572-x","volume":"28","author":"T Zhang","year":"2019","unstructured":"Zhang T, Gao Y, Chen L, Guo W, Pu S, Zheng B, Jensen CS (2019) Efficient distributed reachability querying of massive temporal graphs. VLDB J 28:871\u2013896","journal-title":"VLDB J"},{"key":"279_CR30","doi-asserted-by":"crossref","unstructured":"Zhu AD, Lin W, Wang S, Xiao X (2014) Reachability queries on large dynamic graphs: a total order approach. In: Proceedings of the international conference on management of data (SIGMOD), Snowbird, UT, USA, June 22- 27, pp. 1323\u20131334","DOI":"10.1145\/2588555.2612181"},{"key":"279_CR31","doi-asserted-by":"crossref","unstructured":"Chen X, Wang K, Lin X, Zhang W, Qin L, Zhang Y (2021) Efficiently answering reachability and path queries on temporal bipartite graphs. Proceedings of the VLDB Endowment","DOI":"10.14778\/3467861.3467873"},{"issue":"1","key":"279_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-021-3370-4","volume":"66","author":"J Zhang","year":"2023","unstructured":"Zhang J, Chen H, Yu D, Pei Y, Deng Y (2023) Cluster-preserving sampling algorithm for large-scale graphs. SCIENCE CHINA Inf Sci 66(1):112103","journal-title":"SCIENCE CHINA Inf Sci"},{"issue":"4","key":"279_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3495011","volume":"16","author":"A Sheshbolouki","year":"2022","unstructured":"Sheshbolouki A, \u00d6zsu MT (2022) sgrapp: butterfly approximation in streaming graphs. ACM Trans Knowl Discovery Data (TKDD) 16(4):1\u201343","journal-title":"ACM Trans Knowl Discovery Data (TKDD)"},{"key":"279_CR34","doi-asserted-by":"crossref","unstructured":"Huang C, Zhang Q, Guo D, Zhao X (2023) Discovering persistent subgraph patterns over streaming graphs. In: Proceedings of the international conference on database systems for advanced applications (DASFAA), Tianjin, China, April 17\u201320, pp. 154\u2013171","DOI":"10.1007\/978-3-031-30675-4_11"},{"key":"279_CR35","doi-asserted-by":"crossref","unstructured":"Wang X, Zhang Q, Guo D, Zhao X (2023) Mining top-k frequent patterns over streaming graphs. In: Proceedings of the international conference on database systems for advanced applications (DASFAA), Tianjin, China, April 17\u201320, pp. 199\u2013216","DOI":"10.1007\/978-3-031-30675-4_14"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00279-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-024-00279-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00279-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,18]],"date-time":"2025-09-18T07:54:58Z","timestamp":1758182098000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-024-00279-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,16]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["279"],"URL":"https:\/\/doi.org\/10.1007\/s41019-024-00279-2","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"type":"print","value":"2364-1185"},{"type":"electronic","value":"2364-1541"}],"subject":[],"published":{"date-parts":[[2025,4,16]]},"assertion":[{"value":"19 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}