An Effective and Efficient MapReduce Algorithm for Computing BFS-Based Traversals of Large-Scale RDF Graphs

Algorithms

Alfredo Cuzzocrea¹  Mirel Cosulschi²  Roberto de Virgilio³ 

[1]DIA Department, University of Trieste and ICAR-CNR, Trieste 34127, Italy

[2]Department of Computer Science, University of Craiova, Craiova 200585, Romania

[3]Dipartimento di Informatica e Automazione, Universitá Roma Tre, Rome 00146, Italy

关键词: MapReduce algorithms;    BFS-traversals of RDF graphs;    effective and efficient algorithms for big data processing;   

DOI  :  10.3390/a9010007

来源: mdpi

【 摘 要 】

Nowadays, a leading instance of big data is represented by Web data that lead to the definition of so-called big Web data. Indeed, extending beyond to a large number of critical applications (e.g., Web advertisement), these data expose several characteristics that clearly adhere to the well-known 3V properties (i.e., volume, velocity, variety). Resource Description Framework (RDF) is a significant formalism and language for the so-called Semantic Web, due to the fact that a very wide family of Web entities can be naturally modeled in a graph-shaped manner. In this context, RDF graphs play a first-class role, because they are widely used in the context of modern Web applications and systems, including the emerging context of social networks. When RDF graphs are defined on top of big (Web) data, they lead to the so-called large-scale RDF graphs, which reasonably populate the next-generation Semantic Web. In order to process such kind of big data, MapReduce, an open source computational framework specifically tailored to big data processing, has emerged during the last years as the reference implementation for this critical setting. In line with this trend, in this paper, we present an approach for efficiently implementing traversals of large-scale RDF graphs over MapReduce that is based on the Breadth First Search (BFS) strategy for visiting (RDF) graphs to be decomposed and processed according to the MapReduce framework. We demonstrate how such implementation speeds-up the analysis of RDF graphs with respect to competitor approaches. Experimental results clearly support our contributions.

【 授权许可】

CC BY   
© 2016 by the authors; licensee MDPI, Basel, Switzerland.