Parallel Implementation of Single-Source Shortest Path Algorithm Based on Haloop

Abstract:

As a typical problem of graph theory, Single-Source Shortest Path(SSSP) has a wide range of applications and research. The traditional MapReduce framework such as Hadoop has been applied to SSSP problem. However, in this way, it may need writing and reading the disk frequently, transmitting data largely, beacuse of SSSP’s iterative. Haloop is a parallel programming framework which makes an improvement based on Hadoop framework, and adapts itself to iterative programming. Hence, this article represents the SSSP problem with an iterative way firstly, and then we put forward the implementation mechanism of SSSP algorithm based on Haloop. Though testing and analyzing, the implementation based on Haloop obviously improves the efficiency of program execution, compared with the traditional realization mechanism.

• Periodical: Applied Mechanics and Materials (Volumes 220-223)
• Pages: 2428-2432
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.220-223.2428
• Online since: November 2012
• Authors: Yuan Sheng Lou, Wen Yuan Zhang, Feng Xu, Yu Wang, Sheng Chen
• Keywords: Hadoop, Haloop, MapReduce, SSSP

References

[1] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, (1959), p.269–271.

DOI: 10.1007/bf01386390

[2] Spurr A.P. A low-viscosity epoxy resin embedding medium for electron microscopy(1969). Res 26, 31–43.

DOI: 10.1016/s0022-5320(69)90033-1

[3] Bellman, Richard. "On a routing problem". Quarterly of Applied Mathematics 16(1958): 87–90.

[4] DuanFanding. A Faster Algorithm for Shortest-Path──SPFA[J]. Journal of Southwest JiaoTong University. 1994-02.

[5] Jeffrey Dean, Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, pp.10-10, December 06-08, 2004, San Francisco, CA.

[6] S. J. Plimpton and K. D. Devine. Mapreduce in MPI for large-scale graph algorithms. (to appear in a special issue of ) Parallel Computing,2011.

DOI: 10.1016/j.parco.2011.02.004

[7] Ling Yang, Renfa Li, Zhuo Tang. Research on the Single Source Shortest Path Algorithm Using MapReduce[J]. Microcomputer Information. 2011.12

[8] Karthik Kambatla, Naresh Rapolu, Suresh Jagannathan, Ananth Grama. Asynchronous algorithms in MapReduce. In Proceedings of Cluster (2010).

DOI: 10.1109/cluster.2010.30

[9] Ge Yu, Yu Gu. Large Scale Graph Data Processing on Cloud Computing Environments. Chinese Journal of Computers, 2011,34(10);1753-1767.

DOI: 10.3724/sp.j.1016.2011.01753

[10] Y. Bu, B. Howe, M. Balazinska, and M. Ernst. HaLoop: Efficient iterative data processing on large clusters. PVLDB, 3(1):285--296, 2010.

DOI: 10.14778/1920841.1920881

[11] Hadoop[EB/OL].http://hadoop.apache.org/,2009.

[12] Tom White. Hadoop: The Definitive Guide[M]. O'Reilly Media, Inc. 2009.

[13] Sanjay Ghemawat,Howard Gobioff ,and Shun-Tak Leung. The Google file system.19th ACM Symposium on Operating Systems Principles,Lake George,NY,2003.

DOI: 10.1145/945445.945450