Policy performance ordering

Patent metadata

Field	Value
Publication number	US-9922123-B2
Application number	US-201414152109-A
Country	US
Kind code	B2
Filing date	Jan 10, 2014
Priority date	Jan 10, 2014
Publication date	Mar 20, 2018
Grant date	Mar 20, 2018

Abstract

Technology for optimizing policy evaluation is disclosed. A policy may include an ordered rule set. When evaluated, the highest priority rule in the order that does not skip may control the outcome of the policy. Rules within a policy may have associated costs and an associated probability of not skipping. The rules of a policy may not need to be executed in a particular order for a system to determine the correct evaluation of the policy and groups of rules, or “batches,” may be run simultaneously. Technology is disclosed to optimize policy evaluation by creating batches and orderings of those batches which have a lower expected cost than other ordered sets of batches. The expected cost for each ordered set of batches may be calculated based on: rule costs, probabilities associated with one or more rules, the organization of the rules into batches, and the ordering of batches within sets.

First claim

We claim:

1. A method performed by a computing device for reducing processing time for a policy, comprising:
receiving the policy that includes two or more rules organized in a priority ordering based on priority values assigned to the two or more rules,
wherein each rule of the two or more rules is associated with a condition,
wherein at least one rule of the two or more rules allows a particular action in an event that the condition evaluates to an outcome amounting to true and skips in an event that the condition evaluates to an outcome amounting to false,
wherein at least one other rule of the two or more rules denies the particular action in an event that the condition evaluates to an outcome amounting to true and skips in an event that the condition evaluates to an outcome amounting to false, and
wherein the outcome of the policy is determined by whichever rule is highest in the priority ordering that does not amount to a skip;

organizing the two or more rules into batches,
wherein each batch includes a determinative rule of a first type having a certain priority value and any rules of a second type having a priority value higher than the certain priority value;

identifying at least two ordered sets of batches,
wherein each ordered set of batches that includes two or more batches represents a different execution ordering for the two or more rules of the policy, and
wherein each ordered set of batches includes all of the two or more rules;

for each ordered set of batches,
computing an expected processing cost, wherein the expected processing cost is based on one or more of:
a processing cost and a probability associated with each rule, the probability indicative of a likelihood that the corresponding rule will not skip,
the organization of the two or more rules into batches for that ordered set of batches,
the relationship among the batches of that ordered set of batches, or
any combination thereof; and

selecting an ordered set of batches, from among the at least two ordered sets of batches, having a lowest expected processing cost, wherein executions of the policy conform to the execution ordering corresponding to the selected ordered set of batches.

2. The method of claim 1 , wherein executions of the policy that conform to the selected ordered set of batches are performed by:
for each selected batch in the selected ordered set of batches; performing one or more of:
gathering data for the selected batch concurrently;
executing the one or more rules in the selected batch as a group; or
any combination thereof.

3. A method performed by a computing device for reducing processing time for an ordered set of batches, comprising:
receiving a policy comprising two or more rules organized in a priority ordering based on priority values assigned to the two or more rules, wherein each rule of the policy has a corresponding type;
determining a processing cost associated with each rule of the two or more rules, the processing cost based on one or more of an execution cost for that rule and a data fetch cost for that rule;
organizing the two or more rules into batches;
identifying at least two ordered sets of batches, wherein each ordered set of batches comprises one or more batches, each ordered set of batches defines a relationship among the one or more batches of that ordered set of batches, and each ordered set of batches includes all of the two or more rules;
for each distinguished ordered set of the ordered sets of batches, computing an expected processing cost, wherein the expected processing cost is based on one or more of:
the processing cost determined for each rule and a probability indicative of a likelihood that rule will apply,
the organization of the two or more rules into batches for that distinguished ordered set of batches, and
the relationship among the one or more batches of that distinguished ordered set of batches; and

selecting an ordered set of batches with the lowest expected processing cost as representative for the policy;
wherein the relationship among the one or more batches of each ordered set of batches is created by:
creating one or more first batches;
for each distinguished previous batch of the distinguished ordered set of batches and for each distinguished possible outcome of the distinguished previous batch:
creating a copy of a partial ordered set of batches comprising that distinguished previous batch,
attaching, to that distinguished previous batch in the copy, a child structure, and
associating with the attachment between that distinguished previous batch and the child structure, a type corresponding to that distinguished possible outcome.

4. The method of claim 3 , wherein each distinguished child structure is created by determining, for this distinguished possible outcome:
a set of remaining rules; and
creating, as the distinguished child structure, a second optimized set of ordered rule batches for the remaining rules.

5. The method of claim 4 , wherein:
each of the first batches is a determinative batch corresponding to each of the two or more rules, and
each specific batch of each ordered set of batches that is not a first batch is a determinative set for the set of remaining rules for the previous batch before the specific batch.

6. The method of claim 1 , wherein the batches of each of the determined at least two ordered sets of batches are created by selecting all possible groupings of the two or more rules.

7. The method of claim 1 , wherein each expected processing cost is calculated by traversing that ordered set of batches and adding, for each batch in that set of batches, a product of (A) a probability that batch will be reached when the ordered set of batches is implemented and (B) the cost of executing that batch.

8. The method of claim 1 , wherein the probability is based on the probability associated with each rule in that batch.

9. The method of claim 1 , wherein at least one rule in the policy is itself a set of two or more rules.

10. The method of claim 1 , wherein for at least one of the distinguished ordered sets, one or both of the processing cost determined for at least one rule and the probability is based on observed results of evaluating one or more of the two or more rules.

11. A computer readable memory device storing instructions configured to, when executed by a computing device, cause the computing device to perform operations for reducing processing time for an ordered set of batches, the operations comprising:
receiving a policy that includes two or more rules organizing in a priority ordering based on priority values assigned to the two or more rules, wherein each rule of the two or more rules has a corresponding type;
for each distinguished rule of the two or more rules, creating a determinative batch;
identifying at least two ordered sets of batches, wherein:
for each distinguished ordered set of the ordered sets of batches:
the distinguished ordered set comprises at least one of the determinative batches as a first batch;
the distinguished ordered set defines a relationship among the batches of that distinguished ordered set of batches such that:
for each distinguished possible outcome of possible outcomes of a previous batch:
 the previous batch has attached to it one or more subsequent child structures, and
 the association between the previous batch and each child structure has a type corresponding to the distinguished possible outcome; and
the rules of all batches of the distinguished ordered set includes all of the two or more rules; and

for each distinguished ordered set of batches, calculating an expected processing cost, the expected pro

Assignees

• Facebook Inc

Inventors

• Yung Raylene
• Pimenova Maria S
• Schafer Daniel
• Reeves Dwayne
• Mu Wendy
• Hopkins Kendall

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06F16/9535 Primary

  Search customisation based on user profiles and personalisation · CPC title

• G06F11/3404

  for parallel or distributed programming · CPC title

• G06F8/443

  Optimisation · CPC title

• G06F16/957 Primary

  Browsing optimisation, e.g. caching or content distillation · CPC title