Method and system for distributed processing in a messaging platform

Patent metadata

Field	Value
Publication number	US-9858130-B2
Application number	US-201414498787-A
Country	US
Kind code	B2
Filing date	Sep 26, 2014
Priority date	Sep 26, 2013
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

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 (G T ), valuing partitioning G T 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.

First claim

What is claimed is:

1. A method for distributed processing, comprising:
receiving a first graph (G) comprising a plurality of targets and a plurality of influencers, wherein each of the plurality of influencers is related to at least one of the plurality of targets, and wherein each of the plurality of influencers and the plurality of targets corresponds to a respective account of a messaging system, and wherein the first graph indicates accounts as nodes and relationships between the accounts as edges connecting one or more nodes;
key partitioning G across a first physical shard and a second physical shard;
transposing the first graph (G) to obtain a first transposed graph (G T ), wherein the first transposed graph G T transposes the relationships between the nodes of G;
value partitioning G T across the first physical shard and the second physical shard;
in response to an action associated with a first account of the messaging system, issuing, to the first physical shard, a first request to perform a first intersection using G and G T , wherein the first request specifies an influencer of the plurality of influencers corresponding to the first account;
receiving a first response to the first request, wherein the first response comprises a set of influencers each of which is related to a first target of the plurality of targets, and wherein the set of influencers is calculated based at least on a portion of data resulting from the key partitioning and the value partitioning;
determining whether to send a recommendation to the second account of the messaging system corresponding to the first target based on the first response; and
in response to a determination to send the recommendation, sending the recommendation to the second account.

2. The method of claim 1 , further comprising:
issuing, to the second physical shard, a second request to perform a second intersection, wherein the second request specifies the influencer;
receiving in a second response to the second intersection, wherein the second response comprises a second set of influencers each of which is related to the first target; and
wherein determining whether to send the recommendation to the first target is further based on the second response.

3. The method of claim 1 , wherein the key partitioning of G results in at least a first key partitioned graph (K(G1)) on the first shard and a second key partitioned graph (K(G2)) on the second shard, and wherein the value partitioning of G T results in at least a first value partitioned graph (V(G1 T )) on the first physical shard and a second value partitioned graph (V(G2 T )) on the second physical shard.

4. The method of claim 3 , further comprising:
value partitioning G across the first physical shard and the second physical shard, wherein the value partitioning of G results in at least a third value partitioned graph (V(G1)) on the first physical shard and a fourth value partitioned graph (V(G2)) on the second physical shard;
key partitioning G T across the first physical shard and the second physical shard plurality of physical shards, wherein the key partitioning of G T results in at least a third key partitioned graph (K(G1 t )) on the first physical shard and a fourth key partitioned graph (K(G2 T )) on the second physical shard;
issuing a second request to the first physical shard, where the request requires the first physical shard to use at least one selected from a group consisting of K(G1), V(G1) and K(G1 T ), and V(G1 T ); and
receiving a second response to the second request.

5. The method of claim 4 , wherein the second request is one selected from a group consisting of a first degree query, a second degree query, an intersection query, and a collaborative filtering query.

6. The method of claim 4 , further comprising:
selecting the first physical shard to perform the second request, wherein the second request specifies a member in G and the first physical shard is selected by applying a hash function using the member as an input to the hash function, wherein the member is one selected from a group consisting of a target in G and an influencer in G.

7. The method of claim 4 , further comprising:
issuing a third request to the second physical shard, wherein the third request requires the second physical shard to use one selected from a group consisting of K(G2), V(G2) and K(G2), and V(G2 T ); and
receiving a third response to the third request.

8. The method of claim 7 , further comprising:
generating a final response using the second response and the third response.

9. The method of claim 3 , further comprising:
receiving an action graph comprising a plurality of actions performed by one or more of the plurality of influencers;
issuing, to the first physical shard, a second request to perform a second intersection, wherein the second request specifies a second influencer;
performing, using the second influencer as a key, a look-up in V(G1 T ) to obtain a first set of targets;
performing, using a first target in the set of targets as a key, a look-up in K(G1) to obtain a first set of influencers for the first target;
performing the second intersection between the first set of influencers and the action graph to obtain a second set of influencers;
providing a response to the second request comprising the second set of influencers.

10. The method of claim 9 , wherein the plurality of actions were performed within a time frame.

11. The method of claim 9 , wherein the second set of influencers are related to the first target based on a follow.

12. The method of claim 9 , wherein G1 comprises a plurality of targets and a plurality of influencers, wherein each of the plurality of influencers is related to at least one of the plurality of targets, wherein V(G1 T ) is derived from G1.

13. The method of claim 9 , wherein G1 comprises a plurality of targets and a plurality of influencers, wherein each of the plurality of influencers is related to at least one of the plurality of targets, wherein K(G1) is derived from G1.

14. The method of claim 9 , wherein the action graph comprises a plurality of actions performed by one or more of the plurality of influencers.

15. The method of claim 14 , wherein the plurality of actions comprise one or more of: a follow, viewing a profile, retweeting, sending a direct message, sending a tweet, and favoriting.

16. The method of claim 1 , wherein key partitioning G across the first physical shard and the second physical shard comprises using a hash function and wherein valuing partitioning Gr across the first physical shard and the second physical shard comprises using the hash function.

17. The method of claim 1 , wherein the plurality of influences are related to one or more of the plurality of targets based on a follow.

18. The method of claim 1 , wherein the recommendation is sent to the first target when the size of the set of influencers is greater than 2.

19. The method of claim 1 , wherein the first physical shard is partitioned in to a plurality of nodes, and wherein the K(G1) and V(G1 T ) are located on a node of the plurality of nodes on the first physical shard.

20. The method of claim 1 , wherein a number of influencers of the plurality of influencers for any target in K(G1) is ≦200.

21. The method of claim 1 , wherein the first response to the first request is generated based on:
look-up a first key associated with the influencer associated with the event in the value partition of G T on the first p

Assignees

• Twitter Inc

Inventors

• Grewal Ajeet
• Gurumurthy Siva
• Satuluri Venumadhav
• Gupta Pankaj
• Larson Brian
• Zhabuik Volodymyr
• Sharma Aneesh
• Goel Ashish

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/245

  Query processing · CPC title

• G06F9/46 Primary

  Multiprogramming arrangements · CPC title

• G06F9/546 Primary

  Message passing systems or structures, e.g. queues · CPC title

• G06F17/30958

  Physics · mapped topic