{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:59Z","timestamp":1779174779120,"version":"3.51.4"},"reference-count":29,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2022,5,31]],"date-time":"2022-05-31T00:00:00Z","timestamp":1653955200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SW"],"published-print":{"date-parts":[[2022,5,31]]},"abstract":"<jats:p>There is a growing need to perform real-time analytics on dynamic graphs in order to deliver the values of big data to users. An important problem from such applications is continuously identifying and monitoring critical patterns when fine-grained updates at a high velocity occur on the graphs. A\u00a0lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and\/or many graphs. In this paper, we study the problem of continuous multi-query optimization for subgraph matching over dynamic graph data. (1)\u00a0We propose annotated query graph, which is obtained by merging the multi-queries into one. (2)\u00a0Based on the annotated query, we employ a concise auxiliary data structure to represent partial solutions in a compact form. (3)\u00a0In addition, we propose an efficient maintenance strategy to detect the affected queries for each update and report corresponding matches in one pass. (4)\u00a0Extensive experiments over real-life and synthetic datasets verify the effectiveness and efficiency of our approach and confirm a two orders of magnitude improvement of the proposed solution.<\/jats:p>","DOI":"10.3233\/sw-212864","type":"journal-article","created":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T12:10:22Z","timestamp":1643371822000},"page":"601-622","source":"Crossref","is-referenced-by-count":5,"title":["Continuous multi-query optimization for subgraph matching over dynamic graphs"],"prefix":"10.1177","volume":"13","author":[{"given":"Xi","family":"Wang","sequence":"first","affiliation":[{"name":"Science and Technology on Information Systems Engineering Laboratory, University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qianzhen","family":"Zhang","sequence":"additional","affiliation":[{"name":"Science and Technology on Information Systems Engineering Laboratory, University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deke","family":"Guo","sequence":"additional","affiliation":[{"name":"Science and Technology on Information Systems Engineering Laboratory, University of Defense Technology, China"},{"name":"Tianjin Key Laboratory of Advanced Networking (TANK), College of Intelligence and Computing, Tianjin University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Science and Technology on Information Systems Engineering Laboratory, University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/SW-212864_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"issue":"2","key":"10.3233\/SW-212864_ref2","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/TKDE.2018.2830336","article-title":"Efficient mining of frequent patterns on uncertain graphs","volume":"31","author":"Chen","year":"2019","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"10.3233\/SW-212864_ref3","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2015.15"},{"issue":"10","key":"10.3233\/SW-212864_ref4","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.3233\/SW-212864_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"10.3233\/SW-212864_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"10.3233\/SW-212864_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/582353.582400"},{"issue":"2","key":"10.3233\/SW-212864_ref8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00778-015-0416-z","article-title":"Toward continuous pattern detection over evolving large graph with snapshot isolation","volume":"25","author":"Gao","year":"2016","journal-title":"VLDB J."},{"key":"10.3233\/SW-212864_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2933267.2933306"},{"key":"10.3233\/SW-212864_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"10.3233\/SW-212864_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_4"},{"key":"10.3233\/SW-212864_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"10.3233\/SW-212864_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"10.3233\/SW-212864_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"10.3233\/SW-212864_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"issue":"2","key":"10.3233\/SW-212864_ref17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.14778\/2535568.2448946","article-title":"An in-depth comparison of subgraph isomorphism algorithms in graph databases","volume":"6","author":"Lee","year":"2012","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"10.3233\/SW-212864_ref18","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/3446980","article-title":"Optimizing one-time and continuous subgraph queries using worst-case optimal joins","volume":"46","author":"Mhedhbi","year":"2021","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"10.3233\/SW-212864_ref19","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/2541290","article-title":"Efficient multiview maintenance under insertion in huge social networks","volume":"8","author":"Pugliese","year":"2014","journal-title":"ACM Trans. Web"},{"issue":"1","key":"10.3233\/SW-212864_ref20","doi-asserted-by":"publisher","first-page":"82","DOI":"10.26599\/TST.2018.9010105","article-title":"Design and optimization of VLC enabled data center network","volume":"25","author":"Qin","year":"2020","journal-title":"Tsinghua Science and Technology"},{"key":"10.3233\/SW-212864_ref21","doi-asserted-by":"publisher","DOI":"10.26599\/TST.2018.9010093"},{"issue":"2","key":"10.3233\/SW-212864_ref22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.26599\/TST.2018.9010072","article-title":"Minimum-cost forest for uncertain multicast with delay constraints","volume":"24","author":"Ren","year":"2019","journal-title":"Tsinghua Science and Technology"},{"issue":"3","key":"10.3233\/SW-212864_ref23","doi-asserted-by":"publisher","first-page":"121","DOI":"10.14778\/3021924.3021929","article-title":"Multi-query optimization for subgraph isomorphism search","volume":"10","author":"Ren","year":"2016","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"10.3233\/SW-212864_ref24","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/42201.42203","article-title":"Multiple-query optimization","volume":"13","author":"Sellis","year":"1988","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"10.3233\/SW-212864_ref25","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1109\/69.54724","article-title":"On the multiple-query optimization problem","volume":"2","author":"Sellis","year":"1990","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"10.3233\/SW-212864_ref26","doi-asserted-by":"publisher","first-page":"364","DOI":"10.14778\/1453856.1453899","article-title":"Taming verification hardness: An efficient algorithm for testing subgraph isomorphism","volume":"1","author":"Shang","year":"2008","journal-title":"Proc. VLDB Endow."},{"key":"10.3233\/SW-212864_ref27","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1093\/nar\/gkj109","article-title":"BioGRID: A general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucleic Acids Res."},{"issue":"1","key":"10.3233\/SW-212864_ref28","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM"},{"key":"10.3233\/SW-212864_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.132"},{"key":"10.3233\/SW-212864_ref30","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2020.03"}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-212864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:26:16Z","timestamp":1777613176000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-212864"}},"subtitle":[],"editor":[{"family":"Axel-Cyrille Ngonga Ngomo","sequence":"additional","affiliation":[{"name":"University of Paderborn, Germany"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"family":"Muhammad Saleem","sequence":"additional","affiliation":[{"name":"University of Leipzig, Germany"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"family":"Ruben Verborgh","sequence":"additional","affiliation":[{"name":"Ghent University \u2013 imec, Belgium"}],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Axel-Cyrille","family":"Ngonga Ngomo","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Muhammad","family":"Saleem","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Ruben","family":"Verborgh","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2022,5,31]]},"references-count":29,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.3233\/sw-212864","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2022,5,31]]}}}