USING VERTEX SELF-INFORMATION SCORES FOR VERTICES IN AN ENTITY GRAPH TO DETERMINE WHETHER TO PERFORM ENTITY RESOLUTION ON THE VERTICES IN THE ENTITY GRAPH

• US 20160012149A1
• Filed: 07/09/2014
• Published: 01/14/2016
• Est. Priority Date: 07/09/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Muchinsky, Craig W., Schumacher, Scott, Thorne, Edward B.
• Granted Patent: US 9,946,808 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Provided are a computer program product, system, and method to determine whether to perform entity resolution on vertices in an entity graph. A determination is made of pairs of records in a database having a relationship value satisfying a threshold. An entity relationship graph has a vertex for each of the records of the pairs and an edge between two vertices. Each vertex has a self-information score based on content in the record, an initial unique entity identifier, and an entity information score. For each subject vertex of the vertices, a determination is made of a target vertex directly connected to the subject vertex that has a highest entity information score and whether to set the subject vertex entity identifier and entity information score to the entity identifier and entity information score of the target vertex based on the target vertex self-information score.

Claims

1. A computer program product for entity resolution of records in a database, the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that when executed performs operations, the operations comprising:

determining pairs of records in the database having a relationship value satisfying a threshold;

generating an entity relationship graph having a vertex for each of the records of the pairs and an edge for each of the determined pairs between two vertices representing records in one of the determined pairs, wherein each vertex is associated with a self-information score based on content in the record represented by the vertex and is assigned an initial unique entity identifier and an entity information score;

for each subject vertex of the vertices, performing;

determining a target vertex directly connected to the subject vertex that has a highest entity information score of at least one vertex directly connected to the subject vertex that has an entity information score greater than the entity information score of the subject vertex; and

determining whether to set the subject vertex entity identifier and entity information score to the entity identifier and entity information score of the target vertex based on the target vertex self-information score.

2. The computer program product of claim 1, wherein setting the entity identifier and entity information score of the subject vertex to those of the target vertex is performed in response to determining that the self-information score of the target vertex and the subject vertex entity information score satisfies a comparison criteria.

3. The computer program product of claim 2, wherein the comparison criteria comprises determining whether the target vertex self-information score is less than the subject vertex entity information score minus a threshold, wherein the entity identifier and entity information score of the subject vertex is set to those of the target vertex when the target vertex self-information score is not less than the subject vertex entity information score minus the threshold.

4. The computer program product of claim 2, wherein a group of vertices sharing a common entity identifier and common entity information score change their entity identifier and entity information to that of a target vertex when the target vertex comprises the best directly connected vertex having the self-information score satisfying the comparison criteria.

5. The computer program product of claim 1, wherein the operations further comprise:

sending, by each of the vertices, a message to a directly linked vertex on one of the edges of the vertex indicating a vertex identifier, vertex self-information score, the entity identifier, and the entity information score for the vertex; and

receiving, by each of the vertices, the message from each directly linked vertex, wherein the receiving vertex comprises the subject vertex and the sending vertex the target vertex, wherein the setting of the entity identifier and entity information score of the receiving vertex to that of the sending vertex is based on the information in the message from the sending vertex.

6. The computer program product of claim 1, wherein the operations further comprise:

sending, by the vertices having changed their entity identifier and entity information score information, a new message to each directly linked vertex on one of the edges of the vertex indicating a vertex identifier, vertex self-information score, and the updated entity identifier and the entity information score; and

receiving, by each of the vertices, the new message from each directly linked vertex that changed its entity information, wherein each of the receiving vertices performs an additional iteration of the operations of determining the target vertex and determining whether to set the receiving vertex entity identifier and entity information score to the entity identifier and entity information of the sending vertex comprising the target vertex.

7. The computer program product of claim 1, wherein the operations further comprise:

initiating an unlinking procedure in response to determining that information has changed for one of the records represented by a vertex in the graph, wherein all the vertices have a common entity identifier and common entity information score;

determining whether all the vertices having the common entity identifier are linked directly or indirectly to an entity vertex comprising the vertex having the information score equal to the common entity information score; and

unlinking any of the vertices having the common entity identifier that are not linked directly or indirectly to the center vertex.

8. The computer program product of claim 7, wherein the vertices are unlinked by assigning a new unique entity identifier to each of the vertices that are not linked directly or indirectly to the center vertex.

9. The computer program product of claim 7, wherein the determining whether all the vertices having the common entity identifier are directly or indirectly linked to the entity vertex comprises:

sending the entity vertex a list of all the vertices having the common entity identifier;

removing, by the entity vertex, its vertex from the list;

sending, by the entity vertex, a message to each directly connected vertex in the graph indicating each of the vertices that have been sent the message;

replying, by each of the vertices receiving the message, to the entity vertex;

removing, by the entity vertex, the replying vertices from the list;

forwarding, by each of the vertices receiving the message, the message to directly connected vertices that have not already received the message to cause them to reply to the entity vertex to enable the entity vertex to remove them from the list, wherein the list resulting from the replies from all the vertices that have been forwarded the message indicates vertices having the common entity identifier that are not directly or indirectly linked to the center vertex.

10. A system for entity resolution of records in a database,

comprising:

a processor;

a computer readable storage medium having computer readable program code embodied therein that when executed by the processor performs operations, the operations comprising;

determining pairs of records in the database having a relationship value satisfying a threshold;

generating an entity relationship graph having a vertex for each of the records of the pairs and an edge for each of the determined pairs between two vertices representing records in one of the determined pairs, wherein each vertex is associated with a self-information score based on content in the record represented by the vertex and is assigned an initial unique entity identifier and an entity information score, which is initially set to the information score of the vertex;

for each subject vertex of the vertices, performing;

determining a target vertex directly connected to the subject vertex that has a highest entity information score of at least one vertex directly connected to the subject vertex that has an entity information score greater than the entity information score of the subject vertex; and

determining whether to set the subject vertex entity identifier and entity information score to the entity identifier and entity information score of the target vertex based on the target vertex self-information score.

11. The system of claim 10, wherein setting the entity identifier and entity information score of the subject vertex to those of the target vertex is performed in response to determining that the self-information score of the target vertex and the subject vertex entity information score satisfies a comparison criteria.

12. The method of claim 11, wherein the comparison criteria comprises determining whether the target vertex self-information score is less than the subject vertex entity information score minus a threshold, wherein the entity identifier and entity information score of the subject vertex is set to those of the target vertex when the target vertex self-information score is not less than the subject vertex entity information score minus the threshold.

13. The system of claim 11, wherein a group of vertices sharing a common entity identifier and common entity information score change their entity identifier and entity information to that of a target vertex when the target vertex comprises the best directly connected vertex having the self-information score satisfying the comparison criteria.

14. The system of claim 10, wherein the operations further comprise:

sending, by the vertices having changed their entity identifier and entity information score information, a new message to each directly linked vertex on one of the edges of the vertex indicating a vertex identifier, vertex self-information score, and the updated entity identifier and the entity information score; and

receiving, by each of the vertices, the new message from each directly linked vertex that changed its entity information, wherein each of the receiving vertices performs an additional iteration of the operations of determining the target vertex and determining whether to set the receiving vertex entity identifier and entity information score to the entity identifier and entity information of the sending vertex comprising the target vertex.

15. The system of claim 10, wherein the operations further comprise:

initiating an unlinking procedure in response to determining that information has changed for one of the records represented by a vertex in the graph, wherein all the vertices have a common entity identifier and common entity information score;

determining whether all the vertices having the common entity identifier are linked directly or indirectly to an entity vertex comprising the vertex having the information score equal to the common entity information score; and

unlinking any of the vertices having the common entity identifier that are not linked directly or indirectly to the center vertex.

21. The system of claim 10, wherein the operations further comprise:

sending, by each of the vertices, a message to a directly linked vertex on one of the edges of the vertex indicating a vertex identifier, vertex self-information score, the entity identifier, and the entity information score for the vertex; and

receiving, by each of the vertices, the message from each directly linked vertex, wherein the receiving vertex comprises the subject vertex and the sending vertex the target vertex, wherein the setting of the entity identifier and entity information score of the receiving vertex to that of the sending vertex is based on the information in the message from the sending vertex.

22. The system of claim 15, wherein the vertices are unlinked by assigning a new unique entity identifier to each of the vertices that are not linked directly or indirectly to the center vertex.

23. The system of claim 15, wherein the determining whether all the vertices having the common entity identifier are directly or indirectly linked to the entity vertex comprises:

sending the entity vertex a list of all the vertices having the common entity identifier;

removing, by the entity vertex, its vertex from the list;

sending, by the entity vertex, a message to each directly connected vertex in the graph indicating each of the vertices that have been sent the message;

replying, by each of the vertices receiving the message, to the entity vertex;

removing, by the entity vertex, the replying vertices from the list;

forwarding, by each of the vertices receiving the message, the message to directly connected vertices that have not already received the message to cause them to reply to the entity vertex to enable the entity vertex to remove them from the list, wherein the list resulting from the replies from all the vertices that have been forwarded the message indicates vertices having the common entity identifier that are not directly or indirectly linked to the center vertex.

16-20. -20. (canceled)