Generalized engine for predicting actions

• US 10,169,711 B1
• Filed: 09/27/2016
• Issued: 01/01/2019
• Est. Priority Date: 06/27/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Dean, Jeffrey A.
• Primary Examiner(s): Henderson, Esther B.
• Assistant Examiner(s): Mahmud, Golam
• Application Number:
  US15/277,306
• Time in Patent Office: 826 Days
• Field of Search: 709204
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/041 Abduction
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/142 Managing session states for stateless protocols; Signalling session states; State transitions; Keeping-state mechanisms
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for predicting actions based on large-scale aggregations of data. One of the methods includes obtaining user activity data organized into sessions, the user activity data representing user activities, each session including one or more user activities for a particular user, the sessions including sessions for multiple users; receiving a session query, the session query including a query term representing a query activity; identifying matching sessions, the matching sessions each satisfying the session query; identifying likely activities in the matching sessions, likely activities being activities found in the matching sessions that satisfy the session query and occur in the matching sessions more frequently than in sessions in general; and identifying one or more of the likely activities in a response to the session query.

Claims

1. A prediction computer system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

receiving, by the prediction computer system, a query requesting one or more predicted activities that are likely to be performed by users having a particular attribute;

determining, by the prediction computer system, a plurality of matching sessions from user session data of a plurality of users, each matching session of the plurality of matching sessions being a user session for a user having the particular attribute of the query, wherein each user session for each user of the plurality of users includes data representing one or more user activities performed by the user during a particular time period,

wherein the user session data is partitioned into a plurality of shards, each shard of the plurality of shards being stored on one of multiple index servers of the prediction computer system, wherein the index servers include a root server and a plurality of leaf servers;

computing, by the prediction computer system for each activity of a plurality of activities represented in the matching sessions, a respective lower bound of a number of distinct users having data contributing to the activity in the matching sessions for the activity,

wherein computing a lower bound for an activity comprises;

hashing, by each leaf server for each matching session, a portion of a respective user identifier associated with the matching session to generate one or more user key positions for the matching session,

generating, by each leaf server for each activity of one or more activities occurring in the matching sessions stored in the shard assigned to the leaf server, a respective merged user key for the activity including setting each position in the merged user key indicated by any user key position generated for matching sessions having the activity,

generating, by the root server for each activity of one or more activities occurring in the matching sessions, an overall merged user key for the activity including setting each position in the overall merged user key indicated by any set position in any merged user key received from the leaf servers for matching sessions having the activity, and

computing, by the root server for each activity of one or more activities occurring in the matching sessions, a count of positions that are set in the overall merged user key for the activity;

computing, by the prediction computer system, for each user activity of one or more activities having a lower bound that satisfies a threshold;

a respective first score representing a likelihood that the user activity occurs in the plurality of matching sessions;

a respective second score representing a likelihood that the user activity occurs in any of the user sessions of the user session data;

a respective third score that measures a relative magnitude of the first score compared to the second score;

designating, as the one or more predicted activities, one or more of the user activities having a third score that satisfies a threshold; and

providing, by the prediction computer system and based on the designation of the one or more user activities as the one or more predicted activities, data representing a respective predicted activity for each of the one or more predicted activities.

2. The prediction computer system of claim 1, wherein the operations further comprise preventing information leaks of information that occurs in less than a minimum number of sessions or for less than a minimum number of users.

3. The prediction computer system of claim 1, wherein the operations further comprise organizing user activity data into a plurality of sessions, each session including data representing one or more user activities of a single respective user, the sessions including sessions for multiple users.

4. The prediction computer system of claim 3, wherein organizing the user activity data into the plurality of sessions comprises organizing the user activity data into sessions representing non-overlapping time periods of a fixed, predetermined duration.

5. The prediction computer system of claim 3, wherein the prediction computer system is one subsystem in an environment having multiple subsystems,

wherein organizing the user activity data into the plurality of sessions comprises receiving, from another subsystem of the multiple subsystems, data representing user activities performed within the other subsystem, and

wherein receiving the a query requesting predicted activities comprises receiving the query from the other subsystem.

6. The prediction computer system of claim 5, wherein the other subsystem comprises an email subsystem, a social networking subsystem, a video sharing subsystem, or a search engine subsystem.

7. A computer-implemented method comprising:

receiving, by a prediction computer system, a query requesting predicted activities that are likely to be performed by users having a particular attribute;

determining, by the prediction computer system, a plurality of matching sessions from user session data of a plurality of users, each matching session of the plurality of matching sessions being a user session for a user having the particular attribute of the query, wherein each user session for each user of the plurality of users includes data representing one or more user activities performed by the user during a particular time period,

wherein the user session data is partitioned into a plurality of shards, each shard of the plurality of shards being stored on one of multiple index servers of the prediction computer system, wherein the index servers include a root server and a plurality of leaf servers;

computing, by the prediction computer system for each activity of a plurality of activities represented in the matching sessions, a respective lower bound of a number of distinct users having data contributing to the activity in the matching sessions for the activity,

wherein computing a lower bound for an activity comprises;

hashing, by each leaf server for each matching session, a portion of a respective user identifier associated with the matching session to generate one or more user key positions for the matching session,

generating, by each leaf server for each activity of one or more activities occurring in the matching sessions stored in the shard assigned to the leaf server, a respective merged user key for the activity including setting each position in the merged user key indicated by any user key position generated for matching sessions having the activity,

generating, by the root server for each activity of one or more activities occurring in the matching sessions, an overall merged user key for the activity including setting each position in the overall merged user key indicated by any set position in any merged user key received from the leaf servers for matching sessions having the activity, and

computing by the root server for each activity of one or more activities occurring in the matching sessions, a count of positions that are set in the overall merged user key for the activity;

computing, by the prediction computer system, for each user activity of one or more activities having a lower bound that satisfies a threshold;

a respective first score representing a likelihood that the user activity occurs in the plurality of matching sessions;

a respective second score representing a likelihood that the user activity occurs in any of the user sessions of the user session data;

a respective third score that measures a relative magnitude of the first score compared to the second score;

designating, as the one or more predicted activities, one or more of the user activities having a third score that satisfies a threshold; and

providing, by the prediction computer system and based on the designation of the one or more user activities as the one or more predicted activities, data representing a respective predicted activity for each of the one or more predicted activities.

8. The method of claim 7, further comprising preventing information leaks of information that occurs in less than a minimum number of sessions or for less than a minimum number of users.

9. The method of claim 7, further comprising organizing user activity data into a plurality of sessions, each session including data representing one or more user activities of a single respective user, the sessions including sessions for multiple users.

10. The method of claim 9, wherein organizing the user activity data into the plurality of sessions comprises organizing the user activity data into sessions representing non-overlapping time periods of a fixed, predetermined duration.

11. The method of claim 9, wherein the prediction computer system is one subsystem in an environment having multiple subsystems,

wherein organizing the user activity data into the plurality of sessions comprises receiving, from another subsystem of the multiple subsystems, data representing user activities performed within the other subsystem, and

wherein receiving the a query requesting predicted activities comprises receiving the query from the other subsystem.

12. The method of claim 11, wherein the other subsystem comprises an email subsystem, a social networking subsystem, a video sharing subsystem, or a search engine subsystem.

13. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers of a prediction computer system cause the one or more computers to perform operations comprising:

receiving, by the prediction computer system, a query requesting predicted activities that are likely to be performed by users having a particular attribute;

determining, by the prediction computer system, a plurality of matching sessions from user session data of a plurality of users, each matching session of the plurality of matching sessions being a user session for a user having the particular attribute of the query, wherein each user session for each user of the plurality of users includes data representing one or more user activities performed by the user during a particular time period,

wherein the user session data is partitioned into a plurality of shards, each shard of the plurality of shards being stored on one of multiple index servers of the prediction computer system, wherein the index servers include a root server and a plurality of leaf servers;

computing, by the prediction computer system for each activity of a plurality of activities represented in the matching sessions, a respective lower bound of a number of distinct users having data contributing to the activity in the matching sessions for the activity,

wherein computing a lower bound for an activity comprises;

hashing, by each leaf server for each matching session, a portion of a respective user identifier associated with the matching session to generate one or more user key positions for the matching session,

generating, by each leaf server for each activity of one or more activities occurring in the matching sessions stored in the shard assigned to the leaf server, a respective merged user key for the activity including setting each position in the merged user key indicated by any user key position generated for matching sessions having the activity,

generating, by the root server for each activity of one or more activities occurring in the matching sessions, an overall merged user key for the activity including setting each position in the overall merged user key indicated by any set position in any merged user key received from the leaf servers for matching sessions having the activity, and

computing by the root server for each activity of one or more activities occurring in the matching sessions, a count of positions that are set in the overall merged user key for the activity;

computing, by the prediction computer system, for each user activity of one or more activities having a lower bound that satisfies a threshold;

a respective first score representing a likelihood that the user activity occurs in the plurality of matching sessions;

a respective second score representing a likelihood that the user activity occurs in any of the user sessions of the user session data;

a respective third score that measures a relative magnitude of the first score compared to the second score;

designating, as the one or more predicted activities, one or more of the user activities having a third score that satisfies a threshold; and

providing, by the prediction computer system and based on the designation of the one or more user activities as the one or more predicted activities, data representing a respective predicted activity for each of the one or more predicted activities.

14. The computer program product of claim 13, wherein the operations further comprise preventing information leaks of information that occurs in less than a minimum number of sessions or for less than a minimum number of users.

15. The computer program product of claim 13, wherein the operations further comprise organizing user activity data into a plurality of sessions, each session including data representing one or more user activities of a single respective user, the sessions including sessions for multiple users.

16. The computer program product of claim 15, wherein organizing the user activity data into the plurality of sessions comprises organizing the user activity data into sessions representing non-overlapping time periods of a fixed, predetermined duration.

17. The computer program product of claim 15, wherein the prediction computer system is one subsystem in an environment having multiple subsystems,

wherein organizing the user activity data into the plurality of sessions comprises receiving, from another subsystem of the multiple subsystems, data representing user activities performed within the other subsystem, and

wherein receiving the a query requesting predicted activities comprises receiving the query from the other subsystem.

18. The computer program product of claim 17, wherein the other subsystem comprises an email subsystem, a social networking subsystem, a video sharing subsystem, or a search engine subsystem.