# US 2015/0089514 A1 · Method and system for distributed processing in a messaging platform

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

- Number: US 2015/0089514 A1
- Document ID: US20150089514A1
- Status: Published application
- Kind: A1
- Application number: 14/498,787
- Filed: 2014-09-26
- Published: 2015-03-26
- Earliest claimed: 2013-09-26
- Assignees: Twitter, Inc.
- Applicants: Twitter, Inc.
- Inventors: Ajeet Grewal; Siva Gurumurthy; Venumadhav Satuluri; Pankaj Gupta; Brian Larson; Volodymyr Zhabuik; Aneesh Sharma; Ashish Goel
- Web page: https://patentgrep.com/patent/US20150089514A1

## CPC

- G06F 9/546: {Message passing systems or structures, e.g. queues}
- G06F 9/46: Multiprogramming arrangements
- G06F 16/245: Query processing
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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), valuing 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.

## Claims

### Claim 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;
key partitioning G across a first physical shard and a second physical shard;
transposing the first graph (G) to obtain a first transposed graph (GT);
value partitioning GT across the first physical shard and the second physical shard;
issuing, to the first physical shard, a first request to perform a first intersection, wherein the first request specifies an influencer of the plurality of influencers;
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 the value partitioning; and
determining whether to send a recommendation to the first target based on the first response.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 55)

The method of claim 55, 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 GT across the first physical shard and the second physical shard, wherein the key partitioning of GT results in at least a third key partitioned graph (K(G1T)) on the first physical shard and a fourth key partitioned graph (K(G2T)) 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(G1T), and V(G1T); and
receiving a second response to the second request.

### Claim 4 (depends on 3)

The method of claim 3, 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.

### Claim 5 (depends on 3)

The method of claim 3, 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.

### Claim 6 (depends on 3)

The method of claim 3, 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(G2T), and V(G2T); and
receiving a third response to the third request.

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 1)

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 GT across the first physical shard and the second physical shard comprises using the hash function.

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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(G1T) are located on a node of the plurality of nodes on the first physical shard.

### Claim 12

(canceled)

### Claim 13 (depends on 1)

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

### Claim 14 (depends on 49)

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

### Claim 15

A system, comprising:
a first physical shard;
a second physical shard; and
a cross partitioning engine including functionality to:
receive 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;
key partition G across the first physical shard and the second physical shard;
transpose the first graph (G) to obtain a first transposed graph (GT);
value partition GT across the first physical shard and the second physical shard;
issue, to the first physical shard, a first request to perform a first intersection, wherein the first request specifies an influencer of the plurality of influencers;
receive 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; and
determine whether to send a recommendation to the first target based on the first response.

### Claim at position 16

-28. (canceled)

### Claim 29

A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to;
receive 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;
key partition G across a first physical shard and a second physical shard;
transpose the first graph (G) to obtain a first transposed graph (GT);
value partition GT across the first physical shard and the second physical shard;
issue, to the first physical shard, a first request to perform a first request, wherein the first request specifies an influencer of the plurality of influencers;
receive 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; and
determine whether to send a recommendation to the first target based on the first response.

### Claim at position 18

-48. (canceled)

### Claim 49 (depends on 55)

The method of claim 55, 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(G1T) 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.

### Claim 50 (depends on 49)

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

### Claim 51 (depends on 49)

The method of claim 49, 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(G1T) is derived from G1.

### Claim 52 (depends on 49)

The method of claim 49, 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.

### Claim 53 (depends on 49)

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

### Claim 54 (depends on 53)

The method of claim 53, 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.

### Claim 55 (depends on 1)

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 GT results in at least a first value partitioned graph (V(G1T)) on the first physical shard and a second value partitioned graph (V(G2T)) on the second physical shard.
