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 system for an online social network, comprising:
one or more processors associated with one or more computing devices;
a first database comprising user information, the user information including user profile data for each of a plurality of registered users of the online social network;
a second database comprising relationship information, the relationship information including a plurality of entries, wherein the entries include user IDs of the registered users to indicate which of the registered users are friends in the online social network;
an application server accessible by remote computers over a computer network, the application server being operable to execute instructions comprising:
maintaining, using the one or more processors, information in the first database and information in the second database;
receiving an information request from a remote computer over the computer network;
determining, using the one or more processors, that the information request involves a processor-intensive task, the task comprising determining all registered users of the online social network who are within N degrees of separation from registered user M; and
issuing a processing request to a graph server to handle the processor-intensive task; and
one or more graph servers having access to a dedicated memory device, the one or more graph servers being configured to handle processor-intensive computational tasks, and the one or more graph servers being operable to execute instructions comprising:
executing, using the one or more processors, the processor-intensive task, without accessing the second database, by using a graph data structure representing a social network map, the social network map being based on the relationship information stored in the second database, and the graph data structure being stored in the dedicated memory device, wherein the processor-intensive task further comprises, for each particular user of the registered users of the online network:
if the particular user is connected to the registered user M, determining whether the particular user is within N degrees of separation from the registered user M, the degree of separation corresponding to the shortest path between the particular user and the registered user M;
else, generating an error indication that the particular user is not connected to the registered user M; and
returning, to the application server, a list of user IDs for all registered users of the online social network who are within N degrees of separation from registered user M.
2. The system according to claim 1 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM in an adjacency list format.
3. The system according to claim 1 , wherein the second server is configured to access the second database at programmed intervals to regenerate the graph data structure from the relationship information stored in the second database and store the regenerated graph data structure in the dedicated memory device.
4. The system according to claim 1 , wherein N is 2.
5. The system according to claim 1 , wherein N is 3.
6. The system of claim 1 ,
wherein the determining all registered users of the online social network who are within N degrees of separation from registered user M comprises determining all registered users of the online social network who are exactly N degrees of separation from registered user M, and
wherein the list of user IDs consists of user IDs for all registered users of the online social network who are exactly N degrees of separation from registered user M.
7. A system for an online social network, comprising:
one or more processors associated with one or more computing devices;
a first database comprising user information, the user information including user profile data for each of a plurality of registered users of the online social network;
a second database comprising relationship information, the relationship information including a plurality of entries, wherein the entries include user IDs of the registered users to indicate which of the registered users are friends in the online social network;
an application server accessible by remote computers over a computer network, the application server being operable to execute instructions comprising:
maintaining, using the one or more processors, information in the first database and information in the second database;
receiving an information request from a remote computer over the computer network;
determining, using the one or more processors, that the information request involves a processor-intensive task, the task comprising determining a total number of registered users of the online social network are exactly N degrees of separation from registered user M; and
issuing a processing request to a graph server to handle the processor-intensive task; and
one or more graph servers having access to a dedicated memory device, the one or more graph servers being configured to handle processor-intensive computational tasks, and the one or more graph servers being operable to execute instructions comprising:
executing, using the one or more processors, the processor-intensive task, without accessing the second database, by using a graph data structure representing a social network map, the social network map being based on the relationship information stored in the second database, and the graph data structure being stored in the dedicated memory device, wherein the processor-intensive task further comprises, for each particular user of the registered users of the online network:
if the particular user is connected to the registered user M, determining whether the particular user is exactly N degrees of separation from the registered user M, the degree of separation corresponding to the shortest path between the particular user and the registered user M;
else, generating an error indication that the particular user is not connected to the registered user M; and
returning, to the application server, the total number of registered users of the online social network who are exactly N degrees of separation from the registered user M.
8. The system according to claim 7 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM in an adjacency list format.
9. The system according to claim 7 , wherein the second server is configured to access the second database at programmed intervals to regenerate the graph data structure from the relationship information stored in the second database and store the regenerated graph data structure in the dedicated memory device.
10. The system according to claim 7 , wherein N is 2.
11. The system according to claim 7 , wherein N is 3.
12. A system for an online social network, comprising:
one or more processors associated with one or more computing devices;
a first database comprising user information, the user information including user profile data for each of a plurality of registered users of the online social network;
a second database comprising relationship information, the relationship information including a plurality of entries, wherein the entries include user IDs of the registered users to indicate which of the registered users are friends in the online social network;
an application server accessible by remote computers over a computer network, the application server being operable to execute instructions comprising:
maintaining, using the one or more processors, information in the first database and information in the second database;
receiving an information request from a remote computer over the computer network;
determining, using the one or more processors, that the information request involves a processor-intensive task, the task comprising determining a shortest path between registered user M 1 and registered user M 2 ; and
issuing a processing request to a graph server to handle the processor-intensive task; and
one or more graph servers having access to a dedicated memory device, the one or more graph servers being configured to handle processor-intensive computational tasks, and the one or more graph servers being operable to execute instructions comprising:
executing, using the one or more processors, the processor-intensive task, without accessing the second database, by using a graph data structure representing a social network map, the social network map being based on the relationship information stored in the second database, and the graph data structure being stored in the dedicated memory device; and
if the registered user M 1 is connected to the registered user M 2 , returning, to the application server, the shortest path between the registered user M 1 and the registered user M 2 ;
else, generating an error indication that the registered user M 1 is not connected to the registered user M 2 .
13. The system according to claim 12 , wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM in an adjacency list format.
14. The system according to claim 12 , wherein the second server is configured to access the second database at programmed intervals to regenerate the graph data structure from the relationship information stored in the second database and store the regenerated graph data structure in the dedicated memory device.