{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:07:55Z","timestamp":1740103675487,"version":"3.37.3"},"reference-count":44,"publisher":"Wiley","license":[{"start":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T00:00:00Z","timestamp":1608595200000},"content-version":"unspecified","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":["61976032"],"award-info":[{"award-number":["61976032"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2020,12,22]]},"abstract":"<jats:p>Continuous subgraph matching problem on dynamic graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including information retrieval and community detection. Specifically, given a query graph <jats:inline-formula>\n                     <a:math xmlns:a=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M1\">\n                        <a:mi>q<\/a:mi>\n                     <\/a:math>\n                  <\/jats:inline-formula>, an initial graph <jats:inline-formula>\n                     <c:math xmlns:c=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M2\">\n                        <c:msub>\n                           <c:mrow>\n                              <c:mi>G<\/c:mi>\n                           <\/c:mrow>\n                           <c:mrow>\n                              <c:mn>0<\/c:mn>\n                           <\/c:mrow>\n                        <\/c:msub>\n                     <\/c:math>\n                  <\/jats:inline-formula>, and a graph update stream <jats:inline-formula>\n                     <e:math xmlns:e=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M3\">\n                        <e:mo>\u25b3<\/e:mo>\n                        <e:msub>\n                           <e:mrow>\n                              <e:mi>G<\/e:mi>\n                           <\/e:mrow>\n                           <e:mrow>\n                              <e:mi>i<\/e:mi>\n                           <\/e:mrow>\n                        <\/e:msub>\n                     <\/e:math>\n                  <\/jats:inline-formula>, the problem of continuous subgraph matching is to sequentially conduct all possible isomorphic subgraphs covering <jats:inline-formula>\n                     <g:math xmlns:g=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M4\">\n                        <g:mo>\u25b3<\/g:mo>\n                        <g:msub>\n                           <g:mrow>\n                              <g:mi>G<\/g:mi>\n                           <\/g:mrow>\n                           <g:mrow>\n                              <g:mi>i<\/g:mi>\n                           <\/g:mrow>\n                        <\/g:msub>\n                     <\/g:math>\n                  <\/jats:inline-formula> of <jats:inline-formula>\n                     <i:math xmlns:i=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M5\">\n                        <i:mi>q<\/i:mi>\n                     <\/i:math>\n                  <\/jats:inline-formula> on <jats:inline-formula>\n                     <k:math xmlns:k=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M6\">\n                        <k:msub>\n                           <k:mrow>\n                              <k:mi>G<\/k:mi>\n                           <\/k:mrow>\n                           <k:mrow>\n                              <k:mi>i<\/k:mi>\n                           <\/k:mrow>\n                        <\/k:msub>\n                     <\/k:math>\n                  <\/jats:inline-formula> (=<jats:inline-formula>\n                     <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M7\">\n                        <m:msub>\n                           <m:mrow>\n                              <m:mi>G<\/m:mi>\n                           <\/m:mrow>\n                           <m:mrow>\n                              <m:mn>0<\/m:mn>\n                           <\/m:mrow>\n                        <\/m:msub>\n                        <m:mtext>\u2009<\/m:mtext>\n                        <m:mo>\u2295<\/m:mo>\n                        <m:mtext>\u2009<\/m:mtext>\n                        <m:mo>\u25b3<\/m:mo>\n                        <m:msub>\n                           <m:mrow>\n                              <m:mi>G<\/m:mi>\n                           <\/m:mrow>\n                           <m:mrow>\n                              <m:mi>i<\/m:mi>\n                           <\/m:mrow>\n                        <\/m:msub>\n                     <\/m:math>\n                  <\/jats:inline-formula>). Since knowledge graph is a directed labeled multigraph having multiple edges between a pair of vertices, it brings new challenges for the problem focusing on dynamic knowledge graph. One challenge is that the multigraph characteristic of knowledge graph intensifies the complexity of candidate calculation, which is the combination of complex topological and attributed structures. Another challenge is that the isomorphic subgraphs covering a given region are conducted on a huge search space of seed candidates, which causes a lot of time consumption for searching the unpromising candidates. To address these challenges, a method of subgraph-indexed sequential subdivision is proposed to accelerating the continuous subgraph matching on dynamic knowledge graph. Firstly, a flow graph index is proposed to arrange the search space of seed candidates in topological knowledge graph and an adjacent index is designed to accelerate the identification of candidate activation states in attributed knowledge graph. Secondly, the sequential subdivision of flow graph index and the transition state model are employed to incrementally conduct subgraph matching and maintain the regional influence of changed candidates, respectively. Finally, extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.<\/jats:p>","DOI":"10.1155\/2020\/8871756","type":"journal-article","created":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T20:20:06Z","timestamp":1608668406000},"page":"1-18","source":"Crossref","is-referenced-by-count":0,"title":["Subgraph-Indexed Sequential Subdivision for Continuous Subgraph Matching on Dynamic Knowledge Graph"],"prefix":"10.1155","volume":"2020","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1340-9185","authenticated-orcid":true,"given":"Yunhao","family":"Sun","sequence":"first","affiliation":[{"name":"Faculty of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9829-6131","authenticated-orcid":true,"given":"Guanyu","family":"Li","sequence":"additional","affiliation":[{"name":"Faculty of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7098-5509","authenticated-orcid":true,"given":"Mengmeng","family":"Guan","sequence":"additional","affiliation":[{"name":"Faculty of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9512-7036","authenticated-orcid":true,"given":"Bo","family":"Ning","sequence":"additional","affiliation":[{"name":"Faculty of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]}],"member":"311","reference":[{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"M. R. Garey","key":"1"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2015.2432798"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1142\/s1793351x10000936"},{"first-page":"58","article-title":"Sparkwave: continuous schema-enhanced pattern matching over RDF data streams","author":"S. Komazec","key":"4"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3003047"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-00105-0"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453965"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0125-y"},{"first-page":"54","article-title":"Sesame: a generic architecture for storing and querying rdf and rdf schema","author":"J. Broekstra","key":"10"},{"first-page":"502","article-title":"A categorized bibliography on incremental computation","author":"G. Ramalingam","key":"11"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1145\/2508020.2489791"},{"first-page":"411","article-title":"A fast continuous subgraph matching system for streaming graph data","author":"K. Kim","key":"13"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2016.2542804"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2020.3006961"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0360-y"},{"key":"17","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/978-3-540-92673-3_3","article-title":"Resource description framework","volume-title":"Handbook on Ontologies","author":"J. Z. Pan","year":"2009"},{"key":"18","unstructured":"PhuocD. L.ParreiraJ. X.HausenblasM.HauswirthM.Continuous Query Optimization and Evaluation over Unified Linked Stream Data and Linked Open Data2010Galway, IrelandDERITechnical Report"},{"first-page":"74","article-title":"Jena: implementing the semantic web recommendations","author":"J. J. Carroll","key":"19"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453927"},{"first-page":"1216","article-title":"An efficient SQL-based RDF querying scheme","author":"E. I. Chong","key":"21"},{"first-page":"619","article-title":"The LDBC social network benchmark: Interactive workload","author":"O. Erling","key":"22"},{"first-page":"911","article-title":"RDF data-centric storage","author":"J. J. Levandoski","key":"23"},{"first-page":"363","article-title":"RDFBroker: a signature-based high-performance RDF store","author":"M. Sintek","key":"24"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454227"},{"first-page":"261","article-title":"Eddies: continuously adaptive query processing","author":"R. Avnur","key":"26"},{"first-page":"1","article-title":"SPECTRA: continuous query processing for RDF graph streams over sliding windows","author":"S. Gillani","key":"27"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2004.75"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"first-page":"337","article-title":"Towards ultrafast and robust subgraph isomorphism search in large graph databases","author":"W. S. Han","key":"31"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"first-page":"1199","article-title":"Efficient subgraph matching by postponing cartesian products,","author":"F. Bi","key":"33"},{"key":"34","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809985"},{"key":"35","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00372-z"},{"key":"36","doi-asserted-by":"publisher","DOI":"10.1007\/s12559-019-09680-w"},{"key":"37","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-020-00422-x"},{"first-page":"1478","article-title":"Adaptive Dynamic Bipartite Graph Matching: A Reinforcement Learning Approach","author":"Y. Wang","key":"38"},{"key":"39","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-019-1969-x"},{"first-page":"914","article-title":"Weight-constrained route planning over time-dependent graphs","author":"Y. Yuan","key":"40"},{"first-page":"157","article-title":"A selectivity based approach to continuous pattern detection in streaming graphs","author":"S. Choudhury","key":"41"},{"first-page":"281","article-title":"Incremental graph pattern based node matching","author":"G. Sun","key":"42"},{"key":"43","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2018.2879658"},{"first-page":"1233","article-title":"Estimating the cardinality of RDF graph patterns","author":"A. Maduko","key":"44"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8871756.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8871756.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8871756.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T20:20:10Z","timestamp":1608668410000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/complexity\/2020\/8871756\/"}},"subtitle":[],"editor":[{"given":"Weitong","family":"Chen","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,22]]},"references-count":44,"alternative-id":["8871756","8871756"],"URL":"https:\/\/doi.org\/10.1155\/2020\/8871756","relation":{},"ISSN":["1099-0526","1076-2787"],"issn-type":[{"type":"electronic","value":"1099-0526"},{"type":"print","value":"1076-2787"}],"subject":[],"published":{"date-parts":[[2020,12,22]]}}}