Methods and apparatus for determining social relevance in near constant time

• US 7,856,449 B1
• Filed: 05/06/2005
• Issued: 12/21/2010
• Est. Priority Date: 05/12/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vale, Chris, Wehner, Kristopher C., Martino, Paul J.
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): OBERLY, VAN HONG
• Application Number:
  US11/123,853
• Time in Patent Office: 2,055 Days
• Field of Search: 707/802, 707/781, 707/784, 707/999.009, 707/999.102
• US Class Current: 707/784
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 50/01 Social networking
• 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

A computer system includes a database configured to store a plurality of social network relationships, a graphing system coupled to a database, wherein the graphing system includes a processor and random access memory, wherein the random access memory is configured to store at least a portion of the plurality of social network relationships from the database, wherein the processor is configured to determine a social map for a user in response to at least the portion of the plurality of social network relationships in the random access memory, and wherein the random access memory is configured to store the social map for the user, and a server coupled to the database and the graphing system, wherein the server is configured to receive an indication of the user, and wherein the server is configured to provide the indication of the user to the graphing system.

Claims

1. A computer system comprises:

a database server configured to store a plurality of social network relationships;

a graphing system separate from and coupled to the database server, wherein the graphing system includes a processor and random access memory, wherein the random access memory is configured to store at least a portion of the plurality of social network relationships from the database server, wherein the processor is configured to compute a social map for a user in response to at least the portion of the plurality of social network relationships in the random access memory, and wherein the random access memory is configured to store the social map for the user, the social map including a plurality of different social distances between a plurality of users in a computer network, wherein a first profile is provided for a first user and includes a first social distance between the first user and a second user, and wherein a second profile is provided for the first user and includes a second social distance between the first user and the second user, the first social distance and the second social distance being different, wherein the first social distance is reduced between the first and second users as a result of a weighting factor that is determined by a frequency of communications between the first and second users, a responsiveness by the first user in answering communications from the second user, and by a manual adjustment made directly to the weighting factor by the first user; and

a server separate from and coupled to the database server and to the graphing system, wherein the server is configured to receive an indication of the user and to provide the indication of the user to the graphing system, and wherein the server is configured to receive a request for the social map for the user, from the user, and to provide the social map stored in the random access memory of the graphing system to the user, wherein the social map is computed during log-in time for the user and a cached copy of the social map is stored in a cache, and wherein, while the user is logged into a session, an evaluation of the cached copy of the social map is performed in order to identify dirty bits, which are indicative of the cached copy of the social map being stale and requiring an update to be performed during the session, the server being configured to;

send the cached copy of the social map, in response to the user initiating a query for data drawn from the social network;

compute a revised social map for the first user in the graphing system, in response to the indication of the user and in response to a request to modify the social map, the revised social map being stored for the first user in the random access memory of the graphing system.

2. A computer system comprises:

a database server configured to store a plurality of social network relationships;

a graphing system separate from and coupled to the database server, wherein the graphing system includes a processor and random access memory, wherein the random access memory is configured to store at least a portion of the plurality of social network relationships from the database server, wherein the processor is configured to compute a social map for a user in response to at least the portion of the plurality of social network relationships in the random access memory, and wherein the random access memory is configured to store the social map for the user, the social map including a plurality of different social distances between a plurality of users in a computer network; and

a server separate from and coupled to the database server and to the graphing system, wherein the server is configured to receive an indication of the user and to provide the indication of the user to the graphing system, wherein a first profile is provided for a first user and includes a first social distance between the first user and a second user, and wherein a second profile is provided for the first user and includes a second social distance between the first user and the second user, the first social distance and the second social distance being different, wherein the first social distance is reduced between the first and second users as a result of a weighting factor that is determined by a frequency of communications between the first and second users, a responsiveness by the first user in answering communications from the second user, and by a manual adjustment made directly to the weighting factor by the first user;

wherein the server is configured to receive a social relationship-based query from the user;

wherein the server is also configured to process the social relationship-based query from the user using at least a portion of the social map for the user stored in the random access memory of the graphing system, wherein the social map is computed during log-in time for the user and a cached copy of the social map is stored in a cache, and wherein, while the user is logged into a session, an evaluation of the cached copy of the social map is performed in order to identify dirty bits, which are indicative of the cached copy of the social map being stale and requiring an update to be performed during the session, the server being configured to;

send the cached copy of the social map, in response to the user initiating a query for data drawn from the social network;

compute a revised social map for the first user in the graphing system, in response to the indication of the user and in response to a request to modify the social map, the revised social map being stored for the first user in the random access memory of the graphing system.

3. The computer system of claim 2 wherein the graphing system is also configured to determine additional social metrics selected from a group consisting of:

a social distance between the user and a first user, a shortest path between the user and a first user, all shortest paths between the user and the first user, a path between the user and a first user via a second user, what users are less than N degrees from the user, a revised social map for the user in response to an added relationship by the user, a revised social map for the user in response to a deleted relationship by the user.

4. The computer system of claim 2 wherein the social relationship-based query is selected from a group consisting of:

what affinity groups the user may be interested in joining, what classified listings the user may be interested in viewing, which users the user may be interested in communicating with, which businesses the user may be interested in, which users have a good reputation.

5. The computer system of claim 2

wherein the plurality of social network relationships are between a plurality of users;

wherein the plurality of users comprises over 10 million users; and

wherein the graphing system is configured to process the social relationship-based query in less than approximately 20 milliseconds.

6. The computer system of claim 5 wherein the plurality of users comprises over 15 million users.

7. A method for a computer system including a database system, a graphing system, and a server system comprises:

storing a plurality of social network relationships for a plurality of users including a first user, in the database system;

copying at least a portion of the plurality of social network relationships from the database system to the graphing system, the graphing system being separate from and coupled to the database system, wherein the portion of the plurality of social network relationships are stored in random access memory of the graphing system;

receiving an indication of the first user in the server system, the server system being separate from and coupled to the database system and to the graphing system;

sending the indication of the first user from the server system to the graphing system;

computing a social map for the first user in the graphing system, in response to the indication of the first user and in response to at least the portion of the plurality of social network relationships stored in the random access memory, the social map including a plurality of different social distances between a plurality of users in a computer network, wherein a first profile is provided for the first user and includes a first social distance between the first user and a second user, and wherein a second profile is provided for the first user and includes a second social distance between the first user and the second user, the first social distance and the second social distance being different, wherein the first social distance is reduced between the first and second users as a result of a weighting factor that is determined by a frequency of communications between the first and second users, a responsiveness by the first user in answering communications from the second user, and by a manual adjustment made directly to the weighting factor by the first user;

storing the social map for the first user in the random access memory of the graphing system receiving a request to modify the social map from the first user, wherein the social map is computed during log-in time for the user and a cached copy of the social map is stored in a cache, and wherein, while the user is logged into a session, an evaluation of the cached copy of the social map is performed in order to identify dirty bits, which are indicative of the cached copy of the social map being stale and requiring an update to be performed during the session;

sending the cached copy of the social map, in response to the user initiating a query for data drawn from the social network; and

computing a revised social map for the first user in the graphing system, in response to the indication of the user and in response to a request to modify the social map, the revised social map being stored for the first user in the random access memory of the graphing system.

8. The method of claim 7 further comprising:

receiving a request for at least a portion of the social map of the first user in the graphing system; and

providing at least the portion of the social map stored in the random access memory of the graphing system to the first user.

9. The method of claim 7 further comprising:

determining an additional social metric of the first user in the graphing system, in response to the indication of the user and in response to at least the portion of the plurality of social network relationships stored in the random access memory, wherein the additional social metric is selected from a group consisting of;

a social distance between the user and a first user, a shortest path between the user and a first user, all shortest paths between the user and the first user, a path between the user and a first user via a second user, what users are less than N degrees from the user, a revised social map for the user in response to an added relationship by the user, a revised social map for the user in response to a deleted relationship by the user.

10. The method of claim 9 further comprising:

receiving a social relationship-based query;

processing the social relationship-based query in response to at least the portion of the plurality of social network relationships stored in the random access memory of the graphing system to determine a social relationship-based query response, wherein the social relationship-based query is selected from a group consisting of;

what affinity groups the first user may be interested in joining, what classified listings the first user may be interested in viewing, which users the first user may be interested in communicating with, which businesses the first user may be interested in, which users have a good reputation, what products the first user may be interested in learning about.

11. The method of claim 9

wherein the plurality of users comprises over 10 million users;

and

wherein computing the social map for the first user in the graphing system, in response to the indication of the user and in response to at least the portion of the plurality of social network relationships stored in the random access memory is completed in less than approximately 20 milliseconds.

12. The method of claim 7 further comprising

receiving a social relationship-based query in the database system;

processing the social relationship-based query in the database system in response to at least a portion of the social map for the first user stored in the random access memory of the graphing system to generate a social relationship-based query response.

13. The method of claim 7, wherein the request to modify the social map from the first user is selected from a group consisting of:

a request to add a link from the first user to a second user, a request to delete a link from the first user to the second user, a request to confirm a link from the first user to the second user.