ScaDiGraph: A MapReduce-based ...

چکیده مقاله

Graph data contain a large volume of information, which must be analysed. A method is required that can quickly process the information in distributed and scalable architectures. Single node methods are not suitable because they cannot process large amounts of information on their processors and memories. Problems encountered in distributed environments must also be addressed. These include graph division problems, algorithm division problems, exchange states among hardware nodes, and network traffic. In this paper, a scalable and distributable MapReduce-based method, ScaDiGraph, is proposed that makes hardware nodes independent. With this method, each hardware node can process a subgraph without any information from the other nodes. ScaDiGraph converts iterative graph problems, such as the All Pairs Shortest Path (APSP), pattern matching, and loop detection, into non-iterative problems and makes them suitable for the MapReduce architecture. In the present paper, ScaDiGraph is used to solve APSP, loop detection, and pattern matching problems, and the results are compared with those obtained with other MapReduce- and non-MapReduce-based methods. The results show that when applying ScaDiGraph on graph data, which causes simultaneous algorithm execution on each node, the execution time decreases in comparison with the prominent existing methods.