Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
FFD-Index: An Efficient Indexing Scheme for Star Subgraph Matching on Large RDF Graphs
verfasst von : Xuedong Lyu, Xin Wang, Yuan-Fang Li, Zhiyong Feng
Erschienen in: Database Systems for Advanced Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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.