An effective and efficient MapReduce algorithm for computing BFS-based traversals of large-scale RDF graphs (Q1736757)

Summary: Nowadays, a leading instance of \textit{big data} is represented by \textit{Web data} that lead to the definition of so-called \textit{big Web data}. Indeed, extending beyond to a large number of critical applications (e.g., \textit{Web advertisement}), these data expose several characteristics that clearly adhere to the well-known \textit{3V properties} (\textit{i.e.}, \textit{volume}, \textit{velocity}, \textit{variety}). \textit{Resource Description Framework} (RDF) is a significant formalism and language for the so-called \textit{Semantic Web}, due to the fact that a very wide family of \textit{Web entities} can be naturally modeled in a \textit{graph-shaped manner}. In this context, \textit{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 \textit{social networks}. When RDF graphs are defined on top of big (Web) data, they lead to the so-called \textit{large-scale RDF graphs}, which reasonably populate the next-generation Semantic Web. In order to process such kind of big data, \textit{MapReduce}, an open source computational framework specifically tailored to \textit{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 \textit{an approach for efficiently implementing traversals of large-scale RDF graphs over MapReduce} that is based on the \textit{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.