Patent ID: 7933915
Filing Date: 2011-04-26
Classification: G06F

Abstract:
1. A computer-implemented method for conducting a database graph query, comprising: (a) obtaining a first database graph and a second database graph, wherein the first database graph and second database graph each have two or more vertices and one or more edges; (b) mapping the first database graph to the second database graph, wherein: (ii) each edge in the first database graph has a corresponding edge in the second database graph; wherein the mapping step (b) comprises: (1) computing an initial similarity matrix for the first database graph and the second database graph, wherein each entry of the similarity matrix represents a weight similarity of each vertex of the first database graph to each vertex of the second database graph; (2) creating a priority queue comprised of vertex pairs based on the weight similarity, wherein each vertex pair comprises a vertex from the first database graph and a most similar vertex from the second database graph based on the weight similarity; (3) processing the priority queue by: (c) creating a graph closure tree comprised of a union of the first database graph and the second database graph based on the mapping, wherein each node of the graph closure tree comprises a graph closure of the node's children and each child of a leaf node comprises a database graph; and (d) conducting a graph query based on the graph closure tree.