Using Vertex-Centric Programming Platforms to Implement SPARQL Queries on Large Graphs

In this paper we explore the fusion of two largely disparate but related communities, that of Big Data and the Semantic Web. Due to the rise of large real-world graph datasets, a number of graph-centric parallel platforms have been proposed and developed. Many of these platforms, notable among them Pregel, Giraph, GraphLab, GraphChi, the Graph Processing System, and GraphX, present a programming interface that is vertex-centric, a variant of Valiant's Bulk Synchronous Parallel model. These platforms seek to address growing analytical needs for very large graph datasets arising from a variety of sources, such as social, biological, and computer networks. With this growing interest in large graphs, there has also been a concomitant rise in the Semantic Web, which describes data in terms of subject-predicate-object triples, or in other words edges of a graph where the predicate is a directed labeled edge between the two vertices, the subject and object. Despite the graph-oriented nature of Semantic Web data, and the advent of an increasingly large web of data, no one has explored the usage of these maturing graph platforms to analyze Semantic Web data. In this paper we outline a method of implementing SPARQL queries within the GraphLab framework, obtaining good scaling to the size of our system, 51 nodes.

I. Introduction

With the rise of social, biological, and technological networks of continually increasing size, interest in how to analyze these datasets in a parallel fashion has also grown. Many of these problems are represented as graphs, where there are nodes or entities and connections between them called edges.