Devices and methods for efficient execution of rules using pre-compiled directed acyclic graphs

Abstract

In one aspect, a computer implemented method for translating and executing rules using a directed acyclic graph is provided. The method includes transforming a ruleset into a directed acyclic graph. The directed acyclic graph includes a plurality of nodes and a plurality of branches. The method further includes identifying similarities across the plurality of branches. The method further includes grouping branches of the directed acyclic graph based on the identified similarities. The method further includes creating a modified directed acyclic graph based on the grouping. The method further includes selecting and using a method of processing a group of the modified directed acyclic graph based on an aspect of the group.

What is claimed is: 
     
         1 . A computer implemented method for efficient execution of one or more rules in a ruleset, the method comprising:
 transforming a ruleset into a directed acyclic graph by converting at least one of an input type of the ruleset or a default output type of the ruleset to a different type, the directed acyclic graph comprising a plurality of nodes and a plurality of branches;   identifying similarities across the plurality of branches; grouping, by the at least one processor, branches of the directed acyclic graph based on the identified similarities; and   creating a modified directed acyclic graph based on the grouping by determining redundant branch conditions of the directed acyclic graph based on the identified similarities;   selecting a method of processing a group of the modified acyclic graph based on an aspect the group.   
     
     
         2 . The method of  claim 1 , wherein processing a group of the modified acyclic graph is based on an aspect the group, and the plurality of branches comprises one or more branch conditions identifying properties of nodes associated with a given branch. 
     
     
         3 . The method of  claim 1 , wherein the identifying comprises:
 comparing a first condition of a first branch with a second condition of a second branch; and   determining, based on the comparing, whether the first branch condition and the second branch condition satisfy a similarity threshold.   
     
     
         4 . The method of  claim 3 , wherein the comparing is based on a variable or a property in which the first branch and/or the second branch are formed on. 
     
     
         5 . The method of  claim 4 , wherein the comparing is further based on special values included in the first branch and/or the second branch. 
     
     
         6 . The method of  claim 1 , wherein the grouping comprises:
 determining that a first branch and a second branch of the plurality of branches satisfy a similarity threshold; and   combining, in response to satisfying the similarity threshold, the first branch with the second branch.   
     
     
         7 . The method of  claim 6 , wherein the modified directed acyclic graph comprises the combined branch. 
     
     
         8 . The method of  claim 1 , wherein creating the modified directed acyclic graph comprises:
 combining, by the at least one processor, branches comprising the redundant branch conditions; and   generating, by the at least one processor, the modified directed acyclic graph with the combined branches.   
     
     
         9 . The method of  claim 1 , wherein selecting a method of processing comprises selecting a hash-based method, a binary search method, a sequential method, and/or a Boolean split method. 
     
     
         10 . The method of  claim 1 , further comprising transforming the modified directed acyclic graph into a program that is based on a concurrent, class-based, object-oriented computer programming language. 
     
     
         11 . The method of  claim 10 , where the transforming comprises: converting an incompatible input type of the ruleset into a compatible input type. 
     
     
         12 . The method of  claim 10 , where the transforming comprises: converting a default output type of the ruleset into a specific output type. 
     
     
         13 . The method of  claim 1 , further comprising:
 serializing the modified directed acyclic graph into an array of bytes;   compressing the array of bytes;   encoding the compressed array of bytes into an array of characters; and   embedding the array of characters into a string literal value.   
     
     
         14 . The method of  claim 13 , further comprising:
 decoding the array of characters into the compressed array of bytes;   de-compressing the array of bytes; and   de-serializing the array of bytes into the modified directed acyclic graph.   
     
     
         15 . A system comprising:
 at least one programmable processor; and   a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations comprising:   transforming a ruleset into a directed acyclic graph, the directed acyclic graph comprising a plurality of nodes and a plurality of branches;   identifying similarities across the plurality of branches;   grouping branches of the directed acyclic graph based on the identified similarities;   creating a modified directed acyclic graph based on the grouping;   selecting a method of processing a group of the modified acyclic graph based on an aspect of the group.   
     
     
         16 . The system of  claim 15 , wherein the identifying comprises:
 comparing a first condition of a first branch with a second condition of a second branch;   determining, based on the comparing, whether the first branch condition and the second branch condition satisfy a similarity threshold; and   combining, in response to satisfying the similarity threshold, the first branch with the second branch.   
     
     
         17 . The system of  claim 16 , wherein the comparing is based on a variable or a property in which the first branch and/or the second branch are formed on. 
     
     
         18 . The system of  claim 15 , wherein creating the modified directed acyclic graph comprises:
 determining redundant branch conditions of the directed acyclic graph based on the identified similarities;   combining branches comprising the redundant branch conditions; and   generating the modified directed acyclic graph with the combined branches.   
     
     
         19 . The system of  claim 11 , wherein selecting a method of processing comprises selecting a hash-based method, a binary search method, a sequential method, and/or a Boolean split method. 
     
     
         20 . A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause at least one programmable processor to perform operations comprising:
 transforming a ruleset into a directed acyclic graph, the directed acyclic graph   comprising a plurality of nodes and a plurality of branches;   identifying similarities across the plurality of branches;   grouping branches of the directed acyclic graph based on the identified similarities;   creating a modified directed acyclic graph based on the grouping;   selecting a method of processing a group of the modified acyclic graph based on an aspect of the group.