A Directed Graph Reachability Linked List Generation and Query Method in Parallel Environment

Abstract

The invention belongs to the field of data processing for large graphs and relates to a generation and search method for reachability chain list of a directed graph in the parallel environment. The method includes distributing the directed graph to every processor which stores nodes in the graph and sub-nodes corresponding to the nodes; compressing graph data split to the processors; calculating a backbone node reachability code of a backbone graph; building a chain index; building a skip list on the chain index; allowing data communication among the processors; allowing each processor to send skip list information to other processors; allowing each processor to upgrade own skip list information; and building a reachability index of a total graph. Through use of graph reachability compression technology in the parallel environment, the size of graph data is greatly reduced, system computing load is reduced, and a system can process the graph data on a larger scale. The method has the advantages that the speed of reading data from a disk is higher, search speed is indirectly increased, accuracy of search results is guaranteed, and network communication cost and search time are reduced greatly for a parallel computing system during searching.

Description

technical field [0001] The invention belongs to the field of large graph data processing, and in particular relates to a method for generating and querying a directed graph reachability linked list in a parallel environment. Background technique [0002] Graphs are an important data structure in the computer field. Nowadays, a large number of information processing uses graphs as data structures, and the demand for various operations on graphs continues to increase. As a basic operation on graphs, the graph accessibility query operation has important applications in semantic networks, biological networks, and social networks. At the same time, graph accessibility is also a basic algorithm for advanced applications of graph data. The definition of the accessibility of a graph is as follows. For a directed graph G, the node set on the graph is set to V, and the edge set is set to E. The reachability calculation of a directed graph is to judge the nodes of a directed graph Whe...

AI Technical Summary

Problems solved by technology

If the precomputation cost of these methods is high, the obtained results will cover more accessibility information and the index will be more detailed; the corresponding query process time cost will be relatively small, and the query calculation speed will be relatively fast, but this is also It will cause the problem that the index is too large and takes up too much space

However, if there are too many update operations on the graph, and the index design cannot incrementally maintain the reachability index of the graph, the precomputation cost of this solution exceeds expectations—the entire graph data needs to be recalculated every time an update is performed. The calculated index is usually linearly related to the edge of the graph because the information is relatively complete, and the calculation cost is high, and the index storage cost is also high; if a lightweight index is used for judgment, the index calculation process is relatively short, but the query process is due to the reason Some indexes do not cover the data on the entire graph, so a large amount of data in the original graph needs to be searched

Images