RDF-G*: An efficient RDF query answer engine based on graph model and star index

In recent years, structured knowledge represented in the form of RDF (Resource Description Framework) data has been increasingly utilized by a growing number of applications, as a result efficient processing of SPARQL queries over RDF datasets has become more and more important. There exist two typical approaches to manage RDF data: relational approaches and graph-based approaches. The graph model fits the RDF framework more naturally for depending less on schema regulations, being easy to add or remove link, and handling queries by subgraph matching without costly join operations. However, there is still large room for improvement in existing graph-based RDF query engines. We propose RDF-G*, a high-performance RDF query engine based on the graph model and star index. RDF-G* incorporates a new multi-level filtering index, the star index, which is built using our proposed KDBox-SS-tree index. Additionally, we present a novel encoding method for the vertex neighborhood structure of the RDF data graph, utilizing minimum bounding boxes (MBB) and signatures. Furthermore, a meticulously designed subgraph matching algorithm and a cost-based query optimizer enable RDF-G* to execute SPARQL queries efficiently. Experiments on both synthetic and real-life RDF datasets demonstrate that our proposed query engine can dramatically boost the performance of SPARQL query processing.