Research On Shortest Path Algorithm Of GIS Network Based On Hadoop

As one of the most important spatial analysis functions in GIS,shortest path analysis has been widely used in path navigation,pipe network optimization design and traffic guidance.With the size of the facilities such as traffic network and pipeline network,the scale of spatial network data abstracted by these realistic facilities is gradually becoming massive.How to make a large-scale space network to deal with quickly is the GIS in the shortest path algorithm to face a huge challenge.The shortest path analysis of the GIS platform in the stand-alone environment The situation of the large-scale network data will be less com putationally inefficient and sometimes even cause the GIS software to run to crash.Therefore,the study of the shortest path algorithm of GIS network has practical significance and practical value.Hadoop is one platform of the Cloud computing platform,which in dealing with large data,with high computing efficiency and application of mature,stable advantage.To this end,this paper has in-depth studied and explored the shortest path algorithm which is based on Hadoop and GIS network.(1)This paper studies the storage and management of GIS network vector data in HBase.According to the data structure of GIS network,the storage problem of GIS network under Hadoop is solved by the appropriate HBase table structure design,which creates the prerequisite for the shortest path parallel computation in Hadoop cloud platform.And through the design of the relevant HBase table,to achieve the dynamic weight assignment problem,making the shortest path algorithm can be extended to the optimal path algorithm.(2)This paper designs an algorithm for generating neighbor table based on Map Reduce.The design of the algorithm combines the characteristics of adjacency table structure and the running principle of Map Reduce,and can effectively solve the problem of adjacent table structure generation in large-scale GIS network under Hadoop platform.The adjacency table data structure obtained by the algorithm provides the data structure guarantee for the shortest path algorithm.(3)In this paper,the shortest path parallel algorithm of GIS network based on Hadoop(H_PGNSP)is proposed.In addition to the computational process described above,the algorithm flow includes an improved shortest path algorithm calculation process.The improve dalgorithm is based on Lin J 's breadth of the shortest path parallel algorithm(PBFS_SP)asthe basis of the idea,to improve the design.By constructing the Hadoop cloud platform,the improved algorithm is compared with the PBFS_SP algorithm and the Dijkstra algorithm.Experiments show that the improved algorithm has improved the computational efficien cy of the Dijkstra algorithm when the network size reaches a certain level.In the large-scale network,the algorithm is the most efficient in the three algorithms.(4)Finally,in the simulation of the emergency scenarios,this algorithm H_PGNSP for the development of rescue path.The result of the algorithm can be seamlessly integrated with the relevant GIS platform through GIS technology,and it is easy to realize the spatial visualization of the shortest path.The results show that compared with the stand-alone GIS platform,this algorithm can solve the problem of searching the shortest path of large-scale network.And compared to other parallel shortest path algorithm,this algorithm can be compatible with the relevant GIS platform,in the visualization of space has a certain advantage,efficiency has also been improved.