×

Graph querying, graph motif mining and the discovery of clusters

  • US 7,933,915 B2
  • Filed: 02/27/2007
  • Issued: 04/26/2011
  • Est. Priority Date: 02/27/2006
  • Status: Expired due to Fees
First Claim
Patent Images

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;

    (i) each vertex in the first database graph has a corresponding vertex in the second database graph; and

    (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;

    (i) marking a first vertex pair in the priority queue as matched;

    (ii) assigning a higher similarity weight to unmatched vertex pairs that are neighbors to the first vertex pair;

    (iii) repeating steps (3)(i) and (3)(ii) for each subsequent vertex pair in the priority queue until all vertices in the first database graph have been marked as matched;

    (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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×