Improving the Performance of Parallel SPARQL Query Processing on Apache Spark Using Bloom Filters

The Resource Description Framework (RDF) has become the standard model for data representation on the Web. In RDF, IRIs are used to represent entities and their relationships. SPARQL is the query language for RDF. Today, popular knowledge bases on the Web (e.g., Wikidata, YAGO, Linked Data) employ RDF and SPARQL for representing data and querying relevant information. There is also a growing number of applications in domains such as healthcare, finance, and national security that are employing RDF and Web Ontology Language (OWL). In recent years, the size of RDF datasets on the Web has grown tremendously. Techniques designed for centralized RDF query processing are no longer capable of efficiently handling billions of triples in an RDF dataset. This has led to the use of parallel RDF query processing techniques utilizing cluster computing. Among the different platforms for cluster computing, Apache Spark has emerged as the industry leader with a huge development community. In this thesis, we extend our previous work on parallel SPARQL query processing using Apache Spark, which proposed a simple partitioning strategy for a large RDF dataset. In that study, we computed connected components in large RDF datasets followed by indexing groups of those connected components on different machines in the cluster. However, such an approach yields poor performance when the queries are highly selective and produce results only on a few indexes in the cluster. Motivated by these reasons, we propose a Bloom filter-based approach to improve the performance of parallel SPARQL query processing on Apache Spark. We construct a Bloom filter for each index based on different patterns over (subject, predicate, object) triples stored in that index. When a query is posed, the Bloom filters are first tested in parallel on the cluster nodes. The actual query is executed only on those indexes whose Bloom filters indicate a possible match. Thus, fewer indexes are queried resulting in faster query execution time. We present the performance evaluation of our approach using a real dataset containing 6.4 billion triples (806 GB) on a 7-node cluster (with 56 cores) setup on Microsoft Azure. We show that our approach of leveraging Bloom filters during query processing improves the performance of SPARQL query execution on Apache Spark.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science (UMKC)

Grantor dc:publisher

University of Missouri--Kansas City

Year dc:date.issued

2017

Author dc:creator

• Kolla, Venubabu

Advisor dc:contributor.advisor

• Rao, Praveen R.

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10355/60058

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/60058