# US 2014/0156360 A1 · Dynamic expressions for representing features in an online system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0156360 A1
- Document ID: US20140156360A1
- Status: Published application
- Kind: A1
- Application number: 13/690,088
- Filed: 2012-11-30
- Published: 2014-06-05
- Earliest claimed: 2012-11-30
- Assignees: Facebook, Inc.
- Applicants: Facebook, Inc.
- Inventors: Alon Michael Shalita; Ming Hua; Ryan Allen Stout
- Web page: https://patentgrep.com/patent/US20140156360A1

## CPC

- G06Q 30/0255: {based on user history}
- G06Q 10/42: Determination of affinities or common interests between users
- G06Q 10/48: using social graphs
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## 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.

## Claims

### Claim 1

A computer-implemented method comprising:
receiving, by an online system, information describing a plurality of expressions, each expression specifying a function of attributes of entities represented in the online system;
for each of the plurality of expressions:
selecting a type of representation for the expression from a plurality of types of representation comprising a tree representation and a postfix representation, the selection based on an efficiency of evaluation of the expression using the type of representation,
generating a structure representing the expression based on the selected type of representation, and
storing the generated structure in a cache;
receiving, a request to evaluate an expression for a set of entities represented in the online system; and
evaluating the requested expression for all the entities from the set using the structure representing the expression from the cache.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein selecting a representation of the expression comprises selecting the postfix representation over the tree representation responsive to determining that the expression can be evaluated using the postfix representation.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein responsive to determining that the requested expression is stored as a postfix representation, evaluating a result of the postfix representation of the requested expression using a stack.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein an expression is specified using an expression language that supports identifying a set of computations by a variable, wherein selecting a representation of the expression comprises:
determining whether the expression includes a variable term; and
selecting a tree representation responsive to determining that the expression includes a variable term.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein an expression is specified using an expression language that supports identifying a set of computations by a variable, wherein selecting a representation of the expression comprises:
determining whether the expression includes a variable term; and
selecting a postfix representation responsive to determining that the expression lacks variable terms.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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

### Claim 8 (depends on 1)

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

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, further comprising:
receiving a new expression not stored in the cache; and
adding a representation of the new expression to the cache.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, wherein the online system is a social networking system and the set of entities corresponds to a set of connections of a user, the method further comprising:
ranking the connections from the set of connections using results of evaluation of the expression.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, wherein the online system is a social networking system and the set of entities corresponds to a set of advertisements for presentation to a user, the method further comprising:
ranking the advertisements from the set of advertisements using results of evaluation of the expression; and
selecting one or more advertisements for presentation to the user based on the ranks of the advertisements.

### Claim 12 (depends on 1)

The computer-implemented method of claim 1, wherein the online system is a social networking system and the set of entities corresponds to a set of newsfeed items for presentation to a user, the method further comprising:
ranking the newsfeed items from the set of newsfeed items using results of evaluation of the expression; and
selecting one or more newsfeed items for presentation to the user based on the ranks of the newsfeed items.

### Claim 13 (depends on 1)

The computer-implemented method of claim 1, wherein the online system is a social networking system and the set of entities corresponds to a set of content items for presentation to a user, the method further comprising:
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.

### Claim 14

A computer program product having a non-transitory computer-readable storage medium storing computer-executable code, the code comprising:
an expression manager module of an online system configured to:
receive information describing a plurality of expressions, each expression specifying a function of attributes of entities represented in the online system;
for each of the plurality of expressions:
select a type of representation for the expression from a plurality of types of representation comprising a tree representation and a postfix representation, the selection based on an efficiency of evaluation of the expression using the type of representation,
generate a structure representing the expression based on the selected type of representation, and
store the generated structure in a cache;
receive, a request to evaluate an expression for a set of entities represented in the online system; and
evaluate the requested expression for all the entities from the set using the structure representing the expression from the cache.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein selecting a representation of the expression comprises selecting the postfix representation over the tree representation responsive to determining that the expression can be evaluated using the postfix representation.

### Claim 16 (depends on 14)

The computer program product of claim 14, wherein an expression is specified using an expression language that supports identifying a set of computations by a variable, wherein selecting a representation of the expression comprises:
determining whether the expression includes a variable term; and
selecting a tree representation responsive to determining that the expression includes a variable term.

### Claim 17 (depends on 14)

The computer program product of claim 14, wherein an expression is specified using an expression language that supports identifying a set of computations by a variable, wherein selecting a representation of the expression comprises:
determining whether the expression includes a variable term; and
selecting a postfix representation responsive to determining that the expression lacks variable terms.

### Claim 18 (depends on 14)

The computer program product of claim 14, wherein the expression manager module is further configured to:
receive a modified expression corresponding to an expression stored in the cache; and
modify the representation of the expression in the cache based on the modified expression.

### Claim 19 (depends on 14)

The computer program product of claim 14, wherein the online system is a social networking system and the set of entities corresponds to a set of connections of a user, the expression manager module further configured to:
rank the connections from the set of connections using results of evaluation of the expression.

### Claim 20 (depends on 14)

The computer program product of claim 14, wherein the online system is a social networking system and the set of entities corresponds to a set of advertisements for presentation to a user, the expression manager module further configured to:
rank the advertisements from the set of advertisements using results of evaluation of the expression; and
select one or more advertisements for presentation to the user based on the ranks of the advertisements.

### Claim 21 (depends on 14)

The computer program product of claim 14, wherein the online system is a social networking system and the set of entities corresponds to a set of newsfeed items for presentation to a user, the expression manager module further configured to:
rank the newsfeed items from the set of newsfeed items using results of evaluation of the expression; and
selecting one or more newsfeed items for presentation to the user based on the ranks of the newsfeed items.

### Claim 22 (depends on 14)

The computer program product of claim 14, wherein the online system is a social networking system and the set of entities corresponds to a set of content items for presentation to a user, the expression manager module further configured to:
rank the content items from the set of content items using results of evaluation of the expression; and
select one or more content items for presentation to the user based on the ranks of the content items.