title: A distributed query execution engine of big attributed graphs.
abstract: A graph is a popular data model that has become pervasively used for modeling structural relationships between objects. In practice, in many real-world graphs, the graph vertices and edges need to be associated with descriptive attributes. Such type of graphs are referred to as attributed graphs. G-SPARQL has been proposed as an expressive language, with a centralized execution engine, for querying attributed graphs. G-SPARQL supports various types of graph querying operations including reachability, pattern matching and shortest path where any G-SPARQL query may include value-based predicates on the descriptive information (attributes) of the graph edges/vertices in addition to the structural predicates. In general, a main limitation of centralized systems is that their vertical scalability is always restricted by the physical limits of computer systems. This article describes the design, implementation in addition to the performance evaluation of DG-SPARQL, a distributed, hybrid and adaptive parallel execution engine of G-SPARQL queries. In this engine, the topology of the graph is distributed over the main memory of the underlying nodes while the graph data are maintained in a relational store which is replicated on the disk of each of the underlying nodes. DG-SPARQL evaluates parts of the query plan via SQL queries which are pushed to the underlying relational stores while other parts of the query plan, as necessary, are evaluated via indexless memory-based graph traversal algorithms. Our experimental evaluation shows the efficiency and the scalability of DG-SPARQL on querying massive attributed graph datasets in addition to its ability to outperform the performance of Apache Giraph, a popular distributed graph processing system, by orders of magnitudes.
authors.affiliation: King Abdulaziz University, Jeddah, Saudi Arabia.
authors.forename: Omar
authors.initials: O
authors.lastname: Batarfi
authors.affiliation: Princess Nourah Bint Abdulrahman University, Riyadh, Saudi Arabia.
authors.forename: Radwa
authors.initials: R
authors.lastname: Elshawi
authors.affiliation: King Abdulaziz University, Jeddah, Saudi Arabia.
authors.forename: Ayman
authors.initials: A
authors.lastname: Fayoumi
authors.affiliation: King Abdulaziz University, Jeddah, Saudi Arabia.
authors.forename: Ahmed
authors.initials: A
authors.lastname: Barnawi
authors.affiliation: University of New South Wales, Sydney, Australia ; King Saud bin Abdulaziz University for Health Sciences, Riyadh, Saudi Arabia.
authors.forename: Sherif
authors.initials: S
authors.lastname: Sakr