Publication Type : Conference Paper
Publisher : 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI)
Source : 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, Udupi, India (2017)
Url : https://ieeexplore.ieee.org/abstract/document/8126138
Keywords : All pair shortest path, Dikjstra's algorithm, distributed system, transitive closure
Campus : Amritapuri
School : Department of Computer Science and Engineering, School of Engineering
Department : Computer Science, Sciences
Verified : Yes
Year : 2017
Abstract : Due to the explosion of data from various sources, data analytics is found to be difficult using the CPU alone. For huge networks, the most popular graph algorithms using a single processor failed to accomplish this task. Hence the need of algorithms that have higher processing capabilities became dominant. Graph analytics is gaining importance in the realm of data analysis due to the advantages over other conventional analytical methods. All pair shortest path problem or path-finding problem has applications in various fields. Finding the all pair shortest path in a graph is computationally complex and time consuming in the case of large networks. In this paper, we propose a map reduce approach using the in-memory computation for finding the all pair shortest path using the transitive closure property and the greedy technique in Dijkstra's single source shortest path method. In order to overcome the scalability issues in the network representation, we use a tuple based network representation. The performance of the proposed method is proved experimentally.
Cite this Research Publication :
S. Vaid, Salih, R., Gayathri, R. G., and Jyothisha J. Nair, “All pair shortest path using distributed architectures”, in 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, 2017