## 1 Introduction  
_Big data_ describe data sets that grow so large that they become unpractical to be processed by traditional tools like database management systems, content management systems, advanced statistical analysis software, and so forth. The reason why they came into the attention of the research community is that the infrastructure to handle these data sets has become more affordable due to _Cloud Computing_ and _MapReduce_[1] based open-source frameworks. The vision of everyday people inspecting large amounts of data, easily interacting with graphical interfaces of software applications that handle _data mining tasks_, has indeed enthused final users. On the other hand, those tools have to leverage people's ability to answer analytical processes by inference through large amounts of data. The problem with this data is not the complexity of the processes involved, but rather the quantity of data and the rate of collecting new data. The following two examples are slightly illustrative of this phenomenon. * In April 2009, _EBay_ was using two Data Warehouses, namely _Teradata_ and _Greenplum_, the former having 6.5 PB of data in form of 17 trillion records already stored, and collecting more than 150 billion new records/day, leading to an ingest rate well over 50 TB/day [2]. * In May 2009, _Facebook_ estimates an amount of 2.5 PB of user data, with more than 15 TB of new data per day [3]. As another matter of question, the presence of _graph-based data structures_ occurs almost everywhere starting with _social networks_ like _Facebook_[4], _MySpace_[5] and _NetFlix_[6], and ending with _transportation routes_ or _Internet infrastructure architectures_. These graphs keep growing in size and there are several new things that people would like to infer from the many facets of information stored in these data structures. Graphs can have billions of vertices and edges. Citation graphs, affiliation graphs, instant messenger graphs, phone call graphs and so forth, are part of the so-called _social network analysis and mining_ initiative. Some recent works show that, despite the previously supposed sparse nature of those graphs, their density increases over time [7; 8]. All considering, these trends tend towards the so-called _big Web data_ (e.g., [9; 10]), the transposition of big data on the Web. On the other hand, _Semantic Web technologies_ allow us to effectively support analysis of large-scale distributed data sets by means of the well-known _Resource Description Framework_ (RDF) model [11], which, obviously represents data via a _graph-shaped approach_. As a consequence, in the Semantic Web initiative, the most prominent kind of graph data are represented by _RDF graphs_. This opens the door to a wide family of database-like applications, such as _keyword search over RDF data_ (e.g., [12]). While RDF graphs offer a meaningful data model for successfully representing, analyzing and mining large-scale graph data, the problem of _efficiently processing RDF graphs_ is still an open issue in database research (e.g., [13; 14; 15]). Following this main consideration, in this paper, we focus on _the problem of computing traversals of RDF graphs_, being computing traversals of such graphs very relevant in this area, e.g., for RDF graph analysis and mining over large-scale data sets. Our approach adopts the _Breadth First Search_ (BFS) strategy for visiting (RDF) graphs to be decomposed and processed according to the MapReduce framework. This with the goal of taking advantages from the powerful run-time support offered by MapReduce, hence reducing the computational overheads due to manage large RDF graphs efficiently. This approach is conceptually-sound, as similar initiatives have been adopted in the vast of viable solutions to _the problem of managing large-scale sensor-network data over distributed environments_ (e.g., [16; 17]), like for the case of Cloud infrastructures and their integration with sensor networks.