{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:07:50Z","timestamp":1740103670670,"version":"3.37.3"},"reference-count":34,"publisher":"Wiley","license":[{"start":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T00:00:00Z","timestamp":1608681600000},"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,23]]},"abstract":"<jats:p>Subgraph matching on a large graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including question answering and community detection. However, traditional edge-cutting strategy destroys the structure of indivisible knowledge in a large RDF graph. On the premise of load-balancing on subgraph division, a dominance-partitioned strategy is proposed to divide a large RDF graph without compromising the knowledge structure. Firstly, a dominance-connected pattern graph is extracted from a pattern graph to construct a dominance-partitioned pattern hypergraph, which divides a pattern graph as multiple fish-shaped pattern subgraphs. Secondly, a dominance-driven spectrum clustering strategy is used to gather the pattern subgraphs into multiple clusters. Thirdly, the dominance-partitioned subgraph matching algorithm is designed to conduct all isomorphic subgraphs on a cluster-partitioned RDF graph. Finally, experimental evaluation verifies that our strategy has higher time-efficiency of complex queries, and it has a better scalability on multiple machines and different data scales.<\/jats:p>","DOI":"10.1155\/2020\/6620528","type":"journal-article","created":{"date-parts":[[2020,12,24]],"date-time":"2020-12-24T01:35:50Z","timestamp":1608773750000},"page":"1-18","source":"Crossref","is-referenced-by-count":2,"title":["Dominance-Partitioned Subgraph Matching on Large RDF Graph"],"prefix":"10.1155","volume":"2020","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9512-7036","authenticated-orcid":true,"given":"Bo","family":"Ning","sequence":"first","affiliation":[{"name":"School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1340-9185","authenticated-orcid":true,"given":"Yunhao","family":"Sun","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8303-6943","authenticated-orcid":true,"given":"Deji","family":"Zhao","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9686-2216","authenticated-orcid":true,"given":"Weikang","family":"Xing","sequence":"additional","affiliation":[{"name":"School 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":"School 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.14778\/1453856.1453927"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453965"},{"first-page":"289","article-title":"TriAD: a distributed shared-nothing RDF engine based on asynchronous message passing","author":"S. Gurajada","key":"4"},{"first-page":"317","article-title":"Fast and concurrent RDF queries with RDMA-based distributed graph exploration","author":"J. Shi","key":"5"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149200"},{"first-page":"415","article-title":"StarMR: an efficient star-decomposition based query processor for SPARQL basic graph patterns using MapReduce","author":"Q. Xu","key":"7"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-0090-z"},{"first-page":"1199","article-title":"Efficient subgraph matching by postponing cartesian products","author":"F. Bi","key":"9"},{"key":"10","first-page":"71","article-title":"Resource description framework","volume-title":"Handbook on Ontologies","author":"J. Z. Pan","year":"2019"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0125-y"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2841389"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402747"},{"first-page":"35","article-title":"Clause-iteration with MapReduce to scalably query datagraphs in the SHARD graph-store","author":"K. Rohloff","key":"15"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1137\/s1064827595287997"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.14778\/2977797.2977806"},{"first-page":"41","article-title":"Matrix bit loaded: a scalable lightweight join query processor for RDF data","author":"M. Atre","key":"19"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536352"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.14778\/2002974.2002976"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-018-7212-z"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488333"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-020-07283-1"},{"first-page":"161","article-title":"Effective and efficient community search in directed graphs across heterogeneous social networks","author":"Z. Wang","key":"25"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00372-z"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00075"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1109\/tpds.2016.2535444"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1504\/ijdmb.2019.10022331"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3003047"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2020.101522"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0360-y"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"34","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6620528.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6620528.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6620528.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,24]],"date-time":"2020-12-24T01:35:54Z","timestamp":1608773754000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/complexity\/2020\/6620528\/"}},"subtitle":[],"editor":[{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,23]]},"references-count":34,"alternative-id":["6620528","6620528"],"URL":"https:\/\/doi.org\/10.1155\/2020\/6620528","relation":{},"ISSN":["1099-0526","1076-2787"],"issn-type":[{"type":"electronic","value":"1099-0526"},{"type":"print","value":"1076-2787"}],"subject":[],"published":{"date-parts":[[2020,12,23]]}}}