DiffPageRank: an efficient differential PageRank approach in MapReduce

Unstructured big data processing requires efficient computational styles to rapidly analyze continuously changing data. Incremental processing is a promising technique to update search results without re-computing the whole process. One of the most important mining algorithms is PageRank which necessitates incremental processing and iterative computations to keep the mining results up-to-date. In this paper, a light and efficient PageRank algorithm is proposed using differential dataflow in the MapReduce programming style named DiffPageRank. The innovation of the proposed approach is investigated from two points of view: (1) the updating state is dependent on a partial order of changes in DiffPageRank computing, while the changes are applied based on complete order sequences in the standard incremental computing; and (2) in DiffPageRank, a set of updates rebuilds each version, while in the incremental systems, every single update continually bring up-to-date the current version state. DiffPageRank is compared with two other implementations of PageRank including standard and incremental PageRank in MapReduce in terms of processing time, CPU utilization and update speed of data mining results. The results show that if the changes on the input data are large, the efficiency of the differential method will considerably increase in terms of time than the standard and incremental PageRank approaches up to 61% and 86%, respectively. DiffPageRank is also compared with two state-of-the-art incremental graph processing benchmarks on Orkut and Twitter datasets in terms of execution time and the number of updates. The experimental comparisons on benchmark datasets show that our method reduces the number of updates and total execution time by using the differential MapReduce approach.