Applications that involve functions requiring choosing a rule from a set of prespecified rules typically employ rule engines that apply suitable algorithms, such as the Rete algorithm, to select the most appropriate rule from the rule set. However, such algorithms do not scale well for large rule sets and are unsuitable for handling real-time rule selection. This disclosure describes a rule engine that operates by mapping the set of rules as nodes within a K-D tree. The mapping requires that each rule be represented geometrically as a point in an N-dimensional space by considering the ranges created by intersecting ranges derived from all the conditions of a rule. Once all rules in the underlying rule set are mapped onto a K-D tree in such a manner, finding the rules applicable to an input is achieved by turning the input into a ranged query that identifies a region of the N-dimensional space and using a K-D tree query algorithm to find all rules contained within that region.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Rossini, Mirko, "Application of K-D Trees for the Implementation of a Rule Engine", Technical Disclosure Commons, (June 02, 2021)