SOCIAL NETWORKING FEED DELIVERY SYSTEM AND METHOD

• US 20140006503A1
• Filed: 07/02/2012
• Published: 01/02/2014
• Est. Priority Date: 07/02/2012
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Aristides Gionis
• Inventors: Weber, Ingmar, Serafini, Marco, GIonis, Aristides, Junoueira, Flavio
• Granted Patent: US 8,671,141 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Disclosed herein are a system, method and architecture for optimizing a manner in which queries and updates are issued to data stores servicing an application such as a social networking application. A social graph modeling a social network may be used to generate a data store request schedule that optimizes, e.g., minimizes, data store accesses, such as without limitation queries and updates to the data store.

Claims

1. A method comprising:

obtaining, via at least one computing device, a social graph representing a plurality of social network users as a plurality of content consumers and content producers of the social network, each content producer producing, and each content consumer consuming, one or more items of content, the social graph identifying a content sharing relationship for a consumer-producer pair comprising a content consumer and content producer of the plurality of content consumers and content producers, the content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer;

selecting, via the at least one computing device from the plurality of content consumers and content producers, a content sharing hub for at least one consumer-producer pair, the content sharing hub having a content sharing relationship with each of the content consumer and the content producer of the consumer-producer pair; and

defining, via the at least one computing device, a new content sharing relationship for the consumer-producer pair using the content sharing hub, the new content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer via the content sharing hub.

2. The method of claim 1, the new content sharing relationship for the consumer-producer pair comprising a push strategy to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by the content producer from the content sharing hub to the content consumer.

3. The method of claim 1, selecting a new content sharing relationship for the consumer-producer pair further comprising:

determining a cost of the content sharing relationship for the consumer-producer pair;

determining a cost of the new content sharing relationship for the consumer-producer pair; and

selecting the new content sharing relationship over the content sharing relationship where the cost of the content sharing relationship is greater than the cost of the new content sharing relationship.

4. The method of claim 1, wherein there are a plurality of consumer-producer pairs for the plurality of content consumers and content producers, selecting a new content sharing relationship for the consumer-producer pair further comprising:

determining a plurality of subgraphs of the social graph, each subgraph having as its content sharing hub one of the plurality of content consumers and content producers and comprising one or more consumer-producer pairs of the plurality of consumer-producer pairs and a consumer and producer for each of the one or more consumer-producer pairs;

determining a cost for each subgraph; and

repeatedly selecting one of the plurality of subgraphs based on the cost determined for each subgraph until it is determined that each consumer-producer pair of the plurality of consumer-producer pairs is covered by a content sharing hub of a selected subgraph of the plurality of subgraphs, wherein a selected subgraph has the content sharing hub that is used to define the new content sharing relationship.

5. The method of claim 4, repeatedly selecting one of the plurality of subgraphs based on the cost determined for each subgraph further comprising:

selecting a subgraph of the plurality of subgraphs, the selected subgraph having a minimum cost relative to the cost of each other subgraph of the plurality of subgraphs;

removing the selected subgraph from the plurality of subgraphs;

specifying a push strategy for each producer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub and a pull strategy for each consumer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub; and

repeatedly selecting a subgraph, removing the selected subgraph and specifying the push and pull strategies until it is determined that each consumer-producer pair of the plurality is covered.

6. The method of claim 4, determining a cost for each subgraph further comprising:

determining a number of consumer-producer pairs in the subgraph;

determining a number of consumers and producers in the subgraph; and

determining the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the number of consumers and producers in the subgraph.

7. The method of claim 4, determining a cost for each subgraph further comprising:

determining a number of consumer-producer pairs in the subgraph;

determining a weighted cost sum comprising the content-consuming rate of each consumer and the content-production rate of each producer in the subgraph; and

determining the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the weighted cost sum.

8. The method of claim 1, wherein the social graph represents each content consumer and each content producer of the plurality of content consumers and content producers as a vertex of a plurality of vertices of the social graph, selecting a content sharing hub for at least one consumer-producer pair further comprising:

selecting a first vertex of the plurality of vertices of the social graph;

selecting a second vertex of the plurality of vertices of the social graph, the social graph indicating that the first vertex is in a consumer-producer pair with the second vertex;

identifying at least one third vertex selected from the plurality of vertices, the social graph indicating that each third vertex is in a consumer-producer pair with the first vertex and is in a consumer-producer pair with the second vertex;

determining a cost of sharing content without using the second vertex as the content sharing hub for the first vertex and the at least one third vertex;

determining a cost of sharing content using the second vertex as the candidate sharing hub for the first vertex and the at least one third vertex; and

selecting the third vertex as the content sharing hub for the first vertex and the at least one third vertex where the cost of sharing content without the third vertex as the content sharing hub is greater than the cost of sharing content using the third vertex as the content sharing hub.

9. The method of claim 8, the first vertex represents a content consumer and each third vertex represents one content producer of the plurality of content consumers and content producers, the method further comprising:

using a push strategy for each content producer to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by each content producer from the content sharing hub to the content consumer.

10. The method of claim 8, further comprising:

determining whether there is at least one other content consumer that is in a consumer-producer pair with at least one content producer represented by a third vertex and is in a consumer-producer pair with the content sharing hub; and

performing the following where it is determined that there is at least one other content consumer;

determining a cost of sharing content without using the second vertex as the content sharing hub between the at least one other content consumer and the at least one content producer;

determining a cost of sharing content using the second vertex as the candidate sharing hub between the at least one other content consumer and the at least one content producer; and

selecting the third vertex as the content sharing hub for sharing content between the at least one other content consumer and the at least one content producer where the cost of sharing content without the third vertex as the content sharing hub is more than the cost of sharing content using the third vertex as the content sharing hub.

11. The method of claim 8, further comprising:

determining that there is at least one consumer-producer pair of the plurality for which a content sharing hub is not selected, and performing the following for each of the at least one consumer-producer pair;

obtaining a content-producing rate at which the content producer produces the one or more items of content;

obtaining a content-consuming rate at which the content consumer consumes one or more items of content; and

selecting between a push strategy and a pull strategy for delivering the one or more items of content from the content producer to the content consumer based on the content-consuming rate of the content consumer and the content-producing rate of the content producer, wherein;

with the push strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is produced by the content producer; and

with the pull strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is consumed by the content consumer.

12. A system comprising:

at least one computing device comprising one or more processors to execute and memory to store instructions to;

obtain a social graph representing a plurality of social network users as a plurality of content consumers and content producers of the social network, each content producer producing, and each content consumer consuming, one or more items of content, the social graph identifying a content sharing relationship for a consumer-producer pair comprising a content consumer and content producer of the plurality of content consumers and content producers, the content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer;

select, from the plurality of content consumers and content producers, a content sharing hub for at least one consumer-producer pair, the content sharing hub having a content sharing relationship with each of the content consumer and the content producer of the consumer-producer pair; and

define a new content sharing relationship for the consumer-producer pair using the content sharing hub, the new content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer via the content sharing hub.

13. The system of claim 12, the new content sharing relationship for the consumer-producer pair comprising a push strategy to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by the content producer from the content sharing hub to the content consumer.

14. The system of claim 12, the instructions to select a new content sharing relationship for the consumer-producer pair further comprising instructions to:

determine a cost of the content sharing relationship for the consumer-producer pair;

determine a cost of the new content sharing relationship for the consumer-producer pair; and

select the new content sharing relationship over the content sharing relationship where the cost of the content sharing relationship is greater than the cost of the new content sharing relationship.

15. The system of claim 12, wherein there are a plurality of consumer-producer pairs for the plurality of content consumers and content producers, the instructions to select a new content sharing relationship for the consumer-producer pair further comprising instructions to:

determine a plurality of subgraphs of the social graph, each subgraph having as its content sharing hub one of the plurality of content consumers and content producers and comprising one or more consumer-producer pairs of the plurality of consumer-producer pairs and a consumer and producer for each of the one or more consumer-producer pairs;

determine a cost for each subgraph; and

repeatedly select one of the plurality of subgraphs based on the cost determined for each subgraph until it is determined that each consumer-producer pair of the plurality of consumer-producer pairs is covered by a content sharing hub of a selected subgraph of the plurality of subgraphs, wherein a selected subgraph has the content sharing hub that is used to define the new content sharing relationship.

16. The system of claim 15, the instructions to repeatedly select one of the plurality of subgraphs based on the cost determined for each subgraph further comprising instructions to:

select a subgraph of the plurality of subgraphs, the selected subgraph having a minimum cost relative to the cost of each other subgraph of the plurality of subgraphs;

remove the selected subgraph from the plurality of subgraphs;

specify a push strategy for each producer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub and a pull strategy for each consumer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub; and

repeatedly select a subgraph, remove the selected subgraph and specify the push and pull strategies until it is determined that each consumer-producer pair of the plurality is covered.

17. The system of claim 15, the instructions to determine a cost for each subgraph further comprising instructions to:

determine a number of consumer-producer pairs in the subgraph;

determine a number of consumers and producers in the subgraph; and

determine the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the number of consumers and producers in the subgraph.

18. The system of claim 15, the instructions to determine a cost for each subgraph further comprising instructions to:

determine a number of consumer-producer pairs in the subgraph;

determine a weighted cost sum comprising the content-consuming rate of each consumer and the content-production rate of each producer in the subgraph; and

determine the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the weighted cost sum.

19. The system of claim 12, wherein the social graph represents each content consumer and each content producer of the plurality of content consumers and content producers as a vertex of a plurality of vertices of the social graph, the instructions to select a content sharing hub for at least one consumer-producer pair further comprising instructions to:

select a first vertex of the plurality of vertices of the social graph;

select a second vertex of the plurality of vertices of the social graph, the social graph indicating that the first vertex is in a consumer-producer pair with the second vertex;

identify at least one third vertex selected from the plurality of vertices, the social graph indicating that each third vertex is in a consumer-producer pair with the first vertex and is in a consumer-producer pair with the second vertex;

determine a cost of sharing content without using the second vertex as the content sharing hub for the first vertex and the at least one third vertex;

determine a cost of sharing content using the second vertex as the candidate sharing hub for the first vertex and the at least one third vertex; and

select the third vertex as the content sharing hub for the first vertex and the at least one third vertex where the cost of sharing content without the third vertex as the content sharing hub is greater than the cost of sharing content using the third vertex as the content sharing hub.

20. The system of claim 19, the first vertex represents a content consumer and each third vertex represents one content producer of the plurality of content consumers and content producers, the instructions further comprising instructions to:

use a push strategy for each content producer to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by each content producer from the content sharing hub to the content consumer.

21. The system of claim 19, the instructions further comprising instructions to:

determine whether there is at least one other content consumer that is in a consumer-producer pair with at least one content producer represented by a third vertex and is in a consumer-producer pair with the content sharing hub; and

perform the following where it is determined that there is at least one other content consumer;

determine a cost of sharing content without using the second vertex as the content sharing hub between the at least one other content consumer and the at least one content producer;

determine a cost of sharing content using the second vertex as the candidate sharing hub between the at least one other content consumer and the at least one content producer; and

select the third vertex as the content sharing hub for sharing content between the at least one other content consumer and the at least one content producer where the cost of sharing content without the third vertex as the content share hub is more than the cost of sharing content using the third vertex as the content sharing hub.

22. The system of claim 19, the instructions further comprising instructions to:

determine that there is at least one consumer-producer pair of the plurality for which a content sharing hub is not selected, and perform the following for each of the at least one consumer-producer pair;

obtain a content-producing rate at which the content producer produces the one or more items of content;

obtain a content-consuming rate at which the content consumer consumes one or more items of content; and

select between a push strategy and a pull strategy for delivering the one or more items of content from the content producer to the content consumer based on the content-consuming rate of the content consumer and the content-producing rate of the content producer, wherein;

with the push strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is produced by the content producer; and

with the pull strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is consumed by the content consumer.

23. A computer readable non-transitory storage medium for tangibly storing thereon computer readable instructions that when executed cause at least one processor to:

obtain a social graph representing a plurality of social network users as a plurality of content consumers and content producers of the social network, each content producer producing, and each content consumer consuming, one or more items of content, the social graph identifying a content sharing relationship for a consumer-producer pair comprising a content consumer and content producer of the plurality of content consumers and content producers, the content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer;

select, from the plurality of content consumers and content producers, a content sharing hub for at least one consumer-producer pair, the content sharing hub having a content sharing relationship with each of the content consumer and the content producer of the consumer-producer pair; and

define a new content sharing relationship for the consumer-producer pair using the content sharing hub, the new content sharing relationship representing that the content consumer consumes the one or more content items produced by the content producer via the content sharing hub.

24. The medium of claim 23, the new content sharing relationship for the consumer-producer pair comprising a push strategy to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by the content producer from the content sharing hub to the content consumer.

25. The medium of claim 23, the instructions to select a new content sharing relationship for the consumer-producer pair further comprising instructions to:

determine a cost of the content sharing relationship for the consumer-producer pair;

determine a cost of the new content sharing relationship for the consumer-producer pair; and

select the new content sharing relationship over the content sharing relationship where the cost of the content sharing relationship is greater than the cost of the new content sharing relationship.

26. The medium of claim 23, wherein there are a plurality of consumer-producer pairs for the plurality of content consumers and content producers, the instructions to select a new content sharing relationship for the consumer-producer pair further comprising instructions to:

determine a plurality of subgraphs of the social graph, each subgraph having as its content sharing hub one of the plurality of content consumers and content producers and comprising one or more consumer-producer pairs of the plurality of consumer-producer pairs and a consumer and producer for each of the one or more consumer-producer pairs;

determine a cost for each subgraph; and

repeatedly select one of the plurality of subgraphs based on the cost determined for each subgraph until it is determined that each consumer-producer pair of the plurality of consumer-producer pairs is covered by a content sharing hub of a selected subgraph of the plurality of subgraphs, wherein a selected subgraph has the content sharing hub that is used to define the new content sharing relationship.

27. The medium of claim 26, the instructions to repeatedly select one of the plurality of subgraphs based on the cost determined for each subgraph further comprising instructions to:

select a subgraph of the plurality of subgraphs, the selected subgraph having a minimum cost relative to the cost of each other subgraph of the plurality of subgraphs;

remove the selected subgraph from the plurality of subgraphs;

specify a push strategy for each producer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub and a pull strategy for each consumer in the subgraph that is in a consumer-producer pair with the subgraph'"'"'s content sharing hub; and

repeatedly select a subgraph, remove the selected subgraph and specify the push and pull strategies until it is determined that each consumer-producer pair of the plurality is covered.

28. The medium of claim 26, the instructions to determine a cost for each subgraph further comprising instructions to:

determine a number of consumer-producer pairs in the subgraph;

determine a number of consumers and producers in the subgraph; and

determine the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the number of consumers and producers in the subgraph.

29. The medium of claim 26, the instructions to determine a cost for each subgraph further comprising instructions to:

determine a number of consumer-producer pairs in the subgraph;

determine a weighted cost sum comprising the content-consuming rate of each consumer and the content-production rate of each producer in the subgraph; and

determine the cost of the subgraph as the number of consumer-producer pairs in the subgraph divided by the weighted cost sum.

30. The medium of claim 23, wherein the social graph represents each content consumer and each content producer of the plurality of content consumers and content producers as a vertex of a plurality of vertices of the social graph, the instructions to select a content sharing hub for at least one consumer-producer pair further comprising instructions to:

select a first vertex of the plurality of vertices of the social graph;

select a second vertex of the plurality of vertices of the social graph, the social graph indicating that the first vertex is in a consumer-producer pair with the second vertex;

identify at least one third vertex selected from the plurality of vertices, the social graph indicating that each third vertex is in a consumer-producer pair with the first vertex and is in a consumer-producer pair with the second vertex;

determine a cost of sharing content without using the second vertex as the content sharing hub for the first vertex and the at least one third vertex;

determine a cost of sharing content using the second vertex as the candidate sharing hub for the first vertex and the at least one third vertex; and

select the third vertex as the content sharing hub for the first vertex and the at least one third vertex where the cost of sharing content without the third vertex as the content sharing hub is greater than the cost of sharing content using the third vertex as the content sharing hub.

31. The medium of claim 30, the first vertex represents a content consumer and each third vertex represents one content producer of the plurality of content consumers and content producers, the instructions further comprising instructions to:

use a push strategy for each content producer to deliver the one or more content items produced by the content producer to the content sharing hub and a pull strategy to deliver the one or more content items produced by each content producer from the content sharing hub to the content consumer.

32. The medium of claim 30, the instructions further comprising instructions to:

determine whether there is at least one other content consumer that is in a consumer-producer pair with at least one content producer represented by a third vertex and is in a consumer-producer pair with the content sharing hub; and

perform the following where it is determined that there is at least one other content consumer;

determine a cost of sharing content without using the second vertex as the content sharing hub between the at least one other content consumer and the at least one content producer;

determine a cost of sharing content using the second vertex as the candidate sharing hub between the at least one other content consumer and the at least one content producer; and

select the third vertex as the content sharing hub for sharing content between the at least one other content consumer and the at least one content producer where the cost of sharing content without the third vertex as the content share hub is more than the cost of sharing content using the third vertex as the content sharing hub.

33. The medium of claim 30, the instructions further comprising instructions to:

determine that there is at least one consumer-producer pair of the plurality for which a content sharing hub is not selected, and perform the following for each of the at least one consumer-producer pair;

obtain a content-producing rate at which the content producer produces the one or more items of content;

obtain a content-consuming rate at which the content consumer consumes one or more items of content; and

select between a push strategy and a pull strategy for delivering the one or more items of content from the content producer to the content consumer based on the content-consuming rate of the content consumer and the content-producing rate of the content producer, wherein;

with the push strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is produced by the content producer; and

with the pull strategy, each one of the items of content is delivered from the content producer to the content consumer when the item of content is consumed by the content consumer.