Joining semantically-related data using big table corpora

• US 10,198,471 B2
• Filed: 05/31/2015
• Issued: 02/05/2019
• Est. Priority Date: 05/31/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: He, Yeye, Ganjam, Kris Kuppuswamy, Chu, Xu
• Primary Examiner(s): Waldron, Scott A.
• Assistant Examiner(s): Mina, Fatima P
• Application Number:
  US14/726,547
• Publication Number:
  US 20160350369A1
• Time in Patent Office: 1,346 Days
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Examples of the disclosure enable performing semantic joins using a big table corpus. Pairs of values from at least two data sets are identified. The pairs of values include one value from a first one of the data sets and one value from a second one of the data sets. Statistical co-occurrence scores for the identified pairs of values are determined based on historical co-occurrence data. The determined statistical co-occurrence scores are used for predicting a semantic relationship between the at least two data sets. The predicted semantic relationship is used for joining the at least two data sets.

Claims

1. A system for performing semantic join operations on data in different representations, said system comprising:

a memory area associated with a computing device, said memory area storing a plurality of tables having columns of values; and

a processor programmed to;

receive a request to perform a semantic join operation on at least two of the tables stored in the memory area;

in response to the received request, identify pairs of values from the at least two tables, the pairs of values including one value from a column in a first one of the tables and one value from a column in a second one of the tables;

determine, based on historical co-occurrence data, statistical co-occurrence scores for the identified pairs of values, wherein the statistical co-occurrence scores for the identified pairs of values are based on a row-level statistical co-occurrence score and a column-level statistical co-occurrence score;

infer a join relationship between the at least two tables using the statistical co-occurrence scores by generating a maximum aggregate correlation using the statistical co-occurrence scores; and

perform a semantic loin operation between the at least two tables using the statistical co-occurrence scores.

2. The system of claim 1, wherein the processor is programmed to identify the pairs of values by identifying a plurality of combinations of values from the first one of the tables and values from the second one of the tables.

3. The system of claim 1, wherein the processor is programmed to infer the join relationship by generating the maximum aggregate correlation score among all pairs of values, wherein the join relationship is automatically inferred if the maximum aggregate correlation score is above a threshold, and inferred join relationships are ranked for semantic joins.

4. The system of claim 1, wherein the historical co-occurrence data comprises at least one or more of a big table corpus, data from an enterprise database, and earlier co-occurrence data.

5. The system of claim 1, wherein the processor is further programmed to:

output a bridge table based on the inferred join relationship; and

perform a semantic join of the at least two of the tables using the bridge table.

6. The system of claim 1, wherein the statistical co-occurrence scores for the identified pairs of values is determined by:

crawling a plurality of relational tables;

measuring an aggregate correlation score for the identified pairs of values based on the crawled plurality of relational tables;

generating a portion of the historical co-occurrence data using the measured aggregate correlation score; and

calculating the statistical co-occurrence scores for the identified pairs of values based on the generated portion of the historical co-occurrence data.

7. The system of claim 6, wherein the aggregate correlation score is a measure of semantic relation between the identified pairs of values, the measure of semantic relation being derived from the plurality of relational tables.

8. The system of claim 1, wherein the processor is further programmed to:

crawl a plurality of relational tables, in an offline mode, to generate the statistical co-occurrence scores for pairs of values in the plurality of tables; and

store the generated statistical co-occurrence scores in the memory area.

9. A method comprising:

identifying pairs of values from at least two data sets, the pairs of values including one value from a first one of the data sets and one value from a second one of the data sets;

determining, based on historical co-occurrence data, statistical co-occurrence scores for the identified pairs of values, wherein the statistical co-occurrence scores for the identified pairs of values are based on a row-level statistical co-occurrence score and a column-level statistical co-occurrence score;

predicting, by a processor associated with a computing device, a semantic relationship between the at least two data sets using the determined statistical co-occurrence scores by generating a maximum aggregate correlation using the statistical co-occurrence scores to enable a semantic join operation between the at least two data sets; and

performing a semantic loin operation between the at least two data sets using the determined statistical co-occurrence scores.

10. The method of claim 9, wherein the identified pairs of values have different representations for the one value from the first one of the data sets and the one value from the second one of the data sets.

11. The method of claim 9, wherein the statistical co-occurrence scores for the identified pairs of values are based on one or more of a row-level statistical co-occurrence score and a column-level statistical co-occurrence score.

12. The method of claim 9, further comprising:

materializing the predicted semantic relationship as a bridge table;

enabling corrections, by a user of the computing device, to the predicted semantic relationship in the bridge table; and

updating the bridge table with the corrections to the predicted join relationship.

13. The method of claim 12, further comprising storing the updated bridge table as a portion of the historical co-occurrence data.

14. The method of claim 9, wherein the statistical co-occurrence scores are determined by:

calculating an aggregate correlation score for the identified pairs of values based on a plurality of relational tables; and

maximizing the aggregate correlation score for the identified pairs of values for predicting the semantic relationship.

15. The method of claim 14, wherein the aggregate correlation score is a measure of semantic relation between the identified pairs of values, the measure of semantic relation being derived from the plurality of relational tables.

16. The method of claim 14, wherein the plurality of relational tables are sourced from at least one of public web pages or an enterprise database.

17. The method of claim 9, wherein the semantic join operation comprises performing an equi-join between the at least two data sets without using an intermediate mapping table.

18. One or more computer storage media embodying computer-executable components, said components comprising:

an identification component that on execution by at least one processor causes the at least one processor to identify pairs of values from at least two data sets, the pairs of values including one value from a first one of the data sets and one value from a second one of the data sets;

a statistics serving component that on execution by at least one processor causes the at least one processor to calculate statistical co-occurrence scores for one or more of the identified pairs of values based on their strength of correlation in a big table corpus, wherein the statistical co-occurrence scores for the identified pairs of values are based on a row-level statistical co-occurrence score and a column-level statistical co-occurrence score;

a join path calculation component that on execution by at least one processor causes the at least one processor to compute a join relationship between the one or more of the identified pairs of values using the statistical co-occurrence scores by generating a maximum aggregate correlation using the statistical co-occurrence scores; and

a user interface component that on execution by at least one processor causes the at least one processor to present the computed join relationship to a user for performing semantic join of the at least two data sets,

wherein the join path calculation component that on execution by the at least one processor causes the at least one processor to perform a semantic join operation between the at least two data sets using the statistical co-occurrence scores.

19. The computer storage media of claim 18, further comprising a crawling component that on execution by at least one processor causes the at least one processor to crawl the big table corpus for determining the strength of correlation for one or more of the identified pairs of values.

20. The computer storage media of claim 18, wherein the statistical co-occurrence scores for the one or more of the identified pairs of values are based on one or more of a row-level statistical co-occurrence score and a column-level statistical co-occurrence score.