Statistical record linkage calibration at the field and field value levels without the need for human interaction

• US 8,135,719 B2
• Filed: 04/24/2009
• Issued: 03/13/2012
• 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): Ng, Amy
• Application Number:
  US12/429,382
• Publication Number:
  US 20090271397A1
• Time in Patent Office: 1,054 Days
• Field of Search: 707/692, 707/748, 707/749, 707/750, 707/758
• US Class Current: 707/748
• 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 is a system for, and method of, calculating parameters used to determine whether records and entity representations should be linked. The system and method apply iterative techniques such that parameters from each linking iteration are used in the next linking iteration. The system and method need no human interaction in order to calibrate and utilize record matching formulas used for the linking decisions.

Claims

1. A computer implemented iterative process for generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, wherein at least a portion of parameters for the record matching formula are configured for a particular field value appearing in a selected field of at least one record, the process comprising:

, using the computer, a field value weight, the field value weight reflecting a first probability that an arbitrary record in the database comprises the particular field value in the selected field of the arbitrary record, wherein the first probability comprises a ratio of records in the database that include the particular field value in the selected field to a total number of records in the database;

forming a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record comprising the particular field value, the first record linked to a second record using a first instance of the record matching formula comprising the field value weight;

, using the computer, a revised field value weight, the revised field value weight reflecting a second probability that an arbitrary entity representation in the database comprises the particular field value in the selected field of a record in the arbitrary entity representation, wherein the second probability comprises a ratio of entity representations in the database that include the particular field value in the selected field to a total number of entity representations in the database;

linking at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised field value weight, whereby a number of entity representations in the database is reduced by the linking at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations; and

retrieving information from at least one record in the database.

2. The method of claim 1, further comprising iterating the calculating a revised field value weight and the linking at least two entity representations at least once prior to the retrieving.

3. The method of claim 1, wherein the record matching formula comprises a weighted sum of probabilities that two records match.

4. The method of claim 1, wherein the field value weight comprises a logarithm of a probability that an arbitrary record in the database comprises the particular field value in the selected field of the arbitrary record, and wherein the revised field value weight comprises a logarithm of a probability that an arbitrary entity representation in the database comprises the particular field value in the selected field of a record in the arbitrary entity representation.

5. A computer implemented iterative process for generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, wherein at least a portion of parameters for the record matching formula are configured for a selected field and independent of any field value in the selected field, the process comprising:

, using the computer, a plurality of field value weights, each field value weight reflecting a probability that an arbitrary record in the database comprises a different field value in the selected field of the arbitrary record, wherein each probability comprises a ratio of a number of records in the database that include a different field value in the selected field to a total number of records in the database;

, using the computer, a field weight for the selected field, the field weight for the selected field derived from each of the plurality of field value weights;

forming a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record linked to a second record using a first instance of the record matching formula comprising the field weight for the selected field;

, using the computer, a plurality of revised field value weights, each revised field value weight reflecting a probability that an arbitrary entity representation in the database comprises a different field value in the selected field of a record in the arbitrary entity representation, wherein each probability comprises a ratio of a number of entity representations in the database that include a different field value in the selected field to a total number of entity representations in the database;

, using the computer, a revised field weight for the selected field, the revised field weight for the selected field derived from each of the plurality of revised field value weights;

linking at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised field value weight, whereby a number of entity representations in the database is reduced by the linking at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations; and

retrieving information from at least one record in the database.

6. The method of claim 5 further comprising iterating the calculating the plurality of revised field value probabilities, the calculating a revised field weight, and the linking at least two entity representations at least once prior to the retrieving.

7. The method of claim 5, wherein the record matching formula comprises a weighted sum of probabilities that two records match.

8. The method of claim 5, wherein each field value weight comprises a logarithm of a probability that an arbitrary record in the database comprises a different particular field value in the selected field of the arbitrary record, and wherein each revised field value weight comprises a logarithm of a probability that an arbitrary entity representation in the database comprises a different particular field value in the selected field of a record in the arbitrary entity representation.

9. A computer system for iteratively generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, wherein at least a portion of parameters for the record matching formula are configured for a particular field value appearing in a selected field of at least one record, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value;

a processor programmed to calculate a field value weight, the field value weight reflecting a first probability that an arbitrary record in the database comprises the particular field value in the selected field of the arbitrary record, wherein the first probability comprises a ratio of records in the database that include the particular field value in the selected field to a total number of records in the database;

a processor programmed to form and store a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record comprising the particular field value, the first record linked to a second record using a first instance of the record matching formula comprising the field value weight;

a processor programmed to calculate a revised field value weight, the revised field value weight reflecting a second probability that an arbitrary entity representation in the database comprises the particular field value in the selected field of a record in the arbitrary entity representation, wherein the second probability comprises a ratio of entity representations in the database that include the particular field value in the selected field to a total number of entity representations in the database; and

a processor programmed to link and store at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised field value weight, whereby a number of entity representations in the database is reduced by linking the at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations.

10. The system of claim 9, further comprising program logic configured to repeat calculating a revised field value weight and linking at least two entity representations at least once.

11. The system of claim 9, wherein the record matching formula comprises a weighted sum of probabilities that two records match.

12. The system of claim 9, wherein the field value weight comprises a logarithm of a probability that an arbitrary record in the database comprises the particular field value in the selected field of the arbitrary record, and wherein the revised field value weight comprises a logarithm of a probability that an arbitrary entity representation in the database comprises the particular field value in the selected field of a record in the arbitrary entity representation.

13. A computer system for iteratively generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, wherein at least a portion of parameters for the record matching formula are configured for a selected field and independent of any field value in the selected field, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value;

a processor programmed to calculate a plurality of field value weights, each field value weight reflecting a probability that an arbitrary record in the database comprises a different field value in the selected field of the arbitrary record, wherein each probability comprises a ratio of a number of records in the database that include a different field value in the selected field to a total number of records in the database;

a processor programmed to calculate a field weight for the selected field, the field weight for the selected field derived from each of the plurality of field value weights;

a processor programmed to form and store a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record linked to a second record using a first instance of the record matching formula comprising the field weight for the selected field;

a processor programmed to calculate a plurality of revised field value weights, each revised field value weight reflecting a probability that an arbitrary entity representation in the database comprises a different field value in the selected field of a record in the arbitrary entity representation, wherein the second probability comprises a ratio of entity representations in the database that include the particular field value in the selected field to a total number of entity representations in the database;

a processor programmed to calculate a revised field weight for the selected field, the revised field weight for the selected field derived from each of the plurality of revised field value weights; and

a processor programmed to link and store at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised field value weight, whereby a number of entity representations in the database is reduced by the linking at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations.

14. The system of claim 13 further comprising program logic configured to iterate calculating the plurality of revised field value probabilities, calculating a revised field weight, and linking and storing at least two entity representations at least once.

15. The system of claim 13, wherein the record matching formula comprises a weighted sum of probabilities that two records match.

16. The system of claim 13, wherein each field value weight comprises a logarithm of a probability that an arbitrary record in the database comprises a different particular field value in the selected field of the arbitrary record, and wherein each revised field value weight comprises a logarithm of a probability that an arbitrary entity representation in the database comprises a different particular field value in the selected field of a record in the arbitrary entity representation.