Fast Query Algorithm And Parallel Optimization Of The Widest Path On Dynamic Big Graphs

As a data structure,graph is widely used in practical applications,such as road traffic graph,social network graph,biological network graph and so on.Many real problems can be abstracted as graph problems,and the widest path query problem is a basic problem in graph.Due to the high time complexity,traditional query algorithms cannot meet the needs of intensive query on large graph.In order to support the fast query of the widest path on large graph,a pruned widest path algorithm(PWPL)is proposed.But the real world large graph is always in change with time.The index constructed by PWPL algorithm will be invalid with the dynamic change of the graph,and the time cost of reconstructing index is huge.Therefore,PWPL algorithm cannot solve the problem of the widest path fast query on dynamic large graph.Through the observation and analysis of the relationship between the dynamic change of graph and the widest path index,it is found that: 1)the change of graph can be divided into a variety of cases.In many cases,the change of the graph does not affect the widest path between any two vertices in the graph,so that it will not affect the 2 hop index.2)Suppose that the change of graph affects widest paths.Compared with the widest path of all vertex pairs,only a few of the widest paths are affected due to the change of graph.The indexes corresponding to the changed widest path are also invalid,and most of the indexes are still valid.Based on the above observation,in order to solve the problem that the static index algorithm cannot be applied to the dynamic graph,a dynamic pruned widest path algorithm(DPWPL algorithm)is designed by using the index location technology to realize the fast update of the two hop index.The advantages of the algorithm are as follows: 1)an accurate filtering mechanism is designed to filter the graph changes that do not affect the index.2)The index is divided according to the rounds.By accurately locating the rounds corresponding to the invalid index,part of the index is updated to avoid the recalculation of the valid indexes.In order to solve the problem of large time cost in index construction process,a parallel pruned widest labeling algorithm(PPWPL algorithm)is studied and designed to realize the parallelization of index construction process,and a dynamic task scheduling strategy is designed to further reduce the time cost of index construction.Experimental results show that DPWPL algorithm can achieve millisecond level index update response for edge insertion and second level index update response for edge deletion.PPWPL algorithm can reduce the time cost of index construction by up to 80%.