The Research Of Subgraph Matching On Large-Scale RDF Graph

Basic Subgraph Pattern Matching is a NP-complete problem,also known as subgraph isomorphism.With the development of the Semantic Web and Linked Open Data,more and more data is published in RDF.The high time complexity of subgraph isomorphism and large scale of RDF data have made a big challenge to the management.The main contributions of this dissertation contain two parts.We present a stand-alone querying method,in which we decompose a data graph into a set of star-like subgraphs and encode them into binary bit-strings.Converting join operations to binary bitwise OR or AND operations decreases the complexity of query processing.The bit-string is used to filter out false results.This method avoids lots of expensive self-join operations.As carefully designed indices,we can fetch a subgraph rather than a single triple by one access to the indices.For the distributed solution,we drop MapReduce framework and turn to BSP framework.The message passing mechanism fits solving computation on graph.We pass a query from one vertex to another.In the passing procedure,variable is binding one by one.We also implements a series of experiments to evaluate the performance of both the stand-alone method and the distributed method.To sum up,this dissertation presents two methods,stand-alone and distributed,to solve the subgraph matching.Some detailed scheme is given to optimize the indices,encoding technic,and querying algorithm.They both decrease the time complexity of querying.