{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:12:34Z","timestamp":1784099554566,"version":"3.55.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:00:00Z","timestamp":1618272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:00:00Z","timestamp":1618272000000},"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":["U19B2024"],"award-info":[{"award-number":["U19B2024"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Key Research and Development Program","award":["2018YFB1800203"],"award-info":[{"award-number":["2018YFB1800203"]}]},{"DOI":"10.13039\/501100004761","name":"Natural Science Foundation of Hunan Province","doi-asserted-by":"crossref","award":["Natural Science Foundation of Hunan Province"],"award-info":[{"award-number":["Natural Science Foundation of Hunan Province"]}],"id":[{"id":"10.13039\/501100004761","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872446"],"award-info":[{"award-number":["61872446"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["World Wide Web"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Nowadays, the scale of various graphs soars rapidly, which imposes a serious challenge to develop processing and analytic algorithms. Among them, graph pattern matching is the one of the most primitive tasks that find a wide spectrum of applications, the performance of which is yet often affected by the size and dynamicity of graphs. In order to handle large dynamic graphs, incremental pattern matching is proposed to avoid re-computing matches of patterns over the entire data graph, hence reducing the matching time and improving the overall execution performance. Due to the complexity of the problem, little work has been reported so far to solve the problem, and most of them only solve the graph pattern matching problem under the scenario of the data graph varying alone. In this article, we are devoted to a more complicated but very practical graph pattern matching problem, <jats:italic>continuous matching of evolving patterns over dynamic graph data<\/jats:italic>, and the investigation presents a novel algorithm  for continuously pattern matching along with changes of both pattern graph and data graph. Specifically, we propose a concise representation  of partial matching solutions, which can help to avoid re-computing matches of the pattern and speed up subsequent matching process. In order to enable the updates of data graph and pattern graph, we propose an incremental maintenance strategy, to efficiently maintain the intermediate results. Moreover, we conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of .<\/jats:p>","DOI":"10.1007\/s11280-020-00860-5","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T16:38:51Z","timestamp":1618331931000},"page":"721-745","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Continuous matching of evolving patterns over dynamic graph data"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2856-4599","authenticated-orcid":false,"given":"Qianzhen","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deke","family":"Guo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiang","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,13]]},"reference":[{"key":"860_CR1","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In: SIGMOD\u2019 16, San Francisco, CA, USA, June 26 - July 01, 2016, pp. 1199\u20131214 (2016)","DOI":"10.1145\/2882903.2915236"},{"key":"860_CR2","unstructured":"Choudhury, S., Holder, L.B. Jr., Agarwal, G.C.K, Feo, J.: A selectivity based approach to continuous pattern detection in streaming graphs. In: EDBT\u2019 15, Brussels, Belgium, March 23-27, 2015, pp. 157\u2013168 (2015)"},{"key":"860_CR3","doi-asserted-by":"crossref","unstructured":"Choudhury, S., Holder, L.B. Jr, Ray, G.C., Beus, A., Feo, S.J.: Streamworks: A system for dynamic graph search. In: Ross, K.A., Srivastava, D., Papadias, D. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pp 1101\u20131104. ACM (2013)","DOI":"10.1145\/2463676.2463697"},{"issue":"10","key":"860_CR4","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell 26(10), 1367\u20131372 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"key":"860_CR5","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Luo, J., Tan, Z., Wang, X., Wu, Y.: Incremental graph pattern matching. In: SIGMOD\u201911, Athens, Greece, June 12-16, 2011, pp. 925\u2013936 (2011)","DOI":"10.1145\/1989323.1989420"},{"issue":"2","key":"860_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00778-015-0416-z","volume":"25","author":"J Gao","year":"2016","unstructured":"Gao, J., Zhou, C., Yu, J.X.: Toward continuous pattern detection over evolving large graph with snapshot isolation. VLDB J. 25(2), 269\u2013290 (2016)","journal-title":"VLDB J."},{"key":"860_CR7","doi-asserted-by":"crossref","unstructured":"Han, M., Kim, H., Gu, G., Park, K., Han, W.: Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In: Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pp 1429\u20131446 (2019)","DOI":"10.1145\/3299869.3319880"},{"key":"860_CR8","doi-asserted-by":"crossref","unstructured":"Han, W., Lee, J., Lee, J.: Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD\u201913, New York, USA, June 22-27, 2013, pp. 337\u2013348 (2013)","DOI":"10.1145\/2463676.2465300"},{"key":"860_CR9","doi-asserted-by":"crossref","unstructured":"Kankanamge, C., Sahu, S., Mhedbhi, A., Chen, J., Salihoglu, S.: Graphflow: An active graph database. In: SIGMOD\u201917, Chicago, IL, USA, May 14-19, 2017, pp. 1695\u20131698 (2017)","DOI":"10.1145\/3035918.3056445"},{"key":"860_CR10","doi-asserted-by":"crossref","unstructured":"Kim, K., Seo, I., Han, W., Lee, J., Hong, S., Chafi, H., Shin, H., Jeong, G.: Turboflux: A fast continuous subgraph matching system for streaming graph data. In: SIGMOD\u201918, Houston, TX, USA, June 10-15, 2018, pp. 411\u2013426 (2018)","DOI":"10.1145\/3183713.3196917"},{"issue":"5","key":"860_CR11","doi-asserted-by":"publisher","first-page":"602","DOI":"10.14778\/3377369.3377371","volume":"13","author":"D Ouyang","year":"2020","unstructured":"Ouyang, D., Yuan, L., Qin, L., Chang, L., Zhang, Y., Lin, X.: Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proc. VLDB Endow. 13(5), 602\u2013615 (2020)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"860_CR12","first-page":"364","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: An efficient algorithm for testing subgraph isomorphism. PVLDB 1(1), 364\u2013375 (2008)","journal-title":"PVLDB"},{"key":"860_CR13","doi-asserted-by":"crossref","unstructured":"Wang, C., Chen, L.: Continuous subgraph pattern search over graph streams. In: ICDE\u201909, Shanghai, China, March 29 - April 2, 2009, pp. 393\u2013404 (2009)","DOI":"10.1109\/ICDE.2009.132"},{"issue":"2","key":"860_CR14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00778-015-0408-z","volume":"25","author":"L Yuan","year":"2016","unstructured":"Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: Diversified top-k clique search. VLDB J. 25(2), 171\u2013196 (2016)","journal-title":"VLDB J."},{"issue":"5","key":"860_CR15","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1109\/TKDE.2017.2783933","volume":"30","author":"L Yuan","year":"2018","unstructured":"Yuan, L., Qin, L., Zhang, W., Chang, L., Yang, J.: Index-based densest clique percolation community search in networks. IEEE Trans. Knowl. Data Eng. 30(5), 922\u2013935 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"860_CR16","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Guo, D., Zhao, X., Guo, A.: On continuously matching of evolving graph patterns. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019, pp. 2237\u20132240 (2019)","DOI":"10.1145\/3357384.3358101"},{"issue":"1","key":"860_CR17","first-page":"340","volume":"3","author":"P Zhao","year":"2010","unstructured":"Zhao, P., Han, J.: On graph query optimization in large networks. PVLDB 3(1), 340\u2013351 (2010)","journal-title":"PVLDB"}],"container-title":["World Wide Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-020-00860-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11280-020-00860-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-020-00860-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,21]],"date-time":"2021-05-21T17:15:36Z","timestamp":1621617336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11280-020-00860-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,13]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["860"],"URL":"https:\/\/doi.org\/10.1007\/s11280-020-00860-5","relation":{},"ISSN":["1386-145X","1573-1413"],"issn-type":[{"value":"1386-145X","type":"print"},{"value":"1573-1413","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,13]]},"assertion":[{"value":"8 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}