Graph server querying for managing social network information flow

• US 9,990,430 B2
• Filed: 12/29/2010
• Issued: 06/05/2018
• Est. Priority Date: 05/26/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Galbreath, Nicholas, Predosin, Mirko
• Primary Examiner(s): KUDDUS, DANIEL A
• Application Number:
  US12/981,311
• Publication Number:
  US 20110099167A1
• Time in Patent Office: 2,715 Days
• Field of Search: 707732, 707736, 707798
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 21/629 to features or functions of an application
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/306 User profiles

Abstract

An online social network is managed using one server for database management tasks and another server, preferably in a distributed configuration, for CPU-intensive computational tasks, such as finding a shortest path between two members or a degree of separation between two members. The additional server has a memory device containing relationship information between members of the online social network and carries out the CPU-intensive computational tasks using this memory device. With this configuration, the number of database lookups is decreased and processing speed is thereby increased.

Claims

1. A method comprising:

by one or more computing devices, storing a list of member relationships in a social-networking system, the social-networking system comprising a graph comprising a plurality of nodes and edges connecting the nodes, wherein at least some of the nodes correspond to the members of the social-networking system;

by one or more computing devices, monitoring changes in relationship between the members of the social-networking system;

by one or more computing devices, updating the list in response to relationship changes;

by one or more computing devices, receiving from an application server a query;

by one or more computing devices, processing the query using the stored list of member relationships; and

by one or more computing devices, returning the query results to the application server, wherein the query results comprise degrees-of-separation information with respect to one or more members of the social-networking system.

2. The method of claim 1, the query comprising a degrees-of-separation value and member identifier.

3. The method of claim 2, the results comprising a list of all members of the social-networking system that are exactly the degrees-of-separation value from the member associated with the member identifier.

4. The method of claim 2, the results comprising the number of members of the social-networking system within the degrees-of-separation value from the member associated with the member identifier.

5. The method of claim 1, the query comprising a first member identifier and a second member identifier.

6. The method of claim 5, the results comprising the shortest path between the member associated with the first member identifier and the member associated with the second member identifier.

7. The method of claim 6, the results comprising a list of all members disposed in the shortest path.

8. The method of claim 5, the results comprising the number of degrees of separation corresponding to the shortest path between the member associated with the first identifier and the member associated with the second identifier.

9. One or more computer-readable non-transitory storage media embodying software that is configured to, when executed:

store a list of member relationships in a social-networking system, the social-networking system comprising a graph comprising a plurality of nodes and edges connecting the nodes, wherein at least some of the nodes correspond to the members of the social-networking system;

monitor changes in relationship between the members of the social-networking system;

update the list in response to relationship changes;

receive, from an application server, a query;

process the query using the stored list of member relationships; and

return the query results to the application server, wherein the query results comprise degrees-of-separation information with respect to one or more members of the social-networking system.

10. The media of claim 9, the query comprising a degrees-of-separation value and member identifier.

11. The media of claim 10, the results comprising a list of all members of the social-networking system that are exactly the degrees-of-separation value from the member associated with the member identifier.

12. The media of claim 10, the results comprising the number of members of the social-networking system within the degrees-of-separation value from the member associated with the member identifier.

13. The media of claim 9, the query comprising a first member identifier and a second member identifier.

14. The media of claim 13, the results comprising the shortest path between the member associated with the first member identifier and the member associated with the second member identifier.

15. The media of claim 14, the results comprising a list of all members disposed in the shortest path.

16. The media of claim 13, the results comprising the number of degrees of separation corresponding to the shortest path between the member associated with the first identifier and the member associated with the second identifier.

17. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors being configured to, when executed;

store a list of member relationships in a social-networking system, the social-networking system comprising a graph comprising a plurality of nodes and edges connecting the nodes, wherein at least some of the nodes correspond to the members of the social-networking system;

monitor changes in relationship between the members of the social-networking system;

update the list in response to relationship changes;

receive, from an application server, a query;

process the query using the stored list of member relationships; and

return the query results to the application server, wherein the query results comprise degrees-of-separation information with respect to one or more members of the social-networking system.

18. The system of claim 17, the query comprising value and member identifier.

19. The system of claim 18, the results comprising a list of all members of the social-networking system that are exactly the degrees of separation value from the member associated with the member identifier.

20. The system of claim 18, the results comprising the number of members of the social-networking system within the degrees of separation value from the member associated with the member identifier.

21. The system of claim 17, the query comprising a first member identifier and a second member identifier.

22. The system of claim 21, the results comprising the shortest path between the member associated with the first member identifier and the member associated with the second member identifier.

23. The system of claim 22, the results comprising a list of all members disposed in the shortest path.

24. The system of claim 21, the results comprising the number of degrees of separation corresponding to the shortest path between the member associated with the first identifier and the member associated with the second identifier.