Dominance-Partitioned Subgraph Matching on Large RDF Graph
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 RD...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/6620528 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832546809089622016 |
|---|---|
| author | Bo Ning Yunhao Sun Deji Zhao Weikang Xing Guanyu Li |
| author_facet | Bo Ning Yunhao Sun Deji Zhao Weikang Xing Guanyu Li |
| author_sort | Bo Ning |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-676088f7fa6049848ac62a7560213cdd |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-676088f7fa6049848ac62a7560213cdd2025-02-03T06:47:00ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/66205286620528Dominance-Partitioned Subgraph Matching on Large RDF GraphBo Ning0Yunhao Sun1Deji Zhao2Weikang Xing3Guanyu Li4School of Information Science and Technology, Dalian Maritime University, Dalian 116026, ChinaSchool of Information Science and Technology, Dalian Maritime University, Dalian 116026, ChinaSchool of Information Science and Technology, Dalian Maritime University, Dalian 116026, ChinaSchool of Information Science and Technology, Dalian Maritime University, Dalian 116026, ChinaSchool of Information Science and Technology, Dalian Maritime University, Dalian 116026, ChinaSubgraph 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.http://dx.doi.org/10.1155/2020/6620528 |
| spellingShingle | Bo Ning Yunhao Sun Deji Zhao Weikang Xing Guanyu Li Dominance-Partitioned Subgraph Matching on Large RDF Graph Complexity |
| title | Dominance-Partitioned Subgraph Matching on Large RDF Graph |
| title_full | Dominance-Partitioned Subgraph Matching on Large RDF Graph |
| title_fullStr | Dominance-Partitioned Subgraph Matching on Large RDF Graph |
| title_full_unstemmed | Dominance-Partitioned Subgraph Matching on Large RDF Graph |
| title_short | Dominance-Partitioned Subgraph Matching on Large RDF Graph |
| title_sort | dominance partitioned subgraph matching on large rdf graph |
| url | http://dx.doi.org/10.1155/2020/6620528 |
| work_keys_str_mv | AT boning dominancepartitionedsubgraphmatchingonlargerdfgraph AT yunhaosun dominancepartitionedsubgraphmatchingonlargerdfgraph AT dejizhao dominancepartitionedsubgraphmatchingonlargerdfgraph AT weikangxing dominancepartitionedsubgraphmatchingonlargerdfgraph AT guanyuli dominancepartitionedsubgraphmatchingonlargerdfgraph |