Automated selection of generic blocking criteria

• US 8,275,770 B2
• Filed: 04/24/2009
• Issued: 09/25/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): Ng, Amy
• Application Number:
  US12/429,350
• Publication Number:
  US 20090292695A1
• Time in Patent Office: 1,250 Days
• Field of Search: 707/713, 707/720, 707/736
• US Class Current: 707/736
• 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

Field probabilities associated with fields in a database may be used to create one or more blocking criteria. The blocking criteria may be a set of fields that should be equal among two or more records in a database, so that a search of the records in the database according to the blocking criteria yields a subset of records approximately equal to or less than the specified maximum block size. Generic blocking criteria may also be created. The generic blocking criteria may be used for a batch comparison or batch linking operation within the records of the database.

Claims

1. A computer implemented method of identifying a set of fields applicable to partition a plurality of records in an electronic database into one or more blocks based on a desired block size and independent of specific queries against the database, the method comprising:

receiving a desired block size;

calculating field probabilities for a plurality of fields in the database, wherein each field probability represents an average cohort size for a field divided by the number of records in the database, each of the field probabilities associated with one of the fields in the database, and wherein the average cohort size for each field corresponds to the average number of records containing a same field value in the respective field;

determining a set of fields by combining the field probabilities of one or more fields by mathematical calculation, wherein a product of the combined field probabilities and the number of records in the database is less than or equal to the desired block size, and wherein the set of fields is determined independent of specific queries against the database; and

outputting the set of fields.

2. The method of claim 1, wherein each field probability is calculated as a weighted sum of field value probabilities associated with the associated field in the database.

3. The method of claim 1, further comprising ordering the field probabilities from a lowest field probability to a highest field probability, and the lowest field probability is multiplied with successive higher field probabilities until the cumulative field probability multiplied by the number of records in the database is equal to or less than the desired block size.

4. The method of claim 1, further comprising calculating a potential remaining probability for each field probability by multiplying a largest field probability with successive smaller field probabilities.

5. The method of claim 1, where the desired block size is defined as a number of records.

6. The method of claim 1, where the desired block size is defined as a percentage of the total number of records in the database.

7. The method of claim 1, where the desired block size is defined as the size of a block processed by one or more computers.

8. The method of claim 1, further comprising arranging the fields of the database into a search tree and determining a set of fields according to one or more branches of the search tree.

9. The method of claim 8, further comprising calculating a potential remaining probability for the one or more branches by multiplying a largest field probability with successive smaller field probabilities, and removing branches in the search tree that do not yield a subset of records equal to or less than the desired block size based on the potential remaining probability of the combination.

10. The method of claim 1, where more than one set of fields is determined and presented in an output.

11. A computer implemented method of creating blocking criteria based on a desired block size, the method comprising:

calculating, using a programmed computer, one or more field probabilities for one or more fields in an electronic database, wherein each field probability represents an average cohort size for a field divided by the number of records in the database, each of the field probabilities associated with one of the fields in the database, and wherein the average cohort size for each field corresponds to the average number of records containing a same field value in the respective field;

determining, using a programmed computer, one or more fields by combining the field probabilities of one or more fields by mathematical calculation, wherein a product of the combined field probabilities and a number of records in the database is less than or equal to the desired block size, and wherein the one or more fields is determined independent of specific queries against the database;

grouping, using a programmed computer, the one or more fields into one or more blocking criteria;

outputting the one or more blocking criteria; and

applying, using a programmed computer, at least one of the one or more blocking criteria to the records of the database to create a smaller group of records in the database.

12. The method of claim 11, wherein the set of fields is determined by combining the field probabilities of one or more fields by mathematical calculation until the combined field probabilities of the one or more fields in the set of fields multiplied by the plurality of records in the database is equal to or less than the desired block size.

13. The method of claim 12, wherein the field probabilities are ordered from a lowest field probability to a highest field probability, and the lowest field probability is multiplied with successive higher field probabilities until the cumulative field probability multiplied by the number of records in the database is equal to or less than the desired block size.

14. The method of claim 11, further comprising arranging the fields of the database into a search tree and determining a set of fields according to one or more branches of the search tree.

15. The method of claim 14, further comprising calculating a potential remaining probability for the one or more branches by multiplying a largest field probability with successive smaller field probabilities, and removing branches in the search tree that do not yield a subset of records equal to or less than the desired block size based on the potential remaining probability of the combination.

16. The method of claim 11, further comprising transmitting at least one of the one or more blocking criteria one or more matching algorithms.

17. A system for identifying a set of fields applicable to partition a plurality of records in an electronic database into one or more blocks based on a desired block size and independent of specific queries against the database, comprising:

an electronic processor configured to receive a desired block size;

an electronic processor configured to calculate field probabilities for a plurality of fields in the database, wherein each field probability represents an average cohort size for a field divided by the number of records in the database, each of the field probabilities associated with one of the fields in the database, and wherein the average cohort size for each field corresponds to the average number of records containing a same field value in the respective field;

an electronic processor configured to determine a set of fields by combining the field probabilities of one or more fields by mathematical calculation, wherein a product of the combined field probabilities and the number of records in the database is less than or equal to the desired block size, and wherein the set of fields is determined independent of specific queries against the database; and

an electronic processor configured to output the set of fields.

18. The system of claim 17, wherein an electronic processor is used to order the field probabilities from a lowest field probability to a highest field probability, and the lowest field probability is multiplied with successive higher field probabilities until the cumulative field probability multiplied by the number of records in the database is equal to or less than the desired block size.

19. The system of claim 17, further comprising an electronic processor configured to calculate a potential remaining probability for each field probability by multiplying a largest field probability with successive smaller field probabilities.

20. The system of claim 17, further comprising an electronic processor configured to arrange the fields of the database into a search tree and an electronic processor configured to determine a set of fields according to one or more branches of the search tree.

21. The system of claim 20, further comprising an electronic processor configured to calculate a potential remaining probability for the one or more branches by multiplying a largest field probability with successive smaller field probabilities, and an electronic processor configured to remove branches in the search tree that do not yield a subset of records equal to or less than the desired block size based on the potential remaining probability of the combination.