Querying features based on user actions in online systems

• US 9,195,705 B2
• Filed: 05/15/2014
• Issued: 11/24/2015
• Est. Priority Date: 11/30/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Stout, Ryan Allen, Hua, Ming, Yan, Hong
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US14/278,382
• Publication Number:
  US 20140250137A1
• Time in Patent Office: 558 Days
• Field of Search: 707/722, 707728-730, 707/748, 707/758
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Online systems, for example, social networking systems store features describing relations between entities represented in the online system. The information describing the features is represented as a graph. The online system maintains a cumulative feature graph and an incremental feature graph. Feature values based on recent user actions are stored in the incremental graph and feature values based on previous actions are stored in the cumulative graph. Periodically, the information stored in the incremental feature graph is merged with the information stored in the cumulative feature graph. The incremental graph is marked as inactive during the merge and information based on new user actions is stored in an active incremental feature graph. If a request for feature information is received, the feature information obtained from the cumulative feature graph, inactive incremental feature graph and the active incremental feature graph are combined to determine the feature information.

Claims

1. A computer-implemented method comprising:

accessing a cumulative feature store storing feature values determined from user actions performed before a time point;

accessing an incremental feature store storing feature values determined from user actions performed after the time point;

calculating, by a computer processor of an online system, a weighted combination of feature values from the incremental feature store and corresponding feature values from the cumulative feature store;

updating the cumulative feature store by replacing the corresponding feature values in the cumulative feature store with the weighted combination of feature values;

receiving an update to one or more of the feature values stored in the incremental feature store, the update comprising a new value for one or more of the feature values; and

updating the incremental feature store based on the received update by replacing the corresponding feature values in the incremental feature store with feature values in the received update.

2. The computer-implemented method of claim 1, wherein a feature is represented as an expression based on one or more of values describing user actions or other feature values.

3. The computer-implemented method of claim 1, wherein the weighted combination of feature values includes a third corresponding feature value.

4. The computer-implemented method of claim 1, wherein the incremental feature store is a first incremental feature store, further comprising:

maintaining, by the online system, a second incremental feature store;

marking the first incremental feature store as inactive at a subsequent time point; and

updating features of the second incremental feature store responsive to user actions received by the online system after the subsequent time point.

5. The computer-implemented method of claim 4, further comprising:

calculating, by the computer processor, a weighted combination of feature values from the first incremental feature store, from the second incremental feature store, and from the cumulative feature store.

6. The computer-implemented method of claim 1, further comprising:

storing the incremental feature store in a data store that provides faster data access compared to a data store used for the cumulative feature store.

7. The computer-implemented method of claim 1, wherein the incremental feature store is stored in random access memory.

8. The computer-implemented method of claim 1, wherein each feature is associated with a user, a target entity, and a feature value based on user actions performed by the user associated with the target entity.

9. The computer-implemented method of claim 1, wherein each feature is weighted by a decay factor.

21. The computer-implemented method of claim 1, further comprising storing, by a social networking system, information describing a plurality of users and connections between users, the social networking system allowing users to interact with each other, and wherein:

the cumulative feature store is a cumulative feature graph comprising nodes representing entities in the social networking system and edges representing features associated with a source entity and target entity, and

the incremental feature store is an incremental feature graph comprising nodes and edges.

10. A computer program product having a non-transitory computer-readable storage medium storing computer-executable code, the code comprising:

a feature manager module of an online system configured to;

access a cumulative feature store storing feature values determined from user actions performed before a time point;

access an incremental feature store storing feature values determined from user actions performed after the time point;

a request processor module configured to;

calculate, by a computer processor of the online system, a weighted combination of feature values from the incremental feature store and corresponding feature values from the cumulative feature store;

update the cumulative feature store by replacing the corresponding feature values in the cumulative feature store with the weighted combination of feature values;

receive an update to one or more of the feature values stored in the incremental feature store, the update comprising a new value for one or more of the feature values; and

update, based on the received update, the incremental feature store by replacing the corresponding feature values in the incremental feature store with feature values in the received update.

11. The computer program product of claim 10, wherein a feature is represented as an expression based on one or more of values describing user actions or other feature values.

12. The computer program product of claim 10, wherein the weighted combination of feature values includes a third corresponding feature value.

13. The computer program product of claim 10, wherein the incremental feature store is a first incremental feature store, further comprising a feature manager of an online system configured to:

maintain, by the online system, a second incremental feature store;

mark the first incremental feature store as inactive at a subsequent time point; and

update features of the second incremental feature store responsive to user actions received by the online system after the subsequent time point.

14. The computer program product of claim 13, further comprising a feature manager of an online system configured to:

calculate, by the computer processor, a weighted combination of feature values from the first incremental feature store, from the second incremental feature store, and from the cumulative feature store.

15. The computer program product of claim 10, further comprising a request processor module configured to:

store the incremental feature store in a data store that provides faster data access compared to a data store used for the cumulative feature store.

16. The computer program product of claim 10, wherein the incremental feature store is stored in random access memory.

17. The computer program product of claim 10, wherein each feature is associated with a user, a target entity, and a feature value based on user actions performed by the user associated with the target entity.

18. The computer program product of claim 10, wherein each feature is weighted by a decay factor.

22. The computer program product of claim 10, wherein:

the cumulative feature store is a cumulative feature graph comprising nodes representing entities in a social networking system and edges representing features associated with a source entity and target entity, and

the incremental feature store is an incremental feature graph comprising nodes and edges.

19. A computer program product comprising a nontransitory computer-readable storage medium containing computer program code for:

accessing a cumulative feature store storing feature values determined from user actions performed before a time point;

accessing an incremental feature store storing feature values determined from user actions performed after the time point;

calculating, by a computer processor of an online system, a weighted combination of feature values from the incremental feature store and corresponding feature values from the cumulative feature store;

updating the cumulative feature store by replacing the corresponding feature values in the cumulative feature store with the weighted combination of feature values;

receiving an update to one or more of the feature values stored in the incremental feature store, the update comprising a new value for one or more of the feature values; and

updating the incremental feature store based on the received update by replacing the corresponding feature values in the incremental feature store with feature values in the received update.

20. The computer program product of claim 19, wherein a feature is represented as an expression based on one or more of values describing user actions or other feature values.

23. The computer program product of claim 19, wherein:

the cumulative feature store is a cumulative feature graph comprising nodes representing entities in a social networking system and edges representing features associated with a source entity and target entity, and

the incremental feature store is an incremental feature graph comprising nodes and edges.