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 10,108,746 B2
• Filed: 01/30/2015
• Issued: 10/23/2018
• 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.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US14/610,557
• Publication Number:
  US 20160012151A1
• Time in Patent Office: 1,362 Days
• Field of Search: 707797, 707798, 707748, 707705, 707726, 707737, 707759
• 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 method performed by a computer program executed by a processor to perform entity resolution of records in a database implemented in a computer storage device, 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 self-information score of the vertex; and

determining whether to update the entity information score and entity identifier for each subject vertex of the vertices by performing for each subject vertex of the vertices;

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

setting the subject vertex entity identifier and entity information score to the entity identifier and entity information score of the target vertex in response to a target vertex self-information score satisfying a criteria to perform entity resolution for the record represented by the subject vertex.

2. The method 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 method 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 method 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 the target vertex having the self-information score satisfying the comparison criteria.

5. The method of claim 1, further comprising:

sending, by the vertices having changed their entity identifier and entity information score information, a new message to each directly linked vertex on one edge of the vertex indicating a vertex identifier, vertex self-information score, and the changed 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 a receiving vertex entity identifier and entity information score to the entity identifier and entity information of a sending vertex, of the sending vertices, comprising the target vertex.

6. The method of claim 1, further comprising:

sending, by each of the vertices, a message to a directly linked vertex on one edge 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 a sending vertex comprises 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 message from the sending vertex.

7. The method of claim 1, further comprising:

initiating an unlinking procedure in response to determining that information has changed for one of the records represented by a vertex in the entity relationship 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 entity 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 entity vertex.

8. The method 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 entity vertex.

9. The method 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 entity relationship 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; and

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 a center vertex.