| Subgraph matching,as a fundamental problem in graph theory,is also the basic query pattern in RDF graph data management.With the movement of linked open data and semantic web,the large scale of linked open data combined with the theory complexity of subgraph matching make efficient RDF graph data management a challenging work.The efficiencies of those existing serial filter-and-refine approaches,however,depend on the capabilities of central processing units(CPU).GPU has been widely used in general computing owe to the development of modern hardware.Compared to CPU,GPU has higher computational performance,more scalability,and lower price and it's a tough work to design efficient parallel matching algorithm in RDF graph.In this paper,we expand the concept of type isomorphism to RDF graphs and propose two parallel matching schemas on the GPU.In centralized matching scheme,we present a concurrent RDF graph matching model for type-isomorphism so that the subgraph matching based on type-isomorphism can be paralleled.We develop a parallel RDF graph matching algorithm to implement a prototype called IRSMG.In the solution of parallel computing clusters,we furtherly put forward a hybrid parallel computing architecture called gmars which combine the single GPU parallel with parallel computing cluster.Master node decompose query and put subquery into worker node.Query result can be reconstructed the by join all the subquery result.Extensive experiments are tested in different size of dataset and the experimental results show that our algorithm can outperforms the serial algorithm on the CPU very well(about 3-5 times)To sum up,this paper propose two methods for subgraph matching in large scale of RDF graph,stand-alone and computing cluster and some detailed algorithm schema is given for parallel matching and query reconstruction.Experimental results show that our method can efficiently support type isomorphism matching by using GPU's large scale parallel and computing cluster. |
PDF Full Text Request