SEMANTIC MATCHING AND ANNOTATION OF ATTRIBUTES

• US 20150227589A1
• Filed: 02/10/2014
• Published: 08/13/2015
• Est. Priority Date: 02/10/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chakrabarti, Kaushik, Zhang, Meihui
• Granted Patent: US 10,726,018 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata

Abstract

Techniques and constructs to facilitate semantic matching and automated annotation (SMA) of attributes can take entity names and a keyword describing an attribute associated with the named entities as input and leverage a corpus of data such as data from tables, which can include HTML web tables, to automatically populate values associated with the named entities for the attribute. The constructs enable accurate SMA of attributes, such as attributes that relate to the entity and include numeric values in a different unit than the query, in a different scale than the query, and/or reflecting a time different from that of the query. An entity augmentation application programming interface (API) may be used to accept queries that include numeric criteria, parameters, or arguments, including query attributes represented by numeric values, which may be in different units or scales, and attributes represented by numeric values that can vary by time.

Claims

1. A system comprising:

one or more processing units; and

memory storing instructions that when executed by the one or more processing units, configure the one or more processing units to perform operations comprising;

accepting a query including;

an entity identifier, a keyword, at least one of a unit identifier or a scale identifier, and a time identifier;

acquiring data from a plurality of tables;

identifying at least one existing semantic label of at least a first of the plurality of tables from the data;

identifying that data from a least a second of the plurality of tables includes the entity identifier and the keyword and lacks at least one of the unit identifier, the scale identifier, or the time identifier;

identifying at least one conversion rule associated with the at least one existing semantic label;

normalizing the data from the plurality of tables, based at least in part on the query and the at least one conversion rule; and

outputting a result to the query normalized to show the data, including data from the second of the plurality of tables, in consistent units, scale, and time.

2. A system as claim 1 recites, further comprising:

building a semantic graph over at least the first table and the second table, the semantic graph suited for attributes, including attributes represented by numeric values, the semantic graph including;

the at least one existing semantic label; and

a semantic match; and

exposing results from the semantic match meeting the query, including results acquired via the semantic graph.

3. A system as claim 2 recites, wherein the semantic label represents at least one of unit, scale, or time at individual nodes of the graph.

4. A system as claim 2 recites, wherein a node of the semantic graph is assigned at least one scale label, at least one unit label, and a time label.

5. A method comprising:

extracting a plurality of tables via a computing device;

distinguishing, from the plurality of tables, relational tables from at least one other type of table

building a semantic graph based at least in part on a label from at least one of the relational tables; and

building at least a first index on the relational tables and the semantic graph.

6. A method as claim 5 recites, further comprising receiving a query including an entity identifier, a keyword, a unit identifier, a scale identifier, and a time identifier.

7. A method as claim 6 recites, further comprising receiving conversion rules associated with the label from the relational tables.

8. A method as claim 7 recites, wherein the label from the relational tables includes at least one of a scale label, a unit label, or a time label, and the conversion rules are associated with at least one of the scale label or the unit label.

9. A method as claim 8 recites, further comprising inferring label information for at least one table of the relational tables that lacks the scale label, the unit label, or the time label by applying the conversion rules.

10. A method as claim 9 recites, further comprising exposing the indexes to the query to provide an augmented table in which the label information includes label information inferred for data from the at least one table of the relational tables that lacks the scale label, the unit label, or the time label by applying the conversion rules.

11. A method as claim 5 recites, further comprising identifying a semantic label by extracting at least one of unit information, scale information, or year information from content of at least one of the plurality of tables, the content including a column header and a column value.

12. A method as claim 5 recites, further comprising identifying a semantic edge at least in part by using a tuple similarity between two columns, a first of the two columns from at least one of the plurality of tables and a second of the two columns from at least a second of the plurality of tables.

13. A method as claim 5 recites, further comprising identifying a semantic edge at least in part by using conversion rules.

14. A method as claim 5 recites, further comprising propagating a semantic label from one node of the semantic graph to another node of the semantic graph via a semantic edge.

15. A method as claim 5 recites, further comprising eliminating a spurious semantic match at least in part by recognizing an inconsistency between semantic labels, defining a hard constraint, and incorporating the hard constraint into the graph.

16. A method as claim 5 recites, further comprising addressing interdependence at least in part by representing semantic matching as a probabilistic graphical model.

17. A method as claim 16 recites, further comprising performing collective inference using the probabilistic graphical model at least in part by using a belief propagation algorithm.

18. A method as claim 5 recites, further comprising using a staged approach to build the semantic graph.

19. A method as claim 5 recites, further comprising distinguishing between two types of semantic matches among numeric columns of at least two of the plurality of tables, S edges and X edges, wherein an S edge exists between two tables of the plurality of tables that refer to entities of the same type having the same attributes expressed in the same unit and scale for the same period of time and wherein an X edge exists between two tables of the plurality of tables that refer to entities of the same type having the same attributes expressed in different units and/or scales for the same period of time.

20. One or more computer-readable media having computer executable instructions recorded thereon, the computer-executable instructions, upon execution, to configure a computing device to perform semantic matching and annotation of numeric attribute operations comprising:

receiving an entity augmentation query including a name of an entity, a keyword associated with the entity, time information associated with the keyword, and at least one of unit information associated with the keyword or scale information associated with the keyword;

processing the entity augmentation query based at least in part on existing conversion rules or graphs; and

exposing results for the entity augmentation query.

21. One or more computer-readable media as claim 20 recites, the operations further comprising exposing the entity augmentation query to indexes built on a plurality of tables.

22. One or more computer-readable media as claim 21 recites, the operations further comprising exposing results from a probabilistic graphical model to model discovery of labels and the discovery of matches.

23. One or more computer-readable media as claim 22 recites, wherein the exposing the results includes presenting the results from the probabilistic graphical model in a table format.

24. One or more computer-readable media as claim 20 recites, wherein the exposing the results includes exposing the results to a spreadsheet program.

25. One or more computer-readable media as claim 20 recites, wherein the exposing the results includes presenting the results in a table format.