Keyword search queries on online social networks

• US 10,635,696 B2
• Filed: 05/31/2017
• Issued: 04/28/2020
• Est. Priority Date: 08/27/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: Boucher, Maxime, Li, Xiao, Perelygin, Alexander, Stoyanov, Veselin S., Lee-Goldman, Russell, Ayan, Necip Fazil
• Primary Examiner(s): Jami, Hares
• Application Number:
  US15/610,287
• Publication Number:
  US 20170270126A1
• Time in Patent Office: 1,063 Days
• Field of Search: 707748, 707759, 707765, 707767, 707771
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

In one embodiment, a method includes receiving, from a client system of a first user, a text query including one or more n-grams, including an ambiguous n-gram. The method includes searching multiple keyword generators to identify one or more keyword suggestions matching the ambiguous n-gram, each keyword generator having a particular type. The method includes calculating, by a particular scoring algorithm for each keyword generator, a keyword score for each identified keyword suggestion. The scoring algorithm includes multiple weighting factors chosen based on the type of the keyword generator. The method includes generating a set of suggested queries including at least a portion of the text query and one or more identified keyword suggestions and filtering suggested queries from the set based on privacy settings associated with the identified keyword suggestions. The method includes sending, to the client system, instructions for presenting one or more of the suggested queries.

Claims

1. A method comprising:

receiving, from a client system of a first user, a text query comprising one or more n-grams, wherein at least one of the n-grams is an ambiguous n-gram;

searching a plurality of keyword generators to identify one or more keyword suggestions matching the ambiguous n-gram, each keyword generator being a source of a particular type of a plurality of types, each keyword suggestion being of a type corresponding to the type of the keyword generator that identified the keyword suggestion;

calculating, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion identified by the respective keyword generator, wherein the scoring algorithm comprises a plurality of weighting factors, the particular weighting factors used for the particular scoring algorithm for each respective keyword generator being based on at least the type of the keyword suggestion generated by the keyword generator;

generating a set of suggested queries, each suggested query comprising at least a portion of the text query and one or more identified keyword suggestions having a keyword score greater than a threshold keyword score;

filtering one or more suggested queries from the set of suggested queries based on privacy settings associated with the identified keyword suggestions; and

sending, to the client system responsive to receiving the text query, instructions for presenting one or more of the suggested queries from the post-filtered set.

2. The method of claim 1, wherein each identified keyword suggestion corresponds to one or more concepts or entities associated with an online social network.

3. The method of claim 1, wherein the suggested queries are presented at the client system in ranked order based at least on the keyword scores of the identified keyword suggestions comprising each suggested query.

4. The method of claim 1, wherein at least one keyword generator comprises a query-log keyword generator.

5. The method of claim 4, wherein the query-log keyword generator identifies one or more query-log keyword suggestions based on search queries previously received from a plurality of client systems.

6. The method of claim 5, wherein the keyword score for each identified query-log keyword suggestion is calculated based at least in part on one or more of:

a number of times each query-log keyword suggestion has been searched;

or

a number of times each query-log keyword suggestion was selected.

7. The method of claim 1, wherein at least one keyword generator comprises a typeahead keyword generator.

8. The method of claim 7, wherein the typeahead keyword generator identifies one or more typeahead keyword suggestions by identifying concepts or entities matching the ambiguous n-gram, wherein a typeahead keyword suggestion is identified corresponding to each identified concept or entity matching the ambiguous n-gram.

9. The method of claim 8, wherein the keyword score for each identified typeahead keyword suggestion is calculated based at least in part on one or more of:

a popularity of the concept or entity with which each typeahead keyword suggestion corresponds;

a number of times the typeahead keyword suggestion has been searched;

or

a number of times a profile page on an online social network associated with the concept or entity with which each typeahead keyword suggestion corresponds has been visited.

10. The method of claim 1, wherein at least one keyword generator comprises a metadata keyword generator.

11. The method of claim 10, wherein the metadata keyword generator identifies one or more keywords by:

identifying social-graph information associated with the first user corresponding to one or more n-grams identified from the text query; and

identifying one or more metadata keyword suggestions based on the identified social-graph information.

12. The method of claim 1, further comprising:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, the nodes comprising;

a first node corresponding to the first user; and

a plurality of second nodes that each correspond to a concept or an entity associated with an online social network; and

wherein each identified keyword suggestion corresponds to one or more second nodes of the plurality of second nodes.

13. The method of claim 12, wherein filtering one or more suggested queries from the set of suggested queries comprises filtering one or more suggested queries from the set of suggested queries based on privacy settings associated with the second nodes corresponding to the identified keyword suggestions of the suggested queries, wherein a privacy setting for each second node is based on at least a degree of separation between the first node and the second node.

14. The method of claim 12, wherein at least one keyword generator comprises a grammar-parser keyword generator.

15. The method of claim 14, wherein the grammar-parser keyword generator identifies one or more grammar-parser keyword suggestions by:

identifying one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to one or more n-grams identified from the text query;

accessing a context-free grammar model comprising a plurality of grammars, each grammar comprising one or more query tokens;

identifying one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the identified second nodes or identified edges; and

generating one or more grammar-parser keyword suggestions, each grammar-parser keyword suggestion corresponding to a query token of an identified grammar.

16. The method of claim 15, wherein the keyword score for each grammar-parser keyword suggestion is calculated based at least in part on one or more of:

a degree of separation between the first node and the identified second nodes corresponding to the query tokens of the identified grammar, wherein each edge between two nodes represents a single degree of separation between them;

edges corresponding to the query tokens of the grammar;

a number of identified edges connected to the identified second nodes corresponding to the query tokens of the grammar;

or

a search history associated with the first user.

17. The method of claim 1, further comprising:

blending the keyword suggestions from the plurality of keyword generators to form a set of blended keyword suggestions.

18. The method of claim 1, further comprising:

determining, for each identified keyword suggestion, whether the identified keyword suggestion results in a null-search; and

removing each keyword suggestion resulting in a null-search from the identified keyword suggestions.

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

receive, from a client system of a first user, a text query comprising one or more n-grams, wherein at least one of the n-grams is an ambiguous n-gram;

search a plurality of keyword generators to identify one or more keyword suggestions matching the ambiguous n-gram, each keyword generator being a source of a particular type of a plurality of types, each keyword suggestion being of a type corresponding to the type of the keyword generator that identified the keyword suggestion;

calculate, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion identified by the respective keyword generator, wherein the scoring algorithm comprises a plurality of weighting factors, the particular weighting factors used for the particular scoring algorithm for each respective keyword generator being based on at least the type of the keyword suggestion generated by the keyword generator;

generate a set of suggested queries, each suggested query comprising at least a portion of the text query and one or more identified keyword suggestions having a keyword score greater than a threshold keyword score;

filter one or more suggested queries from the set of suggested queries based on privacy settings associated with the identified keyword suggestions; and

send, to the client system responsive to receiving the text query, instructions for presenting one or more of the suggested queries from the post-filtered set.

20. 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, from a client system of a first user, a text query comprising one or more n-grams, wherein at least one of the n-grams is an ambiguous n-gram;

search a plurality of keyword generators to identify one or more keyword suggestions matching the ambiguous n-gram, each keyword generator being a source of a particular type of a plurality of types, each keyword suggestion being of a type corresponding to the type of the keyword generator that identified the keyword suggestion;

calculate, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion identified by the respective keyword generator, wherein the scoring algorithm comprises a plurality of weighting factors, the particular weighting factors used for the particular scoring algorithm for each respective keyword generator being based on at least the type of the keyword suggestion generated by the keyword generator;

generate a set of suggested queries, each suggested query comprising at least a portion of the text query and one or more identified keyword suggestions having a keyword score greater than a threshold keyword score;

filter one or more suggested queries from the set of suggested queries based on privacy settings associated with the identified keyword suggestions; and

send, to the client system responsive to receiving the text query, instructions for presenting one or more of the suggested queries from the post-filtered set.