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

• US 8,495,077 B2
• Filed: 07/11/2012
• Issued: 07/23/2013
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Inventors: Bayliss, David Alan
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/546,908
• Publication Number:
  US 20120278340A1
• Time in Patent Office: 377 Days
• Field of Search: 707/758, 707/780, 707/737, 707/999.005, 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 the database upon a determination that the first record and the second record correspond to a same individual, wherein each record comprises at least one field and each of the at least one field comprises a field value or a null value, 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, the plurality of match probabilities comprising one or more of a field probability and a field value probability, wherein the field probability represents a probability that two randomly chosen records share a common field value in an associated field, and wherein the field value probability represents a probability that a record chosen at random contains an associated field value;

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, wherein each of the matching formulas are derived, at least in part, from one or more match probabilities;

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 derived from a match probability, wherein the match probability comprises a probability that an arbitrary entity representation in the database comprises a particular field value;

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 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 match probabilities using logarithms.

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

10. A system for linking a first record in a database to a second record in the database upon a determination that the first record and the second record correspond to a same individual, wherein each record comprises at least one field and each of the at least one field comprises a field value or a null value, the system comprising at least one computing apparatus, comprising at least one processor and at least one memory, wherein the at least one computing apparatus is collectively 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, the plurality of match probabilities comprising one or more of a field probability and a field value probability, wherein the field probability represents a probability that two randomly chosen records share a common field value in an associated field, and wherein the field value probability represents a probability that a record chosen at random contains an associated field value;

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, wherein each of the matching formulas are derived, at least in part, from one or more match probabilities;

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 derived from a match probability, wherein the match probability comprises a probability that an arbitrary entity representation in the database comprises a particular field value;

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

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

11. The system of claim 10, wherein the at least one 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.

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

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

14. The system of claim 10 or 11, wherein the size of the population associated with the database is a number of records in the database.

15. The system of claim 11, 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.

16. The system of claims 15, 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.

17. The system of claim 10, 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 match probabilities using logarithms.

18. The system of claim 10, wherein the at least one computing apparatus is configured to calculate the match score by calculating

19. The system of claim 10, wherein the at least one computing apparatus comprises a plurality of processors operating in parallel.