RDF Subgraph Matching by Means of Star Decomposition

Abstract

With the continuous development of the network, the scale of RDF data is becoming larger and larger. In the face of large-scale RDF data processing, the traditional database query method has been unable to meet the needs. Due to the limited characteristics of subgraph matching, most existing algorithms often have the phenomenon that many subgraphs are repeatedly traversed during the query process, resulting in a large number of intermediate result sets and low query efficiency. The core problem to be solved is how to efficiently match subgraphs. In order to improve the query efficiency of RDF subgraphs in massive RDF data graphs and solve the problem of repeated calculation of some graphs in the query process of RDF subgraphs, an RDF subgraph query algorithm based on star decomposition is proposed in this paper. The algorithm uses graph structure to decompose RDF subgraphs into stars and uses a custom node cost model to calculate the query order of the star subgraphs. By decomposing, the amount of communication among subgraphs is reduced, and the communication cost for query processing is lowered. Moreover, utilizing the query order for RDF subgraph matching can effectively reduce the generation of intermediate result sets and accelerate the efficiency of subgraph matching. On this basis, the performances of the proposed algorithm and several other widely used algorithms are compared and analyzed on two different datasets. Experiments show that the proposed algorithm has better advantages in database recreation, memory size, and execution efficiency.