Filtering suggested queries on online social networks

• US 10,108,676 B2
• Filed: 12/14/2016
• Issued: 10/23/2018
• Est. Priority Date: 05/08/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Li, Xiao
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US15/379,278
• Publication Number:
  US 20170097961A1
• Time in Patent Office: 678 Days
• Field of Search: None
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

In one embodiment, a method includes receiving, from a client device of a first user, a text string inputted by the first user, generating a set of suggested queries based on the text string, each suggested query in the set being based on a string generated by a grammar of a grammar model and comprising the text string of the query and one or more tokens inserted by the grammar model, calculating, for each suggested query in the set, a quality score based on an insertion cost of the one or more tokens inserted by the grammar model, filtering the set to remove one or more suggested queries from the set based on the respective quality scores of the suggested queries, and sending, to the client device, one or more of the suggested queries from the post-filtered set for presentation to the first user.

Claims

1. A method comprising, by a computing device:

receiving, from a client device of a first user, a text string comprising one or more characters inputted by the first user;

generating a set of suggested queries based on the text string, each suggested query in the set being based on a string generated by a grammar of a grammar model and comprising the text string of the query and one or more tokens inserted by the grammar model corresponding to one or more terms, respectively;

calculating, for each suggested query in the set, a quality score based on an insertion cost of the one or more tokens of the suggested query inserted by the grammar model;

filtering the set to remove one or more suggested queries from the set based on the respective quality scores of the suggested queries; and

sending, to the client device, one or more of the suggested queries from the post-filtered set for presentation to the first user.

2. The method of claim 1, further comprising:

receiving, from the client device, a selection of one of the sent suggested queries; and

generating one or more search results responsive to the selected suggested query, the one or more search results corresponding to one or more objects associated with the online social network, respectively, each object matching the one or more tokens of the selected suggested query.

3. The method of claim 1, wherein, for each sent suggested query, the grammar used to generate the suggested query comprises one or more tokens corresponding to one or more identified objects associated with the online social network, each of the identified objects corresponding to at least a portion of the one or more characters inputted by the first user.

4. The method of claim 1, wherein one or more of the suggested queries in the set is based on a natural-language string generated by the grammar.

5. The method of claim 1, wherein, for each suggested query, one or more of the tokens inserted by the grammar model corresponds to one or more objects associated with the online social network, respectively.

6. 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; and

a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively.

7. The method of claim 6, wherein one or more of the suggested queries in the set is a structured query comprising one or more tokens corresponding to one or more objects associated with the online social network, respectively.

8. The method of claim 6, wherein the one or more tokens of each structured query comprise one or more grammar tokens or one or more social-graph tokens, and wherein each social-graph token corresponds to a node of the plurality of nodes or an edge of the plurality of edges.

9. The method of claim 1, wherein, for each suggested query:

the text string comprises one or more n-grams, and wherein one or more of the tokens of the suggested query inserted by the grammar model correspond to at least one of the n-grams of the text string; and

calculating the insertion cost of the one or more tokens of the suggested query based on a number of characters inserted by the grammar to match the token with its corresponding n-gram of the text string.

10. The method of claim 1, wherein the quality score is further based on a normalized cost of the suggested query, and wherein calculating the normalized cost comprises, for each suggested query:

determining a first number of n-grams in the text string;

determining a second number of query tokens in the suggested query; and

calculating the normalized cost based on the ratio of the first number to the second number.

11. The method of claim 1, wherein the quality score is further based on a grammar-insertion cost of the suggested query, wherein the one or more tokens of each structured query comprise one or more grammar tokens or one or more social-graph tokens, and wherein calculating the grammar-insertion cost comprises, for each suggested query:

determining a first number of n-grams in the text string;

determining a second number of grammar tokens in the suggested query;

determining a third number of social-graph tokens in the suggested query; and

calculating a grammar-insertion cost based on the ratio of the second number to the third number normalized by the first number.

12. The method of claim 1, wherein the quality score is further based on an entity-numerosity cost of the suggested query, and wherein calculating the entity-numerosity cost comprises, for each suggested query:

determining a first number of tokens corresponding to objects associated with the online social network in the suggested query; and

calculating an entity-numerosity cost based on the first number.

13. The method of claim 1, wherein the quality score is further based on a language-model score of the suggested query, and wherein calculating the language-model score comprises, for each suggested query:

for each query token of the suggested query, wherein the query token corresponds to at least a first portion of the text string, determining a probability that the query token pairs with one or more other query tokens of the suggested query that correspond to one or more second portions of the text string, wherein the one or more second portions are adjacent to the first portion in the text string; and

calculating a language-model score based on the probabilities for each query token.

14. The method of claim 1, further comprising:

identifying one or more objects associated with the online social network, each of the identified object corresponding to at least a portion of the text string;

accessing the grammar model, wherein the grammar model is a context-free grammar model comprising a plurality of grammars, each grammar comprising one or more tokens; and

identifying one or more grammars, each identified grammar having one or more tokens corresponding to at least one of the identified objects.

15. The method of claim 14, further comprising:

determining a grammar score for each identified grammar; and

wherein each suggested query in the set corresponds to an identified grammar having a grammar score greater than a grammar-threshold score, the suggested query being based on a string generated by the identified grammar, each suggested query comprising the tokens of the corresponding identified grammar, wherein one or more of the tokens of the suggested query corresponds to at least one of the identified objects.

16. The method of claim 14, wherein the text string comprises one or more n-grams, and wherein each of the identified objects corresponds to at least one of the n-grams.

17. The method of claim 16, wherein identifying one or more objects comprises:

determining a probability for each n-gram that the n-gram corresponds to an object; and

selecting objects having a probability greater than an threshold probability, each of the identified objects corresponding to at least one of the n-grams.

18. The method of claim 1, wherein the text string is inputted by the first user at a query field of a webpage or a native application associated with the online social network, and wherein the suggested queries are sent to a interface associated with the query field for display to the first user.

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

receive, from a client device of a first user, a text string comprising one or more characters inputted by the first user;

generate a set of suggested queries based on the text string, each suggested query in the set being based on a string generated by a grammar of a grammar model and comprising the text string of the query and one or more tokens inserted by the grammar model corresponding to one or more terms, respectively;

calculate, for each suggested query in the set, a quality score based on an insertion cost of the one or more tokens of the suggested query inserted by the grammar model;

filter the set to remove one or more suggested queries from the set based on the respective quality scores of the suggested queries; and

send, to the client device, one or more of the suggested queries from the post-filtered set for presentation to the first user.

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 device of a first user, a text string comprising one or more characters inputted by the first user;

generate a set of suggested queries based on the text string, each suggested query in the set being based on a string generated by a grammar of a grammar model and comprising the text string of the query and one or more tokens inserted by the grammar model corresponding to one or more terms, respectively;

calculate, for each suggested query in the set, a quality score based on an insertion cost of the one or more tokens of the suggested query inserted by the grammar model;

filter the set to remove one or more suggested queries from the set based on the respective quality scores of the suggested queries; and

send, to the client device, one or more of the suggested queries from the post-filtered set for presentation to the first user.

21. The system of claim 20, further comprising:

receiving, from the client device, a selection of one of the sent suggested queries; and

generating one or more search results responsive to the selected suggested query, the one or more search results corresponding to one or more objects associated with the online social network, respectively, each object matching the one or more tokens of the selected suggested query.

22. The system of claim 20, wherein, for each sent suggested query, the grammar used to generate the suggested query comprises one or more tokens corresponding to one or more identified objects associated with the online social network, each of the identified objects corresponding to at least a portion of the one or more characters inputted by the first user.

23. The system of claim 20, wherein one or more of the suggested queries in the set is based on a natural-language string generated by the grammar.

24. The system of claim 20, wherein, for each suggested query, one or more of the tokens inserted by the grammar model corresponds to one or more objects associated with the online social network, respectively.

25. The system of claim 20, 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; and

a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively.

26. The system of claim 25, wherein one or more of the suggested queries in the set is a structured query comprising one or more tokens corresponding to one or more objects associated with the online social network, respectively.

27. The system of claim 25, wherein the one or more tokens of each structured query comprise one or more grammar tokens or one or more social-graph tokens, and wherein each social-graph token corresponds to a node of the plurality of nodes or an edge of the plurality of edges.

28. The system of claim 20, wherein, for each suggested query:

the text string comprises one or more n-grams, and wherein one or more of the tokens of the suggested query inserted by the grammar model correspond to at least one of the n-grams of the text string; and

calculating the insertion cost of the one or more tokens of the suggested query based on a number of characters inserted by the grammar to match the token with its corresponding n-gram of the text string.

29. The system of claim 20, wherein the quality score is further based on a normalized cost of the suggested query, and wherein calculating the normalized cost comprises, for each suggested query:

determining a first number of n-grams in the text string;

determining a second number of query tokens in the suggested query; and

calculating the normalized cost based on the ratio of the first number to the second number.

30. The system of claim 20, wherein the quality score is further based on a grammar-insertion cost of the suggested query, wherein the one or more tokens of each structured query comprise one or more grammar tokens or one or more social-graph tokens, and wherein calculating the grammar-insertion cost comprises, for each suggested query:

determining a first number of n-grams in the text string;

determining a second number of grammar tokens in the suggested query;

determining a third number of social-graph tokens in the suggested query; and

calculating a grammar-insertion cost based on the ratio of the second number to the third number normalized by the first number.

31. The system of claim 20, wherein the quality score is further based on an entity-numerosity cost of the suggested query, and wherein calculating the entity-numerosity cost comprises, for each suggested query:

determining a first number of tokens corresponding to objects associated with the online social network in the suggested query; and

calculating an entity-numerosity cost based on the first number.

32. The system of claim 20, wherein the quality score is further based on a language-model score of the suggested query, and wherein calculating the language-model score comprises, for each suggested query:

for each query token of the suggested query, wherein the query token corresponds to at least a first portion of the text string, determining a probability that the query token pairs with one or more other query tokens of the suggested query that correspond to one or more second portions of the text string, wherein the one or more second portions are adjacent to the first portion in the text string; and

calculating a language-model score based on the probabilities for each query token.

33. The system of claim 20, further comprising:

identifying one or more objects associated with the online social network, each of the identified object corresponding to at least a portion of the text string;

accessing the grammar model, wherein the grammar model is a context-free grammar model comprising a plurality of grammars, each grammar comprising one or more tokens; and

identifying one or more grammars, each identified grammar having one or more tokens corresponding to at least one of the identified objects.

34. The system of claim 33, further comprising:

determining a grammar score for each identified grammar; and

wherein each suggested query in the set corresponds to an identified grammar having a grammar score greater than a grammar-threshold score, the suggested query being based on a string generated by the identified grammar, each suggested query comprising the tokens of the corresponding identified grammar, wherein one or more of the tokens of the suggested query corresponds to at least one of the identified objects.

35. The system of claim 33, wherein the text string comprises one or more n-grams, and wherein each of the identified objects corresponds to at least one of the n-grams.

36. The system of claim 35, wherein identifying one or more objects comprises:

determining a probability for each n-gram that the n-gram corresponds to an object; and

selecting objects having a probability greater than an threshold probability, each of the identified objects corresponding to at least one of the n-grams.

37. The system of claim 20, wherein the text string is inputted by the first user at a query field of a webpage or a native application associated with the online social network, and wherein the suggested queries are sent to a interface associated with the query field for display to the first user.