Blending search results on online social networks

• US 9,792,364 B2
• Filed: 08/08/2014
• Issued: 10/17/2017
• Est. Priority Date: 08/08/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Weng, Ching-Chih, Presta, Alessandro, Chen, Chun-Yang, Chen, Po-Lung
• Primary Examiner(s): Pham, Tuan A
• Application Number:
  US14/454,826
• Publication Number:
  US 20160042067A1
• Time in Patent Office: 1,166 Days
• Field of Search: None
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes receiving a search query from a user of an online social network and searching multiple verticals to identify multiple sets of objects in each vertical, respectively, that match the search query, and wherein each vertical stores one or more objects associated with the online social network. The method also includes ranking, for each set of identified objects from a vertical, each identified object in the set of identified objects. The method further includes blending the multiple sets of identified objects from each vertical to form a set of blended search results that includes a threshold number of identified objects, the blending including an iterative process performed at least the threshold number of iterations. Each iteration of the iterative blending process includes determining a blender score for each top-ranked identified object in each set of identified objects.

Claims

1. A method comprising, by one or more computing devices:

receiving a search query from a first user of an online social network;

searching a plurality of verticals to identify a plurality of sets of objects in each vertical, respectively, that match the search query, wherein each vertical stores one or more objects of a particular object-type, and wherein each object is associated with the online social network;

ranking, for each set of identified objects in each respective vertical, each identified object in the set of identified objects;

blending the plurality of sets of identified objects from each vertical to form a set of blended search results comprising a threshold number of identified objects, the blending comprising performing a number of iterations until the set of blended search results comprises at least the threshold number of identified objects, each iteration comprising;

determining a blender score for each top-ranked identified object in each set of identified objects; and

for the top-ranked identified object having a highest blender score;

adding the object to the set of blended search results;

removing the object from its particular set of identified objects; and

promoting a second-ranked identified object from the particular set of identified objects to the top-ranked identified object of the particular set of identified objects; and

sending, responsive to the search query, the set of blended search results to the first user for display.

2. The method of claim 1, wherein the particular object-type is selected from a group consisting of:

a user, a photo, a post, a page, an application, an event, a location, or a user group.

3. The method of claim 1, further comprising:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first node corresponding to the first user of the online social network; and

a plurality of second nodes corresponding to a plurality of objects, respectively, each object being a user or concept associated with the online social network.

4. The method of claim 3, wherein, for each top-ranked identified object, the blender score is based at least in part on a degree of separation between the first node and a second node corresponding to the top-ranked identified object.

5. The method of claim 3, wherein, for each top-ranked identified object, the blender score is based at least in part on a social-graph affinity of the first user with respect to the top-ranked identified object.

6. The method of claim 3, wherein a vertical of the plurality of verticals is a users vertical storing one or more user-profile pages of the online social network, each user-profile page corresponding to a user node of the plurality of nodes.

7. The method of claim 1, further comprising:

receiving a selection of an object of the search results from the first user; and

sending the object to the first user.

8. The method of claim 1, wherein:

the plurality of verticals comprises M verticals, wherein M is a first positive integer;

a set of identified objects of an i-th vertical of the M verticals comprises N_i identified objects, wherein i is an integer from 1 to M; and

the threshold number is less than or equal to Σ

_i=1^MN_i.

9. The method of claim 8, wherein:

for each vertical of the plurality of verticals, N_i equals N, wherein N is a second positive integer; and

the threshold number is less than or equal to M×

N.

10. The method of claim 1, wherein, for each set of identified objects from a vertical, ranking each identified object in the set of identified objects comprises:

calculating for each identified object in the set of identified objects a vertical score based on a scoring algorithm associated with the vertical; and

ranking the identified objects in the set of identified objects based on the calculated vertical scores.

11. The method of claim 10, wherein the top-ranked identified object in the set of identified objects is an object having a highest vertical score.

12. The method of claim 1, wherein the blender score for each top-ranked identified object in each set of identified objects is based on a scoring algorithm associated with the plurality of verticals.

13. The method of claim 1, wherein:

the objects of the set of blended search results are arranged in an order in which they were added to the set of blended search results; and

the blender scores for the objects of the set of blended search results decrease monotonically.

14. The method of claim 1, further comprising normalizing the blender scores for the objects of the set of blended search results.

15. The method of claim 1, further comprising boosting a ranking of one or more identified objects in a set of identified objects prior to blending the plurality of sets of identified objects.

16. The method of claim 1, further comprising boosting a ranking of one or more identified objects in the set of blended search results prior to sending the set of blended search results to the first user.

17. The method of claim 1, wherein identified objects from each set of identified objects have a relative order in the set of blended search results that is the same as their order in their respective set of identified objects.

18. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive a search query from a first user of an online social network;

search a plurality of verticals to identify a plurality of sets of objects in each vertical, respectively, that match the search query, wherein each vertical stores one or more objects of a particular object-type, and wherein each object is associated with the online social network;

rank, for each set of identified objects in each respective vertical, each identified object in the set of identified objects;

blend the plurality of sets of identified objects from each vertical to form a set of blended search results comprising a threshold number of identified objects, the blending comprising performing a number of iterations until the set of blended search results comprises at least the threshold number of identified objects, each iteration comprising;

determining a blender score for each top-ranked identified object in each set of identified objects; and

for the top-ranked identified object having a highest blender score;

adding the object to the set of blended search results;

removing the object from its particular set of identified objects; and

promoting a second-ranked identified object from the particular set of identified objects to the top-ranked identified object of the particular set of identified objects; and

send, responsive to the search query, the set of blended search results to the first user for display.

19. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

receive a search query from a first user of an online social network;

search a plurality of verticals to identify a plurality of sets of objects in each vertical, respectively, that match the search query, wherein each vertical stores one or more objects of a particular object-type, and wherein each object is associated with the online social network;

rank, for each set of identified objects in each respective vertical, each identified object in the set of identified objects;

blend the plurality of sets of identified objects from each vertical to form a set of blended search results comprising a threshold number of identified objects, the blending comprising performing a number of iterations until the set of blended search results comprises at least the threshold number of identified objects, each iteration comprising;

determining a blender score for each top-ranked identified object in each set of identified objects; and

for the top-ranked identified object having a highest blender score;

adding the object to the set of blended search results;

removing the object from its particular set of identified objects; and

promoting a second-ranked identified object from the particular set of identified objects to the top-ranked identified object of the particular set of identified objects; and

send, responsive to the search query, the set of blended search results to the first user for display.