System and method for managing an online social network

• US 8,572,221 B2
• Filed: 05/26/2004
• Issued: 10/29/2013
• 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): SMARTH, GERALD A
• Application Number:
  US10/854,054
• Publication Number:
  US 20050267940A1
• Time in Patent Office: 3,443 Days
• Field of Search: 709/8, 709/206, 709/218, 709/204, 709/217, 709/219, 709/227, 709/228, 709/223
• US Class Current: 709/223
• 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 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 M1 and registered user M2; 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 M1 is connected to the registered user M2, returning, to the application server, the shortest path between the registered user M1 and the registered user M2;

else, generating an error indication that the registered user M1 is not connected to the registered user M2.

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.