SCALING USER AUDIENCE GROUPS TO FACILITATE ADVERTISEMENT TARGETING

1 . A method comprising:

receiving, from a third party system, a plurality of business rules specifying criteria for whether a user of an online system is to be included in each of a plurality of audience groups, each business rule including one or more conditions for associating a user with an audience group and each audience group including one or more users;

generating a decision tree including the plurality of business rules;

receiving contextual information from a client device associated with a user of the online system, the contextual information describing an interaction between the user and content of the third party system;

determining, using the decision tree, one or more audience groups associated with the user based on a portion of the received contextual information;

selecting an advertisement for presentation to the user based on the one or more audience groups associated with the user; and

providing the selected advertisement to the client device of the user.

2 . The method of claim 1 , wherein a plurality of nodes in the decision tree identify audience groups, a path from a root node of the decision tree to a node that identifies at least one audience group representing the one or more conditions for associating a user with the at least one audience group.

3 . The method of claim 2 , wherein generating the decision tree comprises:

generating one or more paths for a business rule, a node terminating each path identifying the audience group associated with the business rule; and

combining the paths corresponding to the plurality of business rules.

4 . The method of claim 3 , wherein generating the one or more paths for the business rule comprises:

generating a tree structure comprising the one or more conditions associated with the business rule;

extracting one or more rule fragments from the tree structure; and

generating a path for each of the extracted rule fragments.

5 . The method of claim 2 , wherein determining using the decision tree, one or more audience groups associated with the user comprises:

traversing one or more paths of the decision tree using the contextual information;

storing identifiers of nodes traversed; and

associating the user with the audience groups corresponding to the traversed nodes.

6 . The method of claim 1 , wherein generating the decision tree comprises:

sorting the conditions associated with the plurality of business rules; and

generating the decision tree based on the sorted conditions.

7 . The method of claim 1 , wherein receiving the contextual information comprises:

receiving the contextual information responsive to the client device executing one or more instructions included in the content of the third party system to communicate the contextual information to the online system.

8 . The method of claim 1 , further comprising:

accessing a plurality of advertisement requests, each advertisement request specifying targeting criteria comprising one or more audience groups;

wherein selecting the advertisement for presentation to the user comprises selecting an ad request having targeting criteria specifying the one or more audience groups associated with the user.

9 . A method comprising:

receiving, from a client device associated with a user of an online system, contextual information describing an interaction between the user and content of a third party system;

determining one or more audience groups associated with the user based on a portion of the contextual information and a decision tree, a plurality of nodes in the decision tree identifying audience groups and a path from a root node of the decision tree to a node that identifies at least one audience group representing one or more conditions for associating a user with the at least one audience group;

selecting an advertisement for presentation to the user based on the one or more audience groups associated with the user; and

providing the selected advertisement to the client device of the user.

10 . The method of claim 9 , wherein the decision tree is generated by the online system based on a plurality of business rules received from the third party system, each business rule including one or more conditions for associating a user with an audience group.

11 . The method of claim 9 , wherein determining one or more audience groups associated with the user comprises:

traversing one or more paths of the decision tree using the contextual information;

storing identifiers of nodes traversed; and

associating the user with the audience groups corresponding to the traversed nodes.

12 . The method of claim 9 , wherein receiving the contextual information comprises:

receiving the contextual information responsive to the client device executing one or more instructions included in the content of the third party system to communicate the contextual information to the online system.

13 . The method of claim 9 , further comprising:

accessing a plurality of advertisement requests, each advertisement request specifying targeting criteria comprising one or more audience groups;

wherein selecting the advertisement for presentation to the user comprises selecting an ad request having targeting criteria specifying the one or more audience groups associated with the user.

14 . A computer program product comprising a non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:

receive, from a third party system, a plurality of business rules specifying criteria for whether a user of an online system is to be included in each of a plurality of audience groups, each business rule including one or more conditions for associating a user with an audience group and each audience group including one or more users;

generate a decision tree including the plurality of business rules;

receive contextual information from a client device associated with a user of the online system, the contextual information describing an interaction between the user and content of the third party system;

determine, using the decision tree, one or more audience groups associated with the user based on a portion of the received contextual information;

select an advertisement for presentation to the user based on the one or more audience groups associated with the user; and

provide the selected advertisement to the client device of the user.

15 . The computer program product of claim 14 , wherein a plurality of nodes in the decision tree identify audience groups, a path from a root node of the decision tree to a node that identifies at least one audience group representing the one or more conditions for associating a user with the at least one audience group.

16 . The computer program product of claim 15 , wherein the instructions causing the processor to generate the decision tree comprise instructions that when executed by the processor cause the processor to:

generate one or more paths for a business rule, a node terminating each path identifying the audience group associated with the business rule; and

combine the paths corresponding to the plurality of business rules.

17 . The computer program product of claim 16 , wherein the instructions causing the processor to generate the one or more paths for the business rule comprise instructions that when executed by the processor cause the processor to:

generate a tree structure comprising the one or more conditions associated with the business rule;

extract one or more rule fragments from the tree structure; and

generate a path for each of the extracted rule fragments.

18 . The computer program product of claim 15 , wherein the instructions causing the processor to determine using the decision tree, one or more audience groups associated with the user comprise instructions that when executed by the processor cause the processor to:

traverse one or more paths of the decision tree using the contextual information;

store identifiers of nodes traversed; and

associate the user with the audience groups corresponding to the traversed nodes.

19 . The computer program product of claim 14 , wherein the instructions causing the processor to generate the decision tree comprise instructions that when executed by the processor cause the processor to:

sort the conditions associated with the plurality of business rules; and

generate the decision tree based on the sorted conditions.

20 . The computer program product of claim 14 , further comprising instructions that when executed by the processor cause the processor to:

access a plurality of advertisement requests, each advertisement request specifying targeting criteria comprising one or more audience groups;

wherein the instructions causing the processor to select the advertisement for presentation to the user comprise instructions that when executed by the processor cause the processor to select an ad request having targeting criteria specifying the one or more audience groups associated with the user.