A distributed computation of the shortest path in large-scale road network

被引:1
作者
Zhang, Dongbo [1 ]
Zhang, Wei [2 ]
Yang, Rui [1 ]
Guo, Mamman [3 ]
Chen, Chien-Ming [4 ]
机构
[1] Guangdong Inst Intelligent Mfg, Guangdong Key Lab Modern Control Technol, Guangzhou, Peoples R China
[2] Natl Radio & Televis Adm, Acad Broadcasting Sci, Beijing 100866, Peoples R China
[3] Natl Chiao Tung Univ, Inst Management, Hsinchu 30050, Taiwan
[4] Shandong Univ Sci & Technol, Coll Comp Sci & Engn, Qingdao, Shandong, Peoples R China
关键词
The shortest path; MapReduce model; Parallel computing; Road network; ENCRYPTION; MAPREDUCE;
D O I
10.1007/s12652-019-01615-5
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The shortest path solution in large-scale road network has become a hot topic. How to find a shortest path efficiently and quickly in a road network is very difficult. With the development of parallel computing and the improvement of Hadoop ecology, it makes it easier to solve the problem by using the MapReduce model in the Hadoop ecosystem. In this paper, we propose a improved shortest path algorithm based on cloud computing in large data architecture. The principle of this algorithm is to divide the whole large-scale road network into small-scale road network according to a certain distance, calculate the shortest path of small-scale road network, and finally combine these shortest paths into the shortest path of large-scale road network. The experimental results show that the algorithm has good results, especially with the increase of computing nodes, and the efficiency of calculation is higher.
引用
收藏
页数:16
相关论文
共 41 条
[1]   An Iterative MapReduce Based Frequent Subgraph Mining Algorithm [J].
Bhuiyan, Mansurul A. ;
Al Hasan, Mohammad .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2015, 27 (03) :608-620
[2]  
Broumi Said, 2017, Applied Mechanics and Materials, V859, P59, DOI 10.4028/www.scientific.net/AMM.859.59
[3]   Optimal Allocation of Protective Resources in Shortest-Path Networks [J].
Cappanera, Paola ;
Scaparra, Maria Paola .
TRANSPORTATION SCIENCE, 2011, 45 (01) :64-80
[4]  
Cardona María J, 2017, Inf. tecnol., V28, P125, DOI 10.4067/S0718-07642017000400015
[5]  
Chedjou JC, 2014, COMM COM INF SC, V438, P227
[6]   Attacks and solutions on a three-party password-based authenticated key exchange protocol for wireless communications [J].
Chen, Chien-Ming ;
Wang, King-Hang ;
Yeh, Kuo-Hui ;
Xiang, Bin ;
Wu, Tsu-Yang .
JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING, 2019, 10 (08) :3133-3142
[7]   A Secure Authentication Protocol for Internet of Vehicles [J].
Chen, Chien-Ming ;
Xiang, Bin ;
Liu, Yining ;
Wang, King-Hang .
IEEE ACCESS, 2019, 7 :12047-12057
[8]   Runtime model based approach to IoT application development [J].
Chen, Xing ;
Li, Aipeng ;
Zeng, Xue'e ;
Guo, Wenzhong ;
Huang, Gang .
FRONTIERS OF COMPUTER SCIENCE, 2015, 9 (04) :540-553
[9]   Intelligent radioactive waste process cloud-based system for nuclear power plant decommissioning [J].
Chen Y.-C. ;
Sun H.-M. ;
Chen R.-S. ;
Yeh J.-H. ;
Fan X. ;
Chou I.-H. .
Journal of Ambient Intelligence and Humanized Computing, 2024, 15 (03) :1801-1811
[10]   Single- and dual-arm motion planning with heuristic search [J].
Cohen, Benjamin ;
Chitta, Sachin ;
Likhachev, Maxim .
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2014, 33 (02) :305-320