FFD-Index: An Efficient Indexing Scheme for Star Subgraph Matching on Large RDF Graphs

Subgraph matching, a basic SPARQL operation, is known to be NP-complete. Coupled with the rapidly increasing volumes of RDF data, it makes efficient graph query processing a very challenging problem. In this paper, we tackle the important problem of efficient processing of star-shaped subgraph matching queries, which are a core SPARQL query pattern and usually lead to a number of costly join operations. We present a novel method to encode a star-shaped subgraph into a bit string and an indexing mechanism to improve the query answering performance, called FFD-index. Our extensive evaluation shows that FFD-index and the corresponding algorithms are effective in solving star-shaped graph queries and they significantly outperform the state-of-the-art SPARQL query engine RDF-3X.