Keyword search queries on online social networks

• US 9,703,859 B2
• Filed: 08/27/2014
• Issued: 07/11/2017
• 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: Perelygin, Alexander, Li, Xiao, Stoyanov, Veselin S., Lee-Goldman, Russell, Ayan, Necip Fazil, Boucher, Maxime
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/470,607
• Publication Number:
  US 20160063093A1
• Time in Patent Office: 1,049 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 an unstructured text query. The method includes parsing the text query to identify one or more n-grams. At least one of the n-grams is an ambiguous n-gram. The method includes searching a plurality of keyword generators to identify one or more keyword suggestions matching the ambiguous n-gram. The method further includes calculating a keyword score for each identified keyword suggestions and generating one or more suggested queries including one or more n-grams identified from the text query. The one or more identified keyword suggestions having a keyword score greater than a threshold keyword score. The method includes sending one or more of the suggested queries to the client system of the first user for display.

Claims

1. A method 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 a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receiving from a client system of a first user an unstructured text query;

parsing the text query to identify 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 particular type corresponding to the type of the keyword generator that identified the keyword suggestion, and each identified keyword suggestion corresponding to one or more second nodes of the plurality of second nodes;

calculating, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion generated 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 one or more n-grams identified from 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 second nodes corresponding to the identified keyword suggestions of the filtered suggested queries, wherein the privacy setting for each second node is based on a degree of separation between the first node and the second node; and

sending, responsive to receiving the unstructured text query, one or more of the suggested queries from the post-filtered set to the client system of the first user for display, the suggested queries being displayed in ranked order based on the keyword scores of the identified keyword suggestions comprising each suggested query.

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

3. The method of claim 2, 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.

4. The method of claim 3, 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 suggestions has been searched;

a number of times each query-log keyword suggestions was selected;

or

a popularity of the one or more second nodes with which each query-log keyword suggestion corresponds.

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

6. The method of claim 4, wherein the typeahead keyword generator identifies one or more typeahead keyword suggestions by identifying one or more second nodes matching the ambiguous n-gram, wherein a typeahead keyword suggestion is generated corresponding to each second node matching the ambiguous n-gram.

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

a popularity of the one or more second nodes 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 associated with the one or more second nodes with which each typeahead keyword suggestion corresponds has been visited.

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

9. The method of claim 8, 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.

10. The method of claim 9, wherein the keyword score for each grammar-parser keyword suggestions is calculated based at least in part one or more of:

a degree of separation between the first-user 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.

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

12. The method of claim 11, 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

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

13. The method of claim 1, wherein calculating the keyword score for each identified keyword suggestion comprises:

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

14. 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.

15. The method of claim 1, wherein the suggested queries are sent for display on a user interface of a native application associated with the online social network on the client system of the first user.

16. The method of claim 1, wherein the suggested queries are sent for display on a webpage of the online social network accessed by a browser client on the client system of the first user.

17. The method of claim 1, further comprising:

ranking the identified keyword suggestions based on their keyword scores.

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

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

a first node corresponding to a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receive from a client system of a first user an unstructured text query;

parse the text query to identify 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 particular type corresponding to the type of the keyword generator that identified the keyword suggestion, and each identified keyword suggestion corresponding to one or more second nodes of the plurality of second nodes;

calculate, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion generated 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 one or more n-grams identified from 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 second nodes corresponding to the identified keyword suggestions of the filtered suggested queries, wherein the privacy setting for each second node is based on a degree of separation between the first node and the second node; and

send, responsive to receiving the unstructured text query, one or more of the suggested queries from the post-filtered set to the client system of the first user for display, the suggested queries being displayed in ranked order based on the keyword scores of the identified keyword suggestions comprising each suggested query.

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;

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

a first node corresponding to a first user associated with an online social network; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network;

receive from a client system of a first user an unstructured text query;

parse the text query to identify 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 particular type corresponding to the type of the keyword generator that identified the keyword suggestion, and each identified keyword suggestion corresponding to one or more second nodes of the plurality of second nodes;

calculate, for each keyword generator, by a particular scoring algorithm for the respective keyword generator, a keyword score for each identified keyword suggestion generated 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 one or more n-grams identified from 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 second nodes corresponding to the identified keyword suggestions of the filtered suggested queries, wherein the privacy setting for each second node is based on a degree of separation between the first node and the second node; and

send, responsive to receiving the unstructured text query, one or more of the suggested queries from the post-filtered set to the client system of the first user for display, the suggested queries being displayed in ranked order based on the keyword scores of the identified keyword suggestions comprising each suggested query.