System and method for managing an online social network
View Patent ↗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.
1. A method comprising:
responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, executing, by one or more computing devices, the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;
for each registered user R of the online network that is connected to the registered user M:
determining, by the one or more computing devices, a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and
when the registered user R is within N degrees of separation from the registered user M, providing, by the one or more computing devices, to the application server, a user ID for the registered user R; and
for each registered user R of the online network that is not connected to the registered user M, providing, by the one or more computing devices, to the application server, an indication that the registered user R is not connected to the registered user M.
2. The method of claim 1 , wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.
3. The method of claim 1 , wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.
4. The method of claim 3 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.
5. The method of claim 3 , further comprising:
regenerating, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.
6. The method of claim 1 , wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.
7. The method of claim 1 , wherein two registered users are friends in the online social network if they are each represented by nodes within the social network map and if the two nodes are connected within one degree of separation.
8. A graph server comprising:
one or more processors; and
a memory coupled to the processors and comprising instructions executable by the processors, the processors being operable when executing the instructions to:
responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, execute the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;
for each registered user R of the online network that is connected to the registered user M:
determine a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and
when the registered user R is within N degrees of separation from the registered user M, provide to the application server, a user ID for the registered user R; and
for each registered user R of the online network that is not connected to the registered user M, provide, to the application server, an indication that the registered user R is not connected to the registered user M.
9. The graph server of claim 8 , wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.
10. The graph server of claim 8 , wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.
11. The graph server of claim 10 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.
12. The graph server of claim 10 , wherein the processors are further operable when executing the instructions to:
regenerate, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.
13. The graph server of claim 8 , wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.
14. The graph server of claim 8 , wherein two registered users are friends in the online social network if they are each represented by nodes within the social network map and if the two nodes are connected within one degree of separation.
15. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, execute the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;
for each registered user R of the online network that is connected to the registered user M:
determine a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and
when the registered user R is within N degrees of separation from the registered user M, provide to the application server, a user ID for the registered user R; and
for each registered user R of the online network that is not connected to the registered user M, provide to the application server, an indication that the registered user R is not connected to the registered user M.
16. The media of claim 15 , wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.
17. The media of claim 15 , wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.
18. The media of claim 17 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.
19. The media of claim 17 , wherein the software is further operable when executed to:
regenerate, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.
20. The media of claim 15 , wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.