Patent ID: 6985890

Claim:
A graph structured data processing method for extracting a frequent graph that has a support level equal to or greater than a minimum support level, from a graph database constituting a set of graph structured data, said method comprising: changing the order of vertex labels and edge labels and extracting frequent graphs in order of size; coupling two size k frequent graphs of size k that match the conditions: i) between the matrixes X k and Y k elements other than the k-th row and the k-th column are equal, ii) between the graphs G(X k ) and G(Y k ) which are represented by adjacency matrixes X k and Y k , vertex levels other than the k-th vertex are equal and the order of the level of said k-th vertex of said graph G(X k ) is equal to or lower than the order of the level of the k-th vertex of said graph G(Y k ); iii) between the graphs G(X k ) and G(Y k ) the vertex level at the k-th vertex is equal and the code of said adjacency matrix X k is equal to or smaller than the code of said adjacency matrix Y k ; and iv) said adjacency matrix X k is a canonical form; and returning a set F k of adjacency matrixes of a frequent graph having a size k, where k is a natural number, and a set C k+1 of adjacency matrixes c k+1 of candidate frequent graphs having a size k+1; the obtained graph as candidate of frequent graphs; when said adjacency matrix c′ k+1 is a frequent graph as the result of scanning of said graph database, adding, to a set F k+1 of adjacency matrixes of a frequent graph having said size k +1 , said adjacency matrix c′ k+1 and an adjacency matrix c k+1 that represents the same structure as a graph expressed by said adjacency matrix c′ k+1 , obtaining a candidate frequent graph from a set of adjacency matrixes that represent a candidate of frequent graph, where the return value is a set of adjacency matrixes that represent a candidate of frequent graph for which all the induced subgraphs are frequent graphs; deleting, from said set C k+1 , said adjacency matrix c k+1 of a candidate frequent graph that includes a less frequent graph as an induced subgraph having said size k; selecting only one adjacency matrix c′ k+1 from a sub-set of adjacency matrixes c k+1 that represent the same graph; normalizing the candidate frequent matrix and returning a canonical form from among adjacency matrixes that represent a size k candidate of frequent graph; and extracting a frequent graph.