Dominance-Partitioned Subgraph Matching on Large RDF Graph

Abstract EN

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.