Methods and apparatus for fusing databases

• US 7,698,345 B2
• Filed: 10/21/2003
• Issued: 04/13/2010
• Est. Priority Date: 10/21/2003
• Status: Active Grant

• Current Assignee: Nielsen Company (US), LLC
• Original Assignee: The Nielsen Company LLC (MOOD Media Corporation)
• Inventors: McMillian, Francis G., Samson, Jerome
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US10/576,800
• Publication Number:
  US 20080215602A1
• Time in Patent Office: 2,366 Days
• Field of Search: 707/6, 707/200
• US Class Current: 707/780
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Methods and apparatus for fusing multiple databases into a single database are disclosed. A disclosed method determines a ranking of a plurality of matching variables associated with first and second datasets and generates a hierarchical matching grid including a plurality of levels based on the ranking of the plurality of matching variables. The example method identifies first and second sets of match candidates from the first and second datasets based on successive levels of the hierarchical matching grid and fuses records in the first and second sets of match candidates based on probabilities associated with the records.

Claims

1. A method of fusing first and second datasets, comprising:

determining an importance ranking of a plurality of variables associated with the first and second datasets;

generating a hierarchical matching grid including a plurality of levels based on the importance ranking of the plurality of variables, wherein each of the levels defines match criteria for satisfying a matching records condition by indicating which of the variables are to match;

identifying first and second sets of match candidates from the first and second datasets based on one of the plurality of levels of the hierarchical matching grid; and

fusing records in the first and second sets of match candidates based on probabilities associated with the records.

2. A method as defined in claim 1, wherein determining the importance ranking of the plurality of variables includes ranking the plurality of variables based on a relative strength of a relationship between each of the variables and a respondent characteristic.

3. A method as defined in claim 1, wherein generating the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables includes generating a series of binary values for each level of the hierarchical grid so that each of a plurality of bit positions associated with the binary values uniquely corresponds to one of the plurality of variables, wherein the binary values define whether a corresponding one of the variables is to match in the first and second sets of match candidates.

4. A method as defined in claim 1, wherein the generating the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables includes generating the hierarchical matching grid to allow skewed matching on one or more of the variables.

5. A method as defined in claim 1, wherein generating the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables includes establishing a minimum matching level.

6. A method as defined in claim 1, wherein identifying the first and second sets of match candidates from the first and second datasets based on the one of the plurality of levels of the hierarchical matching grid includes using match criteria from the one of the plurality of levels of the hierarchical matching grid to identify records in the second dataset that match records in the first dataset on ones of the plurality of variables defined by the match criteria.

7. A method as defined in claim 1, wherein fusing the records in the first and second sets of match candidates based on the probabilities associated with the records includes establishing the probabilities based on weights associated with records from at least one of the first and second sets of match candidates.

8. A method as defined in claim 1, further comprising:

comparing a first sum of weights associated with the first set of match candidates with a second sum of weights associated with the second set of match candidates;

identifying one of the first and second sets of match candidates as overweight based on the comparison of the first and second sums of weights; and

trimming records of one of the first and second sets of match candidates identified as overweight prior to fusing the records in the first and second sets of match candidates.

9. A system for fusing first and second datasets, comprising:

a memory; and

a processor coupled to the memory and configured to;

determine an importance ranking of a plurality of variables associated with the first and second datasets;

generate a hierarchical matching grid including a plurality of levels based on the importance ranking of the plurality of variables, wherein each of the levels defines match criteria for satisfying a matching records condition by indicating which of the variables are to match;

identify first and second sets of match candidates from the first and second datasets based on one of the plurality of levels of the hierarchical matching grid; and

fuse records in the first and second sets of match candidates based on probabilities associated with the records.

10. A system as defined in claim 9, wherein the processor is configured to determine the importance ranking of the plurality of variables by ranking the plurality of variables based on a relative strength of a relationship between each of the variables and a respondent characteristic.

11. A system as defined in claim 9, wherein the processor is configured to generate the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables by generating a series of binary values for each level of the hierarchical grid so that each of a plurality of bit positions associated with the binary values uniquely corresponds to one of the plurality of variables, wherein the binary values define whether a corresponding one of the variables is to match in the first and second sets of match candidates.

12. A system as defined in claim 9, wherein the processor is configured to generate the hierarchical matching grid having the plurality of levels based on the importance ranking of the plurality of variables by generating the hierarchical matching grid to allow skewed matching on one or more of the variables.

13. A system as defined in claim 9, wherein the processor is configured to generate the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables by establishing a minimum matching level.

14. A system as defined in claim 9, wherein the processor is configured to identify the first and second sets of match candidates from the first and second datasets based on the one of the plurality of levels of the hierarchical matching grid by using match criteria from the one of the plurality of levels of the hierarchical matching grid to identify records in the second dataset that match records in the first dataset on ones of the plurality of variables defined by the match criteria.

15. A system as defined in claim 9, wherein the processor is configured to fuse the records in the first and second sets of match candidates based on the probabilities associated with the records by establishing the probabilities based on weights associated with records from at least one of the first and second sets of match candidates.

16. A system as defined in claim 9, wherein the processor is configured to:

compare a first sum of weights associated with the first set of match candidates with a second sum of weights associated with the second set of match candidates;

identify one of the first and second sets of match candidates as overweight based on the comparison of the first and second sums of weights; and

trim records of the one of the first and second sets of match candidates identified as overweight prior to fusing the records in the first and second sets of match candidates.

17. A machine readable medium having instructions stored thereon that, when executed, cause a machine to:

determine an importance ranking of a plurality of variables associated with first and second datasets;

generate a hierarchical matching grid including a plurality of levels based on the importance ranking of the plurality of variables, wherein each of the levels defines match criteria for satisfying a matching records condition by indicating which of the variables are to match;

identify first and second sets of match candidates from the first and second datasets based on one of the plurality of levels of the hierarchical matching grid; and

fuse records in the first and second sets of match candidates based on probabilities associated with the records.

18. A machine readable medium as defined in claim 17 having instructions stored thereon that, when executed, cause the machine to determine the importance ranking of the plurality of variables by ranking the plurality of variables based on a relative strength of a relationship between each of the variables and a respondent characteristic.

19. A machine readable medium as defined in claim 17 having instructions stored thereon that, when executed, cause the machine to generate the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables by generating a series of binary values for each level of the hierarchical grid so that each of a plurality of bit positions associated with the binary values uniquely corresponds to one of the plurality of variables, wherein the binary values define whether a corresponding one of the variables is to match in the first and second sets of match candidates.

20. A machine readable medium as defined in claim 17 having instructions stored thereon that, when executed, cause the machine to generate the hierarchical matching grid including the plurality of levels based on the importance ranking of the plurality of variables by generating the hierarchical matching grid to allow skewed matching on one or more of the variables.