Second-Order Connection Search in a Social Networking System

• US 20110137932A1
• Filed: 06/15/2010
• Published: 06/09/2011
• Est. Priority Date: 12/08/2009
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Wable, Akhil
• Granted Patent: US 8,316,056 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A social networking system receives a query associated with a user and, in response, provides a combined result set comprising objects stored by a social networking system that match the query. The combined result set comprises multiple result sets obtained from different search algorithms. The various objects stored by the social networking system may be of different types representing different concepts, such as user objects, application objects, event objects, location objects, group objects, and hub/page objects, any of which may be included in the result set. The objects of the result set may be further filtered, ordered, and/or grouped based at least in part on known relationships of the user with the objects, such as geographic distances between locations associated with the user and the objects.

In one embodiment, one of the search algorithms identifies second-order connections of the user by referring to a connection index that stores a list of the connections of the users. The search algorithm may also identify a number of mutual connections that the user shares with the second-order connections.

Claims

1. A method of identifying connections of a user of a social networking system, the method comprising:

receiving a textual query from a client device, the query associated with a searching user of a social networking system;

identifying a set of first-order connections of the searching user, wherein the first-order connections comprise one or more other users with whom the searching user is connected in the social networking system;

identifying a first set of second-order connections of the searching user that match the query based on the identified first-order connections, wherein the second-order connections comprise one or more other users with whom a first-order connection is connected in the social networking system;

determining a number of first-order connections in common between the searching user and one or more of the identified second-order connections;

generating a result set based at least in part on the determined number of first-order connections in common, the result set including one or more of the identified second-order connections; and

providing at least a portion of the result set to the client device in response to the query.

2. The method of claim 1, wherein the users of the second-order connections have associated name tokens, and wherein identifying the first set of second-order connections of the searching user that match the query comprises identifying users having a name token for which the query is a prefix.

3. The method of claim 1, further comprising:

receiving a second textual query from the client device, the second query consisting of the first query with the addition of one extra textual character; and

identifying a second set of second-order connections of the user that match the query based on the identified first-order connections;

wherein the second set of second-order connections comprises fewer users than the first set of second-order connections.

4. The method of claim 1, wherein the searching user has an associated connections table in the social networking system, the connections table comprising a list of user identifiers corresponding to other users with whom the searching user is connected in the social networking system, and wherein identifying the set of first-order connections of the searching user comprises examining the list of user identifiers.

5. The method of claim 1, wherein each user of the social networking system has an associated connections table in the social networking system, the connections table for a user comprising a set of name tokens of other users of with whom the user is connected in the social networking system, each name token having an associated user identifier of a user to which the name token corresponds.

6. The method of claim 5, wherein identifying the set of second-order connections of the searching user comprises:

identifying one of the user identifiers of the connections table associated with the searching user;

identifying a connections table for the user with which the user identifier is associated; and

performing a binary search of the name tokens of the identified connections table to identify name tokens having the query as a prefix;

wherein the identified set of second-order connections comprises the user identifiers associated with the identified name tokens.

7. The method of claim 6, wherein determining the number of first-order connections in common comprises:

storing a list of second-order connections of the searching user, the second-order connections in the list having associated count values; and

for a first one of the user identifiers associated with the identified name tokens;

determining whether the first one of the user identifiers is present in the stored list;

responsive to the first one of the user identifiers being present in the stored list, incrementing the count value associated with the first one of the user identifiers; and

responsive to the first one of the user identifiers being absent from the stored list, adding the first one of the user identifiers to the stored list and setting the associated count value to 1.

8. The method of claim 1, wherein generating the result set comprises:

sorting the one or more of the identified second-order connections according to the determined number of first-order connections in common.

9. The method of claim 1, wherein generating the result set comprises:

removing a connection from the identified second-order connections responsive to the determined number of first-order connections in common being below a predetermined threshold.

10. The method of claim 1, wherein the result set additionally comprises one or more of the identified set of first-order connections, and wherein generating the result set comprises ordering the one or more of the identified set of first-order connections in the result set before the one or more of the identified set of second-order connections.

11. The method of claim 1, wherein the result set additionally comprises one or more of an application, a page, a group, and an event.

12. A computer-readable storage medium having executable computer program instructions embodied therein for identifying connections of a user of a social networking system, actions of the computer program instructions comprising:

receiving a query from a client device, the query associated with a searching user of a social networking system;

identifying a set of first-order connections of the searching user, wherein the first-order connections comprise one or more other users with whom the searching user is connected in the social networking system;

identifying a first set of second-order connections of the searching user that match the query based on the identified first-order connections, wherein the second-order connections comprise one or more other users with whom a first-order connection is connected in the social networking system;

generating a result set including one or more of the identified second-order connections; and

providing at least a portion of the result set to the client device in response to the query.

13. The computer-readable storage medium of claim 12, the actions of the computer program instructions further comprising:

determining a number of first-order connections in common between the searching user and one or more of the identified second-order connections; and

ordering the one or more of the identified second-order connections in the result set based at least in part on the determined number of first-order connections in common.

14. The computer-readable storage medium of claim 12, wherein the users of the second-order connections have associated name tokens, and wherein identifying the first set of second-order connections of the searching user that match the query comprises identifying users having a name token for which the query is a prefix.

15. The computer-readable storage medium of claim 12, wherein each user of the social networking system has an associated connections table in the social networking system, the connections table for a user comprising a set of name tokens of other users of with whom the user is connected in the social networking system, each name token having an associated user identifier of a user to which the name token corresponds.

16. The computer-readable storage medium of claim 15, wherein identifying the set of second-order connections of the searching user comprises:

identifying one of the user identifiers of the connections table associated with the searching user;

identifying a connections table for the user with which the user identifier is associated; and

performing a binary search of the name tokens of the identified connections table to identify name tokens having the query as a prefix;

wherein the identified set of second-order connections comprises the user identifiers associated with the identified name tokens.

17. The computer-readable storage medium of claim 12, wherein generating the result set comprises:

sorting the one or more of the identified second-order connections according to the determined number of first-order connections in common.

18. The computer-readable storage medium of claim 12, wherein generating the result set comprises:

removing a connection from the identified second-order connections responsive to the determined number of first-order connections in common being below a predetermined threshold.

19. A computer-implemented method of searching for connections a user of a social networking system, the method comprising:

storing a connections index comprising a set of connection tables, each connection table;

associated with one of the users of the social networking system, and

having a set of associations between a name token of a second user with whom the user is connected in the social networking system and a unique identifier of the second user on the social networking system;

receiving, from a client device, a textual query associated with the user;

identifying matching first-order connections of the user by;

identifying, within a connection table associated with the user, a first set of the unique identifiers;

identifying, as the matching first-order connections, unique identifiers from the first set of the unique identifiers having an associated name token that matches the query;

identifying matching second-order connections of the user by;

identifying, within connection tables associated with the first set of the unique identifiers, a set of name tokens that match the query, and

identifying, as the matching second-degree friends, the unique identifiers associated with the second set of matching name tokens,

identifying an object having a name matching the query, the object being one of a page, an application, a group, and an event; and

providing, to the client device in response to the query, a result set including;

a plurality of the matching first-order connections,

a plurality of the matching second-order connections, and the identified object.

20. The computer-implemented method of claim 19, further comprising:

determining a number of first-order connections in common between the user and one or more of the matching second-order connections; and

ordering the plurality of the matching second-order connections in the result set based at least in part on the determined number of first-order connections in common.