# US 8,572,221 B2 · System and method for managing an online social network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,572,221 B2 - Document ID: US8572221B2 - Status: Granted - Kind: B2 - Application number: 10/854,054 - Filed: 2004-05-26 - Published: 2005-12-01 - Granted: 2013-10-29 - Earliest claimed: 2004-05-26 - Assignees: Facebook, Inc. - Applicants: Nicholas Galbreath; Mirko Predosin - Inventors: Nicholas Galbreath; Mirko Predosin - Web page: https://patentgrep.com/patent/US8572221B2 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/9535: Search customisation based on user profiles and personalisation - G06Q 30/02: Marketing; Price estimation or determination; Fundraising - 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) - H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) - H04L 67/306: User profiles - G06F 21/629: {to features or functions of an application} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The system according to claim 1, wherein N is 2. ### Claim 5 (depends on 1) The system according to claim 1, wherein N is 3. ### Claim 6 (depends on 1) 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. ### Claim 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 7) 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. ### Claim 10 (depends on 7) The system according to claim 7, wherein N is 2. ### Claim 11 (depends on 7) The system according to claim 7, wherein N is 3. ### Claim 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. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 12) 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.