DATABASE SYSTEMS AND METHODS FOR LINKING RECORDS AND ENTITY REPRESENTATIONS WITH SUFFICIENTLY HIGH CONFIDENCE

• US 20090271424A1
• Filed: 08/08/2008
• Published: 10/29/2009
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Group Inc. (RELX PLC)
• Inventors: BAYLISS, David Alan
• Granted Patent: US 8,266,168 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed are a system for, and method of, determining whether records correspond to the same individual. The system and method provide such a determination with a known minimum level of confidence. That is, the system and method provide an indication that records correspond to the same individual along with an associated confidence level. The system and method may be used to link records in a database that correspond to the same individuals, creating entity representations in the database.

Claims

1. A computer implemented method of linking a first record in a database to a second record in a database upon a determination that the first record and the second record correspond to the same individual, the method comprising:

calculating a plurality of match probabilities using an iterative process, each of the plurality of match probabilities corresponding to a different field common to the first record and the second record;

calculating a match score based on a plurality of terms, each of the plurality of terms corresponding to a different field common to the first record and the second record, each of the plurality of terms comprising;

(1) a probability that a field value in a corresponding field of the first record matches a field value in a corresponding field in the second record, and (2) a quantity based on a corresponding one of the plurality of match probabilities;

determining, based on the match score and a size of a population associated with the database, whether there is a sufficiently high confidence level that the first record and the second record correspond to the same individual; and

linking, in the database, the first record with the second record based on the determining.

2. The method of claim 1, wherein the determining comprises determining whether the match score exceeds a quantity derived from a threshold probability and the size of the population associated with the database.

3. The method of claim 1 or 2, wherein the size of the population associated with the database is a number of individuals intended to be reflected in the database.

4. The method of claim 1 or 2, wherein the size of the population associated with the database is a number of entity representations in the database.

5. The method of claim 1 or 2, wherein the size of the population associated with the database is a number of records in the database.

6. The method of claim 2 wherein the quantity derived from the threshold probability and the size of the population associated with the database comprises a first logarithm and a second logarithm, wherein an argument of the first logarithm comprises a desired confidence probability and an argument of the second logarithm comprises the size of the population associated with the database.

7. The method of claim 6 wherein the quantity derived from the threshold probability and the size of the population associated with the database comprises log(N)−

log(1−

P)−

1, wherein P represents the threshold probability and N represents the size of the population associated with the database.

8. The method of claim 1 wherein the plurality of match probabilities comprise at least one field probability.

9. The method of claim 1 wherein the plurality of match probabilities comprise at least one field value probability.

10. The method of claim 1 wherein the match score comprises a weighted sum of probabilities that field values in the first record match field values in the second record, wherein the sum is weighted by match weights derived from the match probabilities using logarithms.

11. The method of claim 1 wherein the calculating the match score comprises calculating

$\sum _{}^{}$

i = 1 I 



p i 

w i ,

wherein p_i is a probability that a field value in a corresponding field of the first record matches a field value in a corresponding field in the second record, w_i is a negative logarithm of a corresponding one of the plurality of match probabilities, and I enumerates at least some fields common to the first record and the second record.

12. A system for linking a first record in a database to a second record in a database upon a determination that the first record and the second record correspond to the same individual, the system comprising:

a first computing apparatus configured to calculate a plurality of match probabilities using an iterative process, each of the plurality of match probabilities corresponding to a different field common to the first record and the second record;

a second computing apparatus configured to calculate a match score based on a plurality of terms, each of the plurality of terms corresponding to a different field common to the first record and the second record, each of the plurality of terms comprising;

(1) a probability that a field value in a corresponding field of the first record matches a field value in a corresponding field in the second record, and (2) a quantity based on a corresponding one of the plurality of match probabilities;

a third computing apparatus configured to determine, based on the match score and a size of a population associated with the database, whether there is a sufficiently high confidence level that the first record and the second record correspond to the same individual; and

a fourth computing apparatus configured to link, in the database, the first record with the second record based on the determining.

13. The system of claim 12, wherein the third computing apparatus is configured to determine whether the match score exceeds a quantity derived from a threshold probability and the size of the population associated with the database.

14. The system of claim 12 or 13, wherein the size of the population associated with the database is a number of individuals intended to be reflected in the database.

15. The system of claim 12 or 13, wherein the size of the population associated with the database is a number of entity representations in the database.

16. The system of claim 12 or 13, wherein the size of the population associated with the database is a number of records in the database.

17. The system of claim 13 wherein the quantity derived from the threshold probability and the size of the population associated with the database comprises a first logarithm and a second logarithm, wherein an argument of the first logarithm comprises a desired confidence probability and an argument of the second logarithm comprises the size of the population associated with the database.

18. The system of claim 17 wherein the quantity derived from the threshold probability and the size of the population associated with the database comprises log(N)−

log(1−

P)−

1, wherein P represents the threshold probability and N represents the size of the population associated with the database.

19. The system of claim 12 wherein the plurality of match probabilities comprise at least one field probability.

20. The system of claim 12 wherein the plurality of match probabilities comprise at least one field value probability.

21. The system of claim 12 wherein the match score comprises a weighted sum of probabilities that field values in the first record match field values in the second record, wherein the sum is weighted by match weights derived from the match probabilities using logarithms.

22. The system of claim 12 wherein the second computer is configured to calculate the match by calculating

$\sum _{}^{}$

i = 1 I 



p i 

w i ,

wherein p_i is a probability that a field value in a corresponding field of the first record matches a field value in a corresponding field in the second record, w_i is a negative logarithm of a corresponding one of the plurality of match probabilities, and I enumerates at least some fields common to the first record and the second record.

23. The system of claim 12, wherein the first computing apparatus, the second computing apparatus, the third computing apparatus and the fourth computing apparatus are the same computing apparatus.

24. The system of claim 12, wherein the first computing apparatus comprises a plurality of processors operating in parallel.