A multi-mode graph index construction method and system for weak structure correlation

Abstract

The invention discloses a multi-mode graph index construction method and system for weak structure correlation. The method comprises the following steps: 1) reading mode diagrams in a mode diagram setof a target field and generating a mode diagram mark ID for each mode diagram; 2) constructing a pattern graph isomorphism tree: judging every two pattern graphs, and if a sub-graph isomorphism relationship exists between the two pattern graphs, adding a pattern graph isomorphism tree pointing to the pattern graph with the larger scale from the pattern graph with the smaller scale to obtain the pattern graph isomorphism tree of the pattern graph set; 3) performing frequent subgraph mining on the pattern graph isomorphic tree, finding a public pattern graph and adding the public pattern graphinto the pattern graph isomorphic tree; 4) when one sub-pattern graph in the pattern graph isomorphism tree has a plurality of parent pattern graphs, reserving a unique parent pattern graph for the sub-pattern graph, and 5) calculating a minimum spanning tree of the pattern graph isomorphism tree, and carrying out depth-first traversal on the minimum spanning tree to obtain an optimal matching sequence of the pattern graph set.

Description

technical field [0001] The invention relates to a method and system for constructing a multi-mode graph index oriented to weak structural correlation, and belongs to the technical field of computer software. Background technique [0002] With the advent of the era of big data, massive multi-source heterogeneous data from the Internet and life is being generated and accumulated at an unprecedented speed, and there is a close correlation between these data. Data structure is very suitable for characterizing this kind of intrinsically related data. As an important means to realize efficient query on graph data, graph pattern matching is the basic technology of many graph-based data analysis and mining. [0003] Graph pattern matching refers to given a data graph and a specific pattern graph, and finding all matching results in the data graph with the same connection topology of nodes and edges of the pattern graph and the same attributes on the corresponding nodes and edges. W...

AI Technical Summary

Problems solved by technology

For example, the pattern tree algorithm, simply using the subgraph isomorphism method to construct the pattern graph index, has poor adaptability to the pattern atlas with weak correlation, and there are many patterns in the data atlas that have no isomorphic relationship but have common subgraphs Graph pairs, and the association between them cannot be established using only the pattern tree algorithm, this part of the calculation cannot be ignored

[0013] For the shortcomings of the pattern tree, the new improved algorithm utilizes the largest common subgraph between the data atlases, but the algorithm is more dependent on the effect of clustering, and needs to specify the clustering coefficient, which is less scalable for any data set , In addition, the pattern graph calculates the largest common subgraph in pairs, which consumes more time, and does not filter the common subgraph, and it is easy to perform unnecessary subgraph calculations during matching

Images