Database systems and methods for linking records and entity representations with sufficiently high confidence

• US 8,266,168 B2
• Filed: 08/08/2008
• Issued: 09/11/2012
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk & Information Analytics Group, Inc. (RELX PLC)
• Inventors: Bayliss, David Alan
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US12/188,742
• Publication Number:
  US 20090271424A1
• Time in Patent Office: 1,495 Days
• Field of Search: 707/999.005, 707/758, 707/737, 707/609
• US Class Current: 707/758
• 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 a 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;

selecting a matching formula from the group consisting of a field weight matching formula, a field value weight matching formula, and a supplemental weight matching formula;

calculating a match score based on a plurality of terms using the selected matching formula, 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 weight comprising a match probability, wherein the weight comprises a logarithm of the match probability, wherein the match probability comprises a probability that an arbitrary entity representation in the database comprises a particular field value, wherein the probability comprises a ratio of entity representations in the database that include the particular field value to a total number of entity representations in the database;

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

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 a 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 select a matching formula from the group consisting of a field weight matching formula, a field value weight matching formula, and a supplemental weight matching formula;

a third computing apparatus configured to calculate a match score based on a plurality of terms using the selected matching formula, 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 weight comprising a match probability, wherein the weight comprises a logarithm of the match probability, wherein the match probability comprises a probability that an arbitrary entity representation in the database comprises a particular field value, wherein the probability comprises a ratio of entity representations in the database that include the particular field value to a total number of entity representations in the database;

a fourth 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 fifth computing apparatus configured to link, in the database, the first record with the second record based on the determining;

wherein each computing apparatus comprises at least one processor.

13. The system of claim 12, wherein the fourth 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 third computing apparatus is configured to calculate the match score by calculating

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

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