Graph Server Querying for Managing Social Network Information Flow

• US 20110099167A1
• Filed: 12/29/2010
• Published: 04/28/2011
• Est. Priority Date: 05/26/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Mirko Predosin, Nicholas Galbreath
• Inventors: Predosin, Mirko, Galbreath, Nicholas
• Granted Patent: US 9,990,430 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• 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 computer-implemented method comprising:

storing, by one or more computing systems, a list of member relationships in a social network, the list comprising an entry for each of the plurality of members of the social network, each entry further comprising a list of all members of the social network with first-degree relationships with the member associated with the entry;

monitoring, by the one or more computing systems, changes in relationship between the members of the social network;

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

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

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

returning, by the one or more computing systems, the query results to the application server.

2. The method of claim 1, the query comprising an integer value and member identifier.

3. The method of claim 2, the response comprising a list of all members of the social network that are exactly the integer value degrees of separation from the member associated with the member identifier.

4. The method of claim 2, the response comprising the number of members of the social network within the integer value degrees of separation 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 response 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 response comprising a list of all members disposed in the shortest path.

8. The method of claim 5, the response 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. A system comprising:

one or more web servers hosting an online social network;

one or more application servers managing information exchange requests that it receives from users of the online social network;

one or more graph servers, the graph servers configured to;

store a list of member relationships in a social network, the list comprising an entry for each of the plurality of members of the social network, each entry further comprising a list of all members of the social network with first-degree relationships with the member associated with the entry;

monitor changes in relationship between the members of the social network;

update the list in response to relationship changes;

receive, from one or more of the application servers, a query;

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

return the query results to the transmitting application server.

10. The system of claim 9, the query comprising an integer value and member identifier.

11. The system of claim 10, the response comprising a list of all members of the social network that are exactly the integer value degrees of separation from the member associated with the member identifier.

12. The system of claim 10, the response comprising the number of members of the social network within the integer value degrees of separation from the member associated with the member identifier.

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

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

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

16. The system of claim 13, the response 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 graph server in communication with one or more web servers hosting an online social network, and with one or more application servers managing information exchange requests that it receives from users of the online social network the graph server configured to:

store a list of member relationships in a social network, the list comprising an entry for each of the plurality of members of the social network, each entry further comprising a list of all members of the social network with first-degree relationships with the member associated with the entry;

monitor changes in relationship between the members of the social network;

update the list in response to relationship changes;

receive, from one or more of the application servers, a query;

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

return the query results to the transmitting application server.

18. The graph server of claim 17, the query comprising an integer value and member identifier.

19. The graph server of claim 18 the response comprising a list of all members of the social network that are exactly the integer value degrees of separation from the member associated with the member identifier.

20. The graph server of claim 18, the response comprising the number of members of the social network within the integer value degrees of separation from the member associated with the member identifier.

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

22. The graph server of claim 21, the response comprising the shortest path between the member associated with the first member identifier and the member associated with the second member identifier.

23. The graph server of claim 22, the response comprising a list of all members disposed in the shortest path.

24. The graph server of claim 21, the response 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.