Large-scale graph data processing method based on k<2>-tree and multi-valued decision diagram

Abstract

The invention discloses a large-scale graph data processing method based on a k<2>-tree and a Multi-valued Decision Diagram (MDD). The method comprises the following steps: 1, performing n-bit encoding on a peak of a graph according to the rule of the k<2>-tree, FORMULA, k being greater than or equal to 2; 2, encoding an edge according to a peak code; 3, constructing an MDD structure according to an edge code to obtain a k<2>-MDD structure which corresponds to an oriented graph and contains n variables, wherein the k<2>-MDD structure has the nature of the MDD and is applicable to the simplification rule of the MDD; 4, performing the following basic operation of the graph on the obtained k<2>-MDD structure through logic operation of a symbol decision diagram: edge inquiry, outside adjacent inquiry and calculation of an out degree of the peak, inside adjacent inquiry and calculation of an in degree of the peak, as well as adding and deletion of an edge, and the like. According to the method, the MDD is used for storing graph data, so that isomorphic sub trees in the k<2>-tree are combined, the number of nodes is reduced, and the structure is more compact; the basic operation of the graph is converted into the logic operation, so that the operation is simpler.

Description

technical field [0001] The invention relates to the technical field of large-scale graph data storage and operation, in particular to a k-based 2 Large-Scale Graph Data Processing Methods for Trees and Multivalued Decision Graphs. Background technique [0002] With the development of technologies such as the mobile Internet and the Internet of Things, many new applications generate and accumulate large amounts of data in unprecedented ways and speeds. Among many types of big data, graph data is playing an increasingly important role as a data structure for effectively describing big data. Due to the increasing scale of graph data, it is currently a challenge to realize efficient storage of graph data and efficient operation of graph data. Taking social networks as an example, according to GlobalWebIndex statistics, the number of Facebook users has exceeded 1.1 billion, and each person has more than 100 friends on average. Using an adjacency table to store the relationship ...

AI Technical Summary

Problems solved by technology

[0006] 2)k 2 The tree is only valid for sparse graphs. When the graph becomes dense, since there are fewer 0 nodes that can be compressed in the adjacency matrix, k 2 Tree compactness will also be lower

[0007] 3)k 2 The tree does not involve the representation and operation of dynamic graphs (graphs that need to add or delete vertices, edges, subgraphs, etc.)

[0008] current k 2 The tree graph data compact representation method still lacks the necessary consideration of the structural characteristics of the above graph, and there is still a lot of room for improvement in compactness

Images