AUTOMATED SELECTION OF GENERIC BLOCKING CRITERIA

• US 20090292695A1
• Filed: 04/24/2009
• Published: 11/26/2009
• 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
• Granted Patent: US 8,275,770 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

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, each of the field probabilities associated with one of the fields in the database;

determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is approximately equal to the desired block size; and

outputting the set of fields, the set of fields independent of specific queries against the database.

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 computer implemented method of claim 1, wherein the determining a set of fields comprises determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is less than or equal to the desired block size.

4. The computer implemented method of claim 1, wherein the determining a set of fields comprises determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is not more than one percent more than the desired block size.

5. The computer implemented method of claim 1, wherein the determining a set of fields comprises determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is not more than five percent more than the desired block size.

6. The method of claim 1, 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.

7. The method of claim 6, 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.

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

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

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

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

12. 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.

13. The method of claim 12, 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.

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

15. 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, each of the field probabilities associated with one of the fields in the database;

determining, using a programmed computer, one or more fields wherein a product of the associated field probabilities and a number of records in the database is approximately equal to the desired block size;

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 create a smaller group of records in the database.

16. The method of claim 15, 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.

17. The method of claim 16, 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.

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

19. The method of claim 15, wherein the determining, using a programmed computer, one or more fields comprises determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is not more than one percent more than the desired block size.

20. The method of claim 15, wherein the determining, using a programmed computer, one or more fields comprises determining a set of fields wherein a product of the associated field probabilities and the number of records in the database is not more than five percent more than the desired block size.

21. The method of claim 15, 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.

22. The method of claim 21, 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.

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

24. 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, each of the field probabilities associated with one of the fields in the database;

an electronic processor configured to determine a set of fields wherein a product of the associated field probabilities and the number of records in the database is approximately equal to the desired block size; and

an electronic processor configured to output the set of fields, the set of fields independent of specific queries against the database.

25. The system of claim 24, wherein the set of fields is determined by operating an electronic processor to combine 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.

26. The system of claim 25, 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.

27. The system of claim 25, 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.

28. The system of claim 24, wherein the product of the associated field probabilities and the number of records in the database is not more than one percent more than the desired block size.

29. The system of claim 24, wherein the product of the associated field probabilities and the number of records in the database is not more than five percent more than the desired block size.

30. The system of claim 24, 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.

31. The system of claim 30, 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.