RIQ : Fast processing of SPARQL queries on RDF quadruples

Anas Katib, Vasil Slavov, Praveen Rao

Abstract


In this paper, we address the problem of fast processing of SPARQL queries on a large RDF dataset, where the RDF statements are quadruples (or quads). Quads can capture provenance or other relevant information about facts. This is especially powerful in modeling knowledge graphs, which are becoming increasingly important on the Web to provide high quality search results to users. We propose a new approach called View the MathML source that employs a decrease-and-conquer   strategy for fast SPARQL query processing. Rather than indexing the entire RDF dataset, View the MathML source identifies groups of similar RDF graphs and creates indexes on each group separately. It employs a new vector representation for RDF graphs and locality sensitive hashing to construct the groups efficiently. It constructs a novel filtering index on the groups and compactly represents the index as a combination of Bloom and Counting Bloom Filters. During query processing, View the MathML source employs a streamlined approach. It constructs a query plan for a SPARQL query (containing one or more graph patterns), searches the filtering index to quickly identify candidate groups that may contain matches for the query, and rewrites the original query to produce an optimized query for each candidate. The optimized queries are then executed using an existing SPARQL processor that supports quads to produce the final results. We conducted a comprehensive evaluation of View the MathML source using a real and synthetic dataset, each containing about 1.4 billion quads. Our results show that View the MathML source can outperform its competitors designed to support named graph queries on RDF quads (e.g., Jena TDB and Virtuoso) for a variety of queries.

Full Text: Untitled
Type of Paper: Research Paper
Keywords: RDF; Quadruples; SPARQL; Query processing; Knowledge graphs
Show BibTex format: BibTeX