Ranking search results using diversity groups

Patent metadata

Field	Value
Publication number	US-10032234-B2
Application number	US-201313752616-A
Country	US
Kind code	B2
Filing date	Jan 29, 2013
Priority date	Jan 29, 2013
Publication date	Jul 24, 2018
Grant date	Jul 24, 2018

Abstract

In one embodiment, a method includes receiving a plurality of search results based on a search query from a user. A computing system determines a plurality of scores for each search result, each score generated by applying a distinct scoring function of a plurality of scoring functions to the search result. The computing system generates a plurality of diversity groups, each diversity group corresponding to a scoring function of the plurality of scoring functions, each diversity group including at least a subset of the plurality of search results ordered according to the scores generated by applying the scoring function to the at least the subset of the plurality of search results. The method further includes selecting at least one of the plurality of search results from each diversity group and sending the selected search results to the user.

First claim

What is claimed is:

1. A method comprising, by one or more computing systems:
accessing, by one or more of the computing systems, 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;
identifying, by one or more of the computing systems, a plurality of search results from a plurality of indices based on a search query received from a client device of the first user, each search result corresponding to a node of the social graph, wherein each search result is associated with a plurality of attributes;
determining, by one or more of the computing systems, for each search result of the plurality of search results, a set of scores for the search result, wherein the set of scores for each search result is determined by:
selecting a set of scoring functions from a plurality of distinct scoring functions based on attributes of the search query and attributes of the search results; and
generating the set of scores for the search result from the selected set of scoring functions, respectively, wherein each scoring function applies different weightings to the attributes of the search result and calculates a score for the search result based on the weighted attributes of the search result, wherein the weighting is determined based on a type associated with the scoring function;

generating, by one or more of the computing systems, a plurality of diversity groups corresponding to the plurality of scoring functions, respectively, each diversity group comprising search results corresponding to nodes indexed by a particular index, wherein the search results of each diversity group are ordered according to the scores generated by applying the respective scoring function to the search results;
selecting, by one or more of the computing systems, a set of search results, wherein the selected set of search results comprises one or more search results from each diversity group; and
sending, from one or more of the computing systems, to the client device of the first user for display, a search-results page comprising the selected set of search results.

2. The method of claim 1 , wherein each diversity group comprises a max heap of search results and selecting a search result from a diversity group comprises selecting the root node of the max heap.

3. The method of claim 1 , wherein each of the one or more search results from each diversity group is selected based on its score within the diversity group.

4. The method of claim 1 , further comprising:
determining that a first search result selected from a first diversity group of the plurality of diversity groups is identical to a second search result selected from a second diversity group of the plurality of diversity groups; and
selecting a third search result from the second diversity group to be sent to the user in the place of the second search result.

5. The method of claim 1 , wherein the one or more search results from each diversity group are selected according to a selection function that specifies the minimum number of search results to select from at least one of the plurality of diversity groups.

6. The method of claim 1 , wherein the one or more search results from each diversity group are selected according to a selection function that specifies the maximum number of search results to select from at least one of the plurality of diversity groups.

7. The method of claim 1 , wherein the one or more search results from each diversity group are selected according to a selection function that specifies:
a total number of search results to select;
the number of search results to select from each of the diversity groups except a first diversity group; and
that if the total number of search results is not reached after search results have been selected from the diversity groups other than the first diversity group, then additional search results are to be selected from the first diversity group.

8. The method of claim 1 , wherein each of one or more of the plurality of scoring functions corresponds to a particular index indexing nodes of a particular node type, wherein the node types comprise user nodes and concept nodes.

9. The method of claim 1 , wherein the nodes comprise user nodes and concept nodes, wherein the user nodes correspond to users and the concept nodes correspond to one or more of places, entities, documents, websites, media files, or applications.

10. The method of claim 1 , wherein the attributes of the search query and the attributes of the search results are categories associated with the search query and the search results.

11. A system comprising: one or more processors; and a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
access, by one or more of the computing systems, 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;
identify, by one or more of the computing systems, a plurality of search results from a plurality of indices based on a search query received from a client device of the first user, each search result corresponding to a node of the social graph, wherein each search result is associated with a plurality of attributes;
determine, by one or more of the computing systems, for each search result of the plurality of search results, a set of scores for the search result, wherein the set of scores for each search result is determined by:
selecting a set of scoring functions from a plurality of distinct scoring functions based on attributes of the search query and attributes of the search results; and
generating the set of scores for the search result from the selected set of scoring functions, respectively, wherein each scoring function applies different weightings to the attributes of the search result and calculates a score for the search result based on the weighted attributes of the search result, wherein the weighting is determined based on a type associated with the scoring function;

generate, by one or more of the computing systems, a plurality of diversity groups corresponding to the plurality of scoring functions, respectively, each diversity group comprising search results corresponding to nodes indexed by a particular index, wherein the search results of each diversity group are ordered according to the scores generated by applying the respective scoring function to the search results;
select, by one or more of the computing systems, a set of search results, wherein the selected set of search results comprises one or more search results from each diversity group; and
send, from one or more of the computing systems, to the client device of the first user for display, a search-results page comprising the selected set of search results.

12. The system of claim 11 , wherein each diversity group comprises a max heap of search results and selecting a search result from a diversity group comprises selecting the root node of the max heap.

13. The system of claim 11 , wherein each of the one or more search results from each diversity group based on its score within the diversity group.

14. The system of claim 11 , the processor further operable to:
determine that a first search result selected from a first diversity group of the plurality of diversity groups is identical to a second search result selected from a second diversity group of the plurality of diversity

Assignees

• Facebook Inc

Inventors

• Sankar Sriram
• Kunnatur Sandhya
• Dhamdhere Kedar

Classifications

• G06Q10/40 Primary

  Business processes related to social networking or social networking services · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06Q30/02 Primary

  Marketing; Price estimation or determination; Fundraising · CPC title

• G06F17/30867

  Physics · mapped topic