SYSTEM FOR AND METHOD OF PARTITIONING MATCH TEMPLATES

• US 20100005079A1
• Filed: 07/02/2009
• Published: 01/07/2010
• Est. Priority Date: 07/02/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,639,691 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• 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/24 Querying
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

Disclosed is a system for, and method of, identifying an entity representation. In some embodiments, a match template is used to partition a search criteria so that an expected number of matching records does not exceed a desired threshold. In such embodiments, the match template may limit the number of records that are expected to identically match in certain fields designated as fixed fields, and limit the number of records that are expected to either identically match or have blank field values in certain fields designated as optional fields. Such embodiments thus provide probabilistic limits on a number of database fetches required for a particular search and on a number of record transfers required for a particular search.

Claims

1. A method of partitioning a match template to be used to identify a universal entity representation in an electronic universal database that corresponds to a foreign entity representation in an electronic foreign database, each entity representation comprising a plurality of linked records, each record comprising a plurality of fields, each field associated with a field weight and capable of containing a field value, each field value associated with a field value weight, the method comprising:

receiving a match template specifying an ordered plurality of fields, each field associated with a field weight;

receiving a desired ceiling for a number of records that are likely match a search criteria at a fixed portion of the match template;

receiving a desired ceiling for a number of records that are likely match a search criteria at a fixed portion and an optional portion of the match template;

wherein an arbitrary record matches an arbitrary search criteria if all fixed fields of the arbitrary record are populated with field values that match corresponding fixed field values of the arbitrary search criteria and if all optional fields of the arbitrary record are each populated with one of a null field value and a field value that matches a corresponding optional field value of the arbitrary search criteria;

calculating a first cumulative field weight based on a number of entity representations in the universal database and the desired ceiling for a number of records that are likely match a search criteria in a fixed portion of the match template;

designating an initial segment of fields from the match template as fixed fields based on the first cumulative field weight;

calculating a second cumulative field weight based on a number of entity representations in the universal database and the desired ceiling for a number of records that are likely match a search criteria in a fixed portion and an optional portion of the match template;

designating a subsequent segment of fields from the match template as optional based on the second cumulative field weight; and

outputting a partition of the match template based on at least the initial segment and the subsequent segment, whereby a number of records from the universal database that match an arbitrary search criteria at a fixed portion of the match template is less than the desired ceiling for a number of records that are likely match a search criteria at a fixed portion of the match template, and whereby a number of records from the universal database that match an arbitrary search criteria at a fixed portion and an optional portion of the match template is less than the desired ceiling for a number of records that are likely match a search criteria at an optional portion of the match template.

2. The method of claim 1, wherein each field value weight comprises a probability that an arbitrary entity representation in the universal database comprises a corresponding field value in a field of a record in the arbitrary entity representation.

3. The method of claim 1, wherein each field weight comprises an expected value of a size of a field value cohort of a record in an arbitrary entity representation in the universal database.

4. The method of claim 1, wherein the designating an initial segment of fields from the match template as fixed fields comprises designating an initial segment of fields whose cumulative associated field weights are less than a term comprising a difference between a number of entity representations in the database and the desired ceiling for a number of entity representations that are likely match a search criteria at a fixed portion of the match template.

5. The method of claim 1, wherein the outputting a partition comprises outputting the partition to a user in a human readable form.

6. The method of claim 1, wherein the outputting a partition comprises outputting the partition to a computer configured to perform a search for an entity representation in the universal database based on the match template.

7. The method of claim 1, further comprising searching within the universal database for an entity representation that matches a search criteria according to the match template.

8. The method of claim 1, further comprising designating any part of the match template after the subsequent segment of fields from the match template as extra credit.

9. A system for partitioning a match template to be used to identify a universal entity representation in an electronic universal database that corresponds to a foreign entity representation in an electronic foreign database, each entity representation comprising a plurality of linked records, each record comprising a plurality of fields, each field associated with a field weight and capable of containing a field value, each field value associated with a field value weight, the system comprising:

an electronic universal database comprising a plurality of electronically stored entity representations, each entity representation comprising a plurality of linked records, each record comprising a plurality of fields, each field associated with a field weight and capable of containing a field value, each field value associated with a field value weight;

an electronic memory storing a match template, the match template specifying an ordered plurality of fields, each field associated with a field weight;

an electronic memory storing a desired ceiling for a number of records that are likely match a search criteria at a fixed portion of the match template;

an electronic memory storing a desired ceiling for a number of records that are likely match a search criteria at a fixed portion and an optional portion of the match template;

wherein an arbitrary record matches an arbitrary search criteria if all fixed fields of the arbitrary record are populated with field values that match corresponding fixed field values of the arbitrary search criteria and if all optional fields of the arbitrary record are each populated with one of a null field value and a field value that matches a corresponding optional field value of the arbitrary search criteria;

a processor programmed to calculate a first cumulative field weight based on a number of entity representations in the universal database and the desired ceiling for a number of records that are likely match a search criteria in a fixed portion of the match template;

a processor programmed to store an electronic datum designating an initial segment of fields from the match template as fixed fields, wherein the initial segment is calculated based on the first cumulative field weight;

a processor programmed to calculate a second cumulative field weight based on a number of entity representations in the universal database and the desired ceiling for a number of records that are likely match a search criteria in a fixed portion and an optional portion of the match template;

a processor programmed to store an electronic datum designating a subsequent segment of fields from the match template as optional, wherein the subsequent segment is calculated based on the second cumulative field weight; and

an output configured to output a partition of the match template based on at least the initial segment and the subsequent segment, whereby a number of records from the universal database that match an arbitrary search criteria at a fixed portion of the match template is less than the desired ceiling for a number of records that are likely match a search criteria at a fixed portion of the match template, and whereby a number of records from the universal database that match an arbitrary search criteria at a fixed portion and an optional portion of the match template is less than the desired ceiling for a number of records that are likely match a search criteria at an optional portion of the match template.

10. The system of claim 9, wherein each field value weight comprises a probability that an arbitrary entity representation in the universal database comprises a corresponding field value in a field of a record in the arbitrary entity representation.

11. The system of claim 9, wherein each field weight comprises an expected value of a size of a field value cohort of a record in an arbitrary entity representation in the universal database.

12. The system of claim 9, wherein the initial segment is determined by determining an initial segment of fields whose cumulative associated field weights are less than a term comprising a difference between a number of entity representations in the database and the desired ceiling for a number of entity representations that are likely match a search criteria at a fixed portion of the match template.

13. The system of claim 9, wherein the output comprises a human readable display.

14. The system of claim 9, wherein the output comprises an electronic interface coupled to a computer configured to perform a search for an entity representation in the universal database based on the match template.

15. The system of claim 9, further comprising a processor programmed to store an electronic datum designating any part of the match template after the subsequent segment of fields from the match template as extra credit.