Search and retrieval of objects in a social networking system

• US 8,239,364 B2
• Filed: 06/15/2010
• Issued: 08/07/2012
• 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, DeLorme, Luke Andrew, Kao, Wayne, Roche, Alexandre, Occhino, Thomas
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US12/816,377
• Publication Number:
  US 20110137902A1
• Time in Patent Office: 784 Days
• Field of Search: 707600-831
• US Class Current: 707/706
• 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 computer-implemented method comprising:

accessing a social graph having nodes corresponding to objects, and having edges corresponding to relationships of the objects;

receiving a query from a client device, the query provided by a user of a social networking system;

performing a plurality of search algorithms using the query, wherein one or more of the search algorithms obtains results based at least in part on examining connections of the user in the social networking system;

obtaining a result set from each of the search algorithms, wherein each result set comprises a set of objects from an object store of the social networking system that match the query;

aggregating the result sets from the search algorithms into a combined result set;

ordering at least a plurality of the objects of the combined result set based at least in part on measures of affinities of the user for the objects, an affinity of the user for an object comprising at least one from a group consisting of;

a distance on the social graph between the user and the object, and a similarity between the user and the object; and

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

2. The computer-implemented method of claim 1, wherein the combined result set comprises a first object having a first type and a second object having a second type different from the first type.

3. The computer-implemented method of claim 1, wherein the combined result set comprises a user object.

4. The computer-implemented method of claim 1, wherein the combined result set comprises a page object.

5. The computer-implemented method of claim 1, wherein the combined result set comprises at least one of an application object, a group object, a media object, an event object, and a location object.

6. The computer-implemented method of claim 1, wherein a measure of an affinity of the user for an object further comprises a physical distance between a geographic location associated with the user and a geographic location associated with the object.

7. The computer-implemented method of claim 1, wherein the objects of the result set are grouped within the result set based at least in part on a search algorithm that produced them, the search algorithms including one or more of a second-order connections search, a history search, and a global importance search.

8. The computer-implemented method of claim 1, wherein one or more of the objects in the object store have associated name tokens, and wherein an object matches the query if the query is a prefix of at least one of the associated name tokens of the object.

9. A computer-implemented method comprising:

receiving a query from a user;

submitting the query to a remote social networking system; and

receiving, from the social networking system, a combined result set comprising objects matching the query, the combined result set comprising objects obtained from a plurality of search algorithms performed by the social networking system;

wherein at least a plurality of the objects of the combined result set are ordered based at least in part on measures of affinities of the user for the objects, an affinity of the user for an object comprising at least one from a group consisting of;

a distance on a social graph between the user and the object, and a similarity between the user and the object.

10. The computer-implemented method of claim 9, further comprising using an application programming interface (API) of the remote social networking system to log the user in to the social networking system before submitting the query.

11. The computer-implemented method of claim 9, wherein a measure of an affinity of the user for an object comprises a physical distance between a geographic location associated with the user on the social networking system and a geographic location associated with the object on the social networking system.

12. The computer-implemented method of claim 9, wherein the social graph has nodes corresponding to objects and edges corresponding to relationships of the objects, the user being represented as one of the objects.

13. The computer-implemented method of claim 9, wherein the combined result set comprises a first object having a first type and a second object having a second type different from the first type.

14. A computer-readable storage medium having executable computer program instructions embodied therein, the instructions for:

accessing a social graph having nodes corresponding to objects, and having edges corresponding to relationships of the objects;

receiving a query from a client device, the query provided by a user of a social networking system;

performing a plurality of search algorithms using the query, wherein one or more of the search algorithms obtains results based at least in part on examining connections of the user in the social networking system;

obtaining a result set from each of the search algorithms, wherein each result set comprises a set of objects from an object store of the social networking system that match the query;

aggregating the result sets from the search algorithms into a combined result set;

ordering at least a plurality of the objects of the combined result set based at least in part on measures of affinities of the user for the objects, an affinity of the user for an object comprising at least one of a group consisting of;

a distance on the social graph between the user and the object, and a similarity between the user and the object; and

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

15. The computer-readable storage medium of claim 14, wherein the combined result set comprises a first object having a first type and a second object having a second type different from the first type.

16. The computer-readable storage medium of claim 14, wherein a measure of an affinity of the user for an object further comprises a physical distance between a geographic location associated with the user and a geographic location associated with the object.

17. The computer-readable storage medium of claim 14, wherein the objects of the combined result set are grouped within the combined result set based at least in part on a search algorithm that produced them, the search algorithms including one or more of a second-order connections search, a history search, and a global importance search.

18. The computer-readable storage medium of claim 14, wherein one or more of the objects in the object store have associated name tokens, and wherein an object matches the query if the query is a prefix of at least one of the associated name tokens of the object.

19. The computer-readable storage medium of claim 14, wherein the combined result set comprises a first object having a first type and a second object having a second type different from the first type.

20. The computer-readable storage medium of claim 14, wherein the combined result set comprises at least one of a user object and a page object.