Dynamic expressions for representing features in an online system

Patent metadata

Field	Value
Publication number	US-10395321-B2
Application number	US-201213690088-A
Country	US
Kind code	B2
Filing date	Nov 30, 2012
Priority date	Nov 30, 2012
Publication date	Aug 27, 2019
Grant date	Aug 27, 2019

Abstract

Online systems, for example, social networking systems evaluate expressions based on features describing relations between entities represented in the online system. These expressions are represented using an expression language. The expression language allows features to be specified as functions of attributes from user accounts. The expressions support use of variables to represent computations, for example, sub-expressions. The expressions are dynamic, since expressions can be specified and executed at call time. The same set of expressions is used many times, e.g., to compute the same function for multiple feature sets, for example, user accounts. Expressions are preferably represented using postfix representation. However some expressions, for example, expressions using variables are represented as trees. To optimize the expressions at runtime, the expressions are cached using a representation determined to be efficient for executing the expression. The cached representation of the expression is applied to multiple feature sets, for example, user accounts.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, by a social networking system, information describing a plurality of expressions, each expression specifying a set of computations using an expression language, each expression comprising operands and one or more operators for combining the operands into a result, the operands comprising attributes of entities represented in the social networking system;
for each expression of the plurality of expressions:
determining whether the expression includes a variable term referring to a different expression using the expression language;
selecting a type of representation for the expression by selecting between a tree representation and a postfix representation based at least in part on whether the expression includes a variable term referring to a different expression,
generating a data structure representing the expression by converting the expression from the expression language to the selected type of representation, and
storing the generated data structure in a cache;

receiving a request to evaluate an expression for a set of entities represented in the social networking system, the request associated with a viewing user;
accessing, from a feature store of the social networking system, values of operands included in the requested expression for the set of entities;
accessing the data structure representing the requested expression from the cache;
determining, by a processor, an expression result for each entity of the set of entities by evaluating the requested expression using the data structure representing the expression accessed from the cache and using the values of the operands of the requested expression accessed from the feature store;
selecting one or more of the entities based on a ranking of the set of entities according to the expression result for each entity; and
providing the selected one or more entities for presentation to the viewing user.

2. The computer-implemented method of claim 1 ,
wherein selecting the type of representation for the expression comprises selecting the postfix representation over the tree representation responsive to determining that the expression does not include any variable term, and
wherein generating the data structure representing the expression comprises generating a stack structure to represent the postfix representation.

3. The computer-implemented method of claim 1 , wherein the selected type of representation is the postfix representation, wherein determining the expression result for an entity comprises:
sequentially reading the one or more operators and the operands from the postfix representation of the expression;
responsive to reading an operand, pushing the operand onto a stack data structure; and
responsive to reading an operator,
popping a number of operands from the stack data structure, the number of operands corresponding to the operator,
determining a result of the operator by combining the number of operands popped from the stack according to the operator, and
pushing the result of the operator to the stack data structure.

4. The computer-implemented method of claim 1 ,
wherein selecting the type of representation for the expression comprises:
selecting the tree representation responsive to determining that the expression includes the variable term.

5. The computer-implemented method of claim 1 ,
wherein selecting the type of representation for the expression comprises:
selecting the postfix representation responsive to determining that the expression does not include any variable term.

6. The computer-implemented method of claim 1 , further comprising:
receiving a modified expression corresponding to an expression stored in the cache; and
modifying the representation of the expression in the cache based on the modified expression.

7. The computer-implemented method of claim 1 , further comprising:
receiving a modified expression corresponding to an expression stored using the postfix representation in the cache, the modified expression including at least one variable term representing at least one different expression; and
changing the representation of the expression in the cache to the tree representation.

8. The computer-implemented method of claim 1 , further comprising:
receiving a modified expression corresponding to an expression stored using the tree representation in the cache, the modified expression lacking variable terms representing different expressions; and
changing the representation of the expression in the cache to the postfix representation.

9. The computer-implemented method of claim 1 , wherein the set of entities corresponds to a set of connections of a user, wherein selecting the one or more of the entities comprises:
ranking the connections from the set of connections using results of evaluation of the expression.

10. The computer-implemented method of claim 1 , wherein the set of entities corresponds to a set of content items for presentation to a user, wherein selecting the one or more entities comprises:
ranking the content items from the set of content items using results of evaluation of the expression; and
selecting one or more content items for presentation to the user based on the ranks of the content items.

11. A computer program product having a non-transitory computer-readable storage medium storing computer-executable code executable to cause a processor to:
receive information describing a plurality of expressions, each expression specifying a set of computations using an expression language, each expression comprising operands and one or more operators for combining the operands into a result, the operands comprising attributes of entities represented in the social networking system;
for each expression of the plurality of expressions:
determine whether the expression includes a variable term referring to a different expression using the expression language;
select a type of representation for the expression by selecting between a tree representation and a postfix representation based at least in part on whether the expression includes a variable term representing a different expression,
generate a data structure representing the expression by converting the expression from the expression language to the selected type of representation, and
store the generated data structure in a cache;

access, from a feature store of the social networking system, values of operands included in the requested expression for the set of entities;
access the data structure representing the requested expression from the cache;
receive a request to evaluate an expression for a set of entities represented in the social networking system; and
determine an expression result for each entity of the set of entities by evaluating the requested expression using the data structure representing the expression accessed from the cache and using the values of the operands of the requested expression accessed from the feature store.

12. The computer program product of claim 11 ,
wherein selecting the type of representation for the expression comprises selecting the postfix representation over the tree representation responsive to determining that the expression does not include any variable term, and
wherein generating the data structure representing the expression comprises generating a stack structure to represent the postfix representation.

13. The computer program product of claim 11 ,
wherein selecting the type of representation for the expression comprises:
selecting the tree presentation responsive to determining that the expression incl

Assignees

• Facebook Inc

Inventors

• Shalita Alon Michael
• Hua Ming
• Stout Ryan Allen

Classifications

• G06Q10/40 Primary

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

• G06Q30/0255 Primary

  based on user history · CPC title

• G06Q50/01 Primary

  Physics · mapped topic

• G06Q10/42

  Determination of affinities or common interests between users · CPC title

• G06Q10/48

  using social graphs · CPC title