Efficient probabilistic reasoning over semantic data

A computing device for performing probabilistic reasoning over a semantic graph, the computing device comprising:

• a processor configured to execute computer-executable instructions;
• and
• memory storing computer-executable instructions for:
• providing a semantic graph formed by a plurality of concepts connected together via probabilistic assertions;
• receiving a query;
• identifying edges within the semantic graph that can be collapsed based on one or more collapsing rules, to provide identified edges, wherein:
• the identified edges belong to at least one path through the semantic graph that addresses the query, and
• said one or more collapsing rules include a series-type collapsing rule specifying that two edges can be combined if the two edges are connected in series in a manner that is independent of other edges in the semantic graph;
• collapsing the identified edges into a single edge having a resultant probability associated therewith;
• repeating said identifying and said collapsing until no additional collapsible edges are identified in the semantic graph, to provide a remaining graph;
• and
• generating an answer to the query based on the remaining graph.

A computer-readable storage device storing computer-executable instructions that, when executed by one or more processing devices of a computing device, causes the computing device to perform a method comprising:

• receiving a query;
• providing a semantic graph formed by a plurality of concepts connected together via probabilistic assertions;
• identifying edges within the semantic graph that can be collapsed based on one or more collapsing rules, to provide identified edges, wherein:
• the identified edges belong to at least one path through the semantic graph that addresses the query, and
• said one or more collapsing rules include a series-type collapsing rule specifying that two edges can be combined if the two edges are connected in series in a manner that is independent of other edges in the semantic graph;
• collapsing the identified edges into a single edge having a resultant probability associated therewith,
• repeating said identifying and said collapsing until no additional collapsible edges are identified in the semantic graph, to yield a remaining graph;
• and
• generating an answer to the query based on a the remaining graph.