Graph based resolution of matching items in data sources

• US 10,268,735 B1
• Filed: 12/27/2016
• Issued: 04/23/2019
• Est. Priority Date: 12/29/2015
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: White, Nicholas, Xu, Han
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US15/391,532
• Time in Patent Office: 847 Days
• Field of Search: 707749
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

In an embodiment, a computer-implemented method comprises calculating a first relational classification score for a first node in a first graph; calculating a second relational classification core for a second node in a second graph; calculating a relational classification matching score for the first node and the second node that is based upon on the first relational classification score and the second relational classification score; calculating a composite score based at least upon the relational classification matching score; generating a canonical tuple that represents a match between the first node and the second node in response to determining that the composite score is equal to or greater than a specified threshold score value.

Claims

1. A method comprising:

calculating a first relational classification score for a first node in a first graph that is digitally stored in computer memory, the first graph representing a first digitally stored database, the first node representing an element of the first digital stored database, and the first relational classification score being a measure of a logical position of the first node in the first graph;

calculating a second relational classification score for a second node in a second graph that is digitally stored in computer memory, the second graph representing a second digitally stored database, the second node representing an element of said second digitally stored database, and the second relational classification score being a measure of a logical position of said second node in the first graph;

calculating a relational classification matching score for the first node and the second node that is based upon on the first relational classification score and the second relational classification score, the relational classification matching score representing a similarity in location in the graphs of said first node and said second node;

calculating a composite score based at least upon the relational classification matching score, the composite score being a measure of quality of match of said first node and said second node;

generating a canonical tuple that represents a match between the first node and the second node in response to determining that the composite score is equal to or greater than a specified threshold score value;

storing said canonical tuple as a merged digitally stored database that is created to resolve said first node and said second node;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

calculating the first relational classification score based in part on one or more of;

ancestors or descendants of the first node;

edit distance of the path from a root node of the first graph to the first node;

calculating the second relational classification score based in part on one or more of;

ancestors or descendants of the second node;

edit distance of the path from a root node of the second graph to the second node.

3. The method of claim 1, further comprising calculating the composite score based on one or more of:

an entity identifier edit distance score;

a property score;

a known synonym score;

a known abbreviation score.

4. The method of claim 1, further comprising calculating each relational classification score as a measure of a logical position of the first node, and based upon relationships to other nodes by calculating a distance of the first node to a root node of the first graph, counting proximate nodes to which the first node is joined as parent nodes, grandparent nodes, child nodes, or grandchild nodes, and determining which proximate nodes match the first node in node identifiers, properties or attributes.

5. The method of claim 1, wherein the first graph has been generated based upon database records of a first database that contains the first node, and wherein the second graph has been generated based upon other database records of a second, different database that contains the second node.

6. The method of claim 1, further comprising calculating the relational classification matching score for the first node and the second node as a representation of similarity between the first node and the second node based upon a first similarity of the respective locations of the nodes, a second similarity of all proximate nodes that are joined respectively to the first node and the second node, and a third similarity of numbers of child nodes of the first node and the second node.

7. The method of claim 1, further comprising calculating the composite score as a measure of quality of match of the first node and the second node, using the relational classification matching score and also using one or more of:

a node identifier edit distance matching score, property matching score, known synonym matching score, or known abbreviation matching score.

8. The method of claim 1, further comprising:

creating and storing, in computer memory, an output graph comprising the first graph, the second graph, and the canonical tuple, wherein the canonical tuple comprises a first edge and a second edge that respectively link the canonical tuple to the first node and the second node when the composite score exceeds a threshold value;

causing displaying the output graph using a computer display device in a graphical user interface that visually depicts one or more nodes, edges, and canonical tuples of the output graph.

9. The method of claim 8, further comprising partitioning the output graph into two or more clusters of nodes, in which all nodes of a particular cluster among the two or more clusters are directly or transitively connected by edges of the output graph.

10. A data processing system, comprising:

one or more processors;

one or more non-transitory machine readable storage media storing sequences of instructions which, when executed using the one or more processors, cause the one or more processors to perform;

calculating a first relational classification score for a first node in a first graph, wherein said first graph represents a first digital stored database, said first node represents an element of said first digital stored database, and said first relational classification score is a measure of a logical position of said first node in the first graph;

calculating a second relational classification score for a second node in a second graph, wherein said second graph represents a second digitally stored database and said second node represents an element of said second digital stored database, and said second relational classification score is a measure of a logical position of said second node in the first graph;

calculating a relational classification matching score for the first node and the second node that is based upon on the first relational classification score and the second relational classification score, wherein said relational classification matching score represents a similarity in location of said first node and said second node;

calculating a composite score based at least upon the relational classification matching score, wherein said composite score is a measure of quality of match of said first node and said second node;

generating a canonical tuple that represents a match between the first node and the second node in response to determining that the composite score is equal to or greater than a specified threshold score value;

storing said canonical tuple as a merged digital stored database that is created to resolve said first node and said second node;

wherein the method is performed by one or more computing devices.

11. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform:

calculating the first relational classification score based in part on one or more of;

ancestors or descendants of the first node;

edit distance of the path from a root node of the first graph to the first node;

calculating the second relational classification score based in part on one or more of;

ancestors or descendants of the second node;

edit distance of the path from a root node of the second graph to the second node.

12. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform calculating the composite score based on one or more of:

an entity identifier edit distance score;

a property score;

a known synonym score;

a known abbreviation score.

13. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform calculating each relational classification score as a measure of a logical position of the first node, and based upon relationships to other nodes by calculating a distance of the first node to a root node of the first graph, counting proximate nodes to which the first node is joined as parent nodes, grandparent nodes, child nodes, or grandchild nodes, and determining which proximate nodes match the first node in node identifiers, properties or attributes.

14. The computer system of claim 10, wherein the first graph has been generated based upon database records of a first database that contains the first node, and wherein the second graph has been generated based upon other database records of a second, different database that contains the second node.

15. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform calculating the relational classification matching score for the first node and the second node as a representation of similarity between the first node and the second node based upon a first similarity of the respective locations of the nodes, a second similarity of all proximate nodes that are joined respectively to the first node and the second node, and a third similarity of numbers of child nodes of the first node and the second node.

16. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform calculating the composite score as a measure of quality of match of the first node and the second node, using the relational classification matching score and also using one or more of:

a node identifier edit distance matching score, property matching score, known synonym matching score, or known abbreviation matching score.

17. The computer system of claim 10, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform:

creating and storing, in computer memory, an output graph comprising the first graph, the second graph, and the canonical tuple, wherein the canonical tuple comprises a first edge and a second edge that respectively link the canonical tuple to the first node and the second node when the composite score exceeds a threshold value;

causing displaying the output graph using a computer display device in a graphical user interface that visually depicts one or more nodes, edges, and canonical tuples of the output graph.

18. The computer system of claim 17, further comprising sequences of instructions which when executed by the one or more processors cause the one or more processors to perform partitioning the output graph into two or more clusters of nodes, in which all nodes of a particular cluster among the two or more clusters are directly or transitively connected by edges of the output graph.

19. A computer-implemented data processing method for determining whether a first node, which is associated with a first entity of a first digitally stored database, matches and represents a same object as a second node, which is associated with a second entity of a second, different digitally stored database, the method comprising:

calculating a first relational classification score for the first node in a first graph that has been created and stored in a computer memory based upon the first entity of the first digitally stored database and calculating a second relational classification score for the second node in a second graph that has been created and stored in the computer memory based upon the second entity of the second digitally stored database, including calculating each relational classification score as a measure of a logical position of the first node, and based upon relationships to other nodes by calculating a distance of the first node to a root node of the first graph, counting proximate nodes to which the first node is joined as parent nodes, grandparent nodes, child nodes, or grandchild nodes, and determining which proximate nodes match the first node in node identifiers, properties or attributes;

calculating a relational classification matching score for the first node and the second node that is based upon on the first relational classification score and the second relational classification score, as a representation of similarity between the first node and the second node based upon a first similarity of the respective locations of the nodes, a second similarity of all proximate nodes that are joined respectively to the first node and the second node, and a third similarity of numbers of child nodes of the first node and the second node;

calculating a composite score as a measure of quality of match of the first node and the second node, using the relational classification matching score and also using one or more of;

a node identifier edit distance matching score, property matching score, known synonym matching score, or known abbreviation matching score;

generating a canonical tuple that represents a match between the first node and the second node in response to determining that the composite score is equal to or greater than a specified threshold score value.

20. The method of claim 19, further comprising:

creating and storing, in computer memory, an output graph comprising the first graph, the second graph, and the canonical tuple, wherein the canonical tuple comprises a first edge and a second edge that respectively link the canonical tuple to the first node and the second node when the composite score exceeds a threshold value;

partitioning the output graph into two or more clusters of nodes, in which all nodes of a particular cluster among the two or more clusters are directly or transitively connected by edges of the output graph;

causing displaying the output graph using a computer display device in a graphical user interface that visually depicts one or more nodes, edges, and canonical tuples of the output graph.