Using relationships in candidate discovery

• US 8,150,813 B2
• Filed: 12/18/2008
• Issued: 04/03/2012
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Adair, Gregery G., Jonas, Jeffrey J.
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): WILLIS, AMANDA LYNN
• Application Number:
  US12/338,552
• Publication Number:
  US 20100161566A1
• Time in Patent Office: 1,202 Days
• Field of Search: 707/692, 707/706, 707/738, 707/E17.008, 707/999.1, 707/999.101
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Techniques are disclosed for adding entities to a group of entity resolution candidates by selecting entities that have a minimum threshold of similarity to a candidate, allowing a greater number of resolutions in an entity resolution system. To resolve an incoming identity record, an initial group of candidates may be selected from known entities by identifying entities that match a candidate building attribute of the incoming identity record. Additional candidates may be selected by identifying entities with some information that is similar to one of the candidate entities.

Claims

1. A computer-implemented method of resolving entities in an entity resolution system storing identity records related to a plurality of entities, the method comprising:

receiving a new identity record;

identifying a set of candidate entities, from the plurality of entities, based upon a match between an attribute of the new identity record and corresponding attributes of one or more of the plurality of entities;

identifying, from the plurality of entities not included in the set of candidate entities, a set of first-degree entities having a likeness score satisfying a threshold, wherein the likeness score for each first-degree entity is determined relative to a respective candidate entity;

by operation of one or more processors, identifying, from the plurality of entities not included in the set of candidate entities and not included in the set of first-degree entities, a set of second-degree entities having a likeness score satisfying the threshold, wherein the likeness score for each second-degree entity is determined relative to a respective first-degree entity, wherein the threshold is based on a count of degrees of separation from a respective candidate entity, such that the threshold to be satisfied by the set of second-degree entities is stricter than the threshold to be satisfied by the set of first-degree entities;

adding, to the set of candidate entities, the set of first-degree entities and the set of second-degree entities; and

upon determining that the new identity record refers to a candidate entity in the set of candidate entities, including any added entities, conjoining the new identity record and the candidate entity to form a first conjoined entity, wherein the first conjoined entity is further conjoinable with a different entity of the plurality of entities to resolve an instance of data ambiguity.

2. The method of claim 1, further comprising:

upon determining that the new identity record does not refer to any candidate entity, creating a new entity; and

conjoining the new identity record with the new entity.

3. The method of claim 1, further comprising:

identifying that conjoining the new identity record and the candidate entity resolves the instance of data ambiguity between two entities, comprising, subsequent to conjoining the new identity record and the candidate entity, determining that the first conjoined entity and the different entity refer to a single individual, wherein the instance of data ambiguity previously prevented the different entity from being conjoined with the candidate entity; and

conjoining the first conjoined entity and the different entity to form a second conjoined entity.

4. The method of claim 1, wherein identifying a set of candidate entities based upon a match between the attribute of the new identity record and a corresponding attribute of one or more of the plurality of entities, comprises:

determining a plurality of attribute values of the new identity record; and

identifying entities associated with identity records matching each of the plurality of attribute values.

5. The method of claim 1, wherein the threshold represents a measure of similarity between entities.

6. The method of claim 1, wherein the attribute of the new identity record and the corresponding attribute of the plurality of entities refers to one of a demographic characteristic, a biographic characteristic, a demographic characteristic, and a biometric of an individual represented by the entity.

7. The method of claim 1, wherein each record in a respective one of the plurality of entities each refers to a same individual.

8. A computer program product comprising a computer useable storage medium having a computer readable program, wherein the computer readable program, when executed on a computer causes the computer to perform an operation for resolving entities in an entity resolution system storing identity records related to a plurality of entities, the operation comprising:

receiving a new identity record;

identifying a set of candidate entities, from the plurality of entities, based upon a match between an attribute of the new identity record and corresponding attributes of one or more of the plurality of entities;

identifying, from the plurality of entities not included in the set of candidate entities, a set of first-degree entities having a likeness score satisfying a threshold, wherein the likeness score for each first-degree entity is determined relative to a respective candidate entity;

by operation of one or more computer processors of the computer when executing the computer readable program, identifying, from the plurality of entities not included in the set of candidate entities and not included in the set of first-degree entities, a set of second-degree entities having a likeness score satisfying the threshold, wherein the likeness score for each second-degree entity is determined relative to a respective first-degree entity, wherein the threshold is based on a count of degrees of separation from a respective candidate entity, such that the threshold to be satisfied by the set of second-degree entities is stricter than the threshold to be satisfied by the set of first-degree entities;

adding, to the set of candidate entities, the set of first-degree entities and the set of second-degree entities; and

upon determining that the new identity record refers to a candidate entity in the set of candidate entities, including any added entities, conjoining the new identity record and the candidate entity to form a first conjoined entity, wherein the first conjoined entity is further conjoinable with a different entity of the plurality of entities to resolve an instance of data ambiguity.

9. The computer program product of claim 8, wherein the operation further comprises:

upon determining that the new identity record does not refer to any candidate entity, creating a new entity; and

conjoining the new identity record with the new entity.

10. The computer program product of claim 8, wherein the operation further comprises:

identifying that conjoining the new identity record and the candidate entity resolves the instance of data ambiguity between two entities, comprising, subsequent to conjoining the new identity record and the candidate entity, determining that the first conjoined entity and the different entity refer to a single individual, wherein the instance of data ambiguity previously prevented the different entity from being conjoined with the candidate entity; and

conjoining the first conjoined entity and the different entity to form a second conjoined entity.

11. The computer program product of claim 8, wherein identifying a set of candidate entities based upon a match between the attribute of the new identity record and a corresponding attribute of one or more of the plurality of entities, comprises:

determining a plurality of attribute values of the new identity record; and

identifying entities associated with identity records matching each of the plurality of attribute values.

12. The computer program product of claim 8, wherein the threshold represents a measure of similarity between entities.

13. The computer program product of claim 8, wherein the attribute of the new identity record and the corresponding attribute of the plurality of entities refers to one of a demographic characteristic, a biographic characteristic, a demographic characteristic, and a biometric of an individual represented by the entity.

14. The computer program product of claim 8, wherein each record in a respective one of the plurality of entities each refers to a same individual.

15. A system, comprising:

one or more computer processors; and

a memory containing a program, which when executed by the one or more computer processors, performs an operation for resolving entities in an entity resolution system storing identity records related to a plurality of entities by performing the steps of;

receiving a new identity record;

identifying a set of candidate entities, from the plurality of entities, based upon a match between an attribute of the new identity record and corresponding attributes of one or more of the plurality of entities;

identifying, from the plurality of entities not included in the set of candidate entities, a set of first-degree entities having a likeness score satisfying a threshold, wherein the likeness score for each first-degree entity is determined relative to a respective candidate entity;

identifying, from the plurality of entities not included in the set of candidate entities and not included in the set of first-degree entities, a set of second-degree entities having a likeness score satisfying the threshold, wherein the likeness score for each second-degree entity is determined relative to a respective first-degree entity, wherein the threshold is based on a count of degrees of separation from a respective candidate entity, such that the threshold to be satisfied by the set of second-degree entities is stricter than the threshold to be satisfied by the set of first-degree entities;

adding, to the set of candidate entities, the set of first-degree entities and the set of second-degree entities; and

upon determining that the new identity record refers to a candidate entity in the set of candidate entities, including any added entities, conjoining the new identity record and the candidate entity to form a first conjoined entity, wherein the first conjoined entity is further conjoinable with a different entity of the plurality of entities to resolve an instance of data ambiguity.

16. The system of claim 15, wherein the steps further comprise:

upon determining that the new identity record does not refer to any candidate entity, creating a new entity; and

conjoining the new identity record with the new entity.

17. The system of claim 15, wherein the steps further comprise:

identifying that conjoining the new identity record and the candidate entity resolves the instance of data ambiguity between two entities, comprising, subsequent to conjoining the new identity record and the candidate entity, determining that the first conjoined entity and the different entity refer to a single individual, wherein the instance of data ambiguity previously prevented the different entity from being conjoined with the candidate entity; and

conjoining the first conjoined entity and the different entity to form a second conjoined entity.

18. The system of claim 15, wherein identifying a set of candidate entities based upon a match between the attribute of the new identity record and a corresponding attribute of one or more of the plurality of entities, comprises:

determining a plurality of attribute values of the new identity record; and

identifying entities associated with identity records matching each of the plurality of attribute values.

19. The system of claim 15, wherein the threshold represents a measure of similarity between entities.

20. The system of claim 15, wherein the attribute of the new identity record and the corresponding attribute of the plurality of entities refers to one of a demographic characteristic, a biographic characteristic, a demographic characteristic, and a biometric of an individual represented by the entity.

21. The system of claim 15, wherein each record in a respective one of the plurality of entities each refers to a same individual.