Distributed processing in a messaging platform

Abstract

A method for distributed processing involves receiving a graph (G) of targets and of influencers, with each influencer related to at least one target, receiving an action graph of actions performed by one or more of the influencers, and key partitioning G across shards. The method further involves transposing the first graph (G) to obtain a first transposed graph (GT), value partitioning GT across the shards, storing the action graph on multiple shards, issuing, to a shard, a request specifying an influencer, to perform an intersection, receiving a response to the request of a set of influencers each of which is related to a target, and determining whether to send a recommendation to the target based on the response.

1 . (canceled) 
     
     
         2 . A method comprising:
 receiving a graph G representing relationships between user accounts of a messaging platform, the user accounts being represented by nodes of G and having edges between nodes where each edge represents a relationship between a pair of user accounts;   key partitioning G to generate key partitioned graphs and distributing the key partitioned graphs across a plurality of physical shards, wherein distributing the key partitioned graphs results in at least storing a first key partitioned graph on a first shard of the plurality of physical shards and storing a second key partitioned graph on a second shard of the plurality of physical shards;   value partitioning G to generate value partitioned graphs and distributing the value partitioned graphs across the plurality of physical shards, wherein distributing the value partitioned graphs results in at least storing a first value partitioned graph on the first shard and storing a second value partitioned graph on the second shard;   receiving a request to determine one or more user accounts that have a relationship two degrees from a first user account;   issuing, to each shard, a first request to look up second user accounts in the respective value partitioned graphs that have a first degree connection with the first user account;   issuing, to each shard, a second request to look up third user accounts in the respective key partitioned graphs having a first degree connection with a second user account of the one or more second user accounts;   generating a union of the third user accounts received from each shard; and   determining whether to send a recommendation to the first user account based on the one or more third user accounts.   
     
     
         3 . The method of  claim 2 , further comprising:
 receiving an action graph representing actions performed by users, wherein the action graph includes a set of subgraphs of the form C←[b 1 , . . . , b n ], with C corresponding to a particular action and [b 1 , . . . , b n ] corresponding to a set of user accounts for users that have performed the particular action.   
     
     
         4 . The method of  claim 3 , wherein determining whether to send a recommendation to the first user account comprises:
 intersecting the one or more third user accounts with a particular action of the action graph to determine which third user accounts have performed the particular action; and   sending a recommendation to the first user account based on the particular action.   
     
     
         5 . The method of  claim 4 , wherein determining whether to send the recommendation to the first user account includes determining whether the particular action was performed by a specified number of third user accounts. 
     
     
         6 . The method of  claim 2 , wherein determining whether to send the recommendation to the first user account includes determining to send a recommendation to form a graph relationship with one or more third user accounts. 
     
     
         7 . The method of  claim 2 , wherein the request to determine user accounts that have a relationship two degrees from the first user account comprises a request for a top K user accounts, the method further comprising generating a local union at each shard of the results of the first request and the second request; and returning top K results of the local union. 
     
     
         8 . The method of  claim 2 , wherein the request to determine user accounts that have a relationship two degrees from a first user account comprises a request for a random user account, the method further comprising: selecting at each shard, from the results of the second request, a random third user account; and randomly selecting a third user account from the union of the third user accounts received from each shard. 
     
     
         9 . A system comprising:
 one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:   receiving a graph G representing relationships between user accounts of a messaging platform, the user accounts being represented by nodes of G and having edges between nodes where each edge represents a relationship between a pair of user accounts;   key partitioning G to generate key partitioned graphs and distributing the key partitioned graphs across a plurality of physical shards, wherein distributing the key partitioned graphs results in at least storing a first key partitioned graph on a first shard of the plurality of physical shards and storing a second key partitioned graph on a second shard of the plurality of physical shards;   value partitioning G to generate value partitioned graphs and distributing the value partitioned graphs across the plurality of physical shards, wherein distributing the value partitioned graphs results in at least storing a first value partitioned graph on the first shard and storing a second value partitioned graph on the second shard;   receiving a request to determine one or more user accounts that have a relationship two degrees from a first user account;   issuing, to each shard, a first request to look up second user accounts in the respective value partitioned graphs that have a first degree connection with the first user account;   issuing, to each shard, a second request to look up third user accounts in the respective key partitioned graphs having a first degree connection with a second user account of the one or more second user accounts;   generating a union of the third user accounts received from each shard; and   determining whether to send a recommendation to the first user account based on the one or more third user accounts.   
     
     
         10 . The system of  claim 9 , the operations further comprising:
 receiving an action graph representing actions performed by users, wherein the action graph includes a set of subgraphs of the form C←[b 1 , . . . , b n ], with C corresponding to a particular action and [b 1 , . . . , b n ] corresponding to a set of user accounts for users that have performed the particular action.   
     
     
         11 . The system of  claim 10 , wherein determining whether to send a recommendation to the first user account comprises:
 intersecting the one or more third user accounts with a particular action of the action graph to determine which third user accounts have performed the particular action; and   sending a recommendation to the first user account based on the particular action.   
     
     
         12 . The system of  claim 11 , wherein determining whether to send the recommendation to the first user account includes determining whether the particular action was performed by a specified number of third user accounts. 
     
     
         13 . The system of  claim 9 , wherein determining whether to send the recommendation to the first user account includes determining to send a recommendation to form a graph relationship with one or more third user accounts. 
     
     
         14 . The system of  claim 9 , wherein the request to determine user accounts that have a relationship two degrees from the first user account comprises a request for a top K user accounts, the operations further comprising generating a local union at each shard of the results of the first request and the second request; and returning top K results of the local union. 
     
     
         15 . The system of  claim 9 , wherein the request to determine user accounts that have a relationship two degrees from a first user account comprises a request for a random user account, the operations further comprising: selecting at each shard, from the results of the second request, a random third user account; and randomly selecting a third user account from the union of the third user accounts received from each shard. 
     
     
         16 . One or more non-transitory computer readable media comprising computer readable program code, which when executed by a computer processor causes the computer processor to perform operations comprising:
 receiving a graph G representing relationships between user accounts of a messaging platform, the user accounts being represented by nodes of G and having edges between nodes where each edge represents a relationship between a pair of user accounts;   key partitioning G to generate key partitioned graphs and distributing the key partitioned graphs across a plurality of physical shards, wherein distributing the key partitioned graphs results in at least storing a first key partitioned graph on a first shard of the plurality of physical shards and storing a second key partitioned graph on a second shard of the plurality of physical shards;   value partitioning G to generate value partitioned graphs and distributing the value partitioned graphs across the plurality of physical shards, wherein distributing the value partitioned graphs results in at least storing a first value partitioned graph on the first shard and storing a second value partitioned graph on the second shard;   receiving a request to determine one or more user accounts that have a relationship two degrees from a first user account;   issuing, to each shard, a first request to look up second user accounts in the respective value partitioned graphs that have a first degree connection with the first user account;   issuing, to each shard, a second request to look up third user accounts in the respective key partitioned graphs having a first degree connection with a second user account of the one or more second user accounts;   generating a union of the third user accounts received from each shard; and   determining whether to send a recommendation to the first user account based on the one or more third user accounts.   
     
     
         17 . The non-transitory computer readable media of  claim 16 , the operations further comprising:
 receiving an action graph representing actions performed by users, wherein the action graph includes a set of subgraphs of the form C←[b 1 , . . . , b n ], with C corresponding to a particular action and [b 1 , . . . , b n ] corresponding to a set of user accounts for users that have performed the particular action.   
     
     
         18 . The non-transitory computer readable media of  claim 17 , wherein determining whether to send a recommendation to the first user account comprises:
 intersecting the one or more third user accounts with a particular action of the action graph to determine which third user accounts have performed the particular action; and   sending a recommendation to the first user account based on the particular action.   
     
     
         19 . The non-transitory computer readable media of  claim 18 , wherein determining whether to send the recommendation to the first user account includes determining whether the particular action was performed by a specified number of third user accounts. 
     
     
         20 . The non-transitory computer readable media of  claim 16 , wherein determining whether to send the recommendation to the first user account includes determining to send a recommendation to form a graph relationship with one or more third user accounts. 
     
     
         21 . The non-transitory computer readable media of  claim 16 , wherein the request to determine user accounts that have a relationship two degrees from the first user account comprises a request for a top K user accounts, the operations further comprising generating a local union at each shard of the results of the first request and the second request; and returning top K results of the local union. 
     
     
         22 . The non-transitory computer readable media of  claim 16 , wherein the request to determine user accounts that have a relationship two degrees from a first user account comprises a request for a random user account, the operations further comprising: selecting at each shard, from the results of the second request, a random third user account; and randomly selecting a third user account from the union of the third user accounts received from each shard.