Methods for generating selection structures, for making selections according to selection structures and for creating selection descriptions

摘要

A real-time system receives a selection structure formed by weighted rules joined by links, each of the weighted rules including a condition part, a conclusion part and a weight. The selection structure is an Algebraic Decision Diagram (ADD) that includes internal nodes, each representing a decision point and terminal nodes, each representing a subset of candidate results having an accumulated weight. In response to a query that specifies a set of conditions, the ADD is traversed by making a series of decisions at decision points of the ADD to reach at least one terminal node having a maximum accumulated weight among terminal nodes that satisfy the set of conditions. The subset of candidate results represented by the at least one terminal node is selected as the output for responding to the query.

主权项

1. A method performed by a real-time system for making a selection from a selection structure in response to a query, the method comprising:
receiving an Algebraic Decision Diagram (ADD) of the selection structure generated from a plurality of weighted rules joined by links, each of the weighted rules including a condition part that further includes at least one argument predicate, a conclusion part that further includes at least one result predicate, and a weight, the ADD generated via a sequence of operations, at least one of the operations comprising:
linking at least two weighted rules to form an intermediate ADD that includes a path connecting one or more internal nodes to a terminal node, wherein each internal node represents a decision point at which the argument predicate is evaluated;identifying a set of result predicates that satisfy all argument predicates along the path;keeping at least one result predicate in the set of result predicates to be represented by the terminal node, the at least one result predicate having a maximum accumulated weight among the set of result predicates; andremoving result predicates not having the maximum accumulated weight from the set of result predicates represented by the terminal node; traversing the ADD in response to the query that specifies a set of argument predicates by making a series of decisions at decision points of the ADD to reach at least one terminal node; and generating an output including one or more result predicates represented by the at least one terminal node.