Filtering suggested structured queries on online social networks

• US 9,594,852 B2
• Filed: 10/28/2015
• Issued: 03/14/2017
• 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:
  US14/925,861
• Publication Number:
  US 20160048527A1
• Time in Patent Office: 503 Days
• Field of Search: 707/769, 707/765, 707/767
• US Class Current: 1/1
• 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 an text query inputted by a first user from a client device of the first user, generating a set of structured queries based on the text query, each structured query in the set corresponding to a grammar of a context-free grammar model, wherein each structured query is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more tokens, wherein one or more of the tokens of each structured query correspond to one or more objects associated with the online social network, respectively, filtering the set to remove one or more structured queries from the set, each removed structured query having a quality score less than a threshold quality score, and sending one or more of the structured queries from the post-filtered set to the client device of the first user for display.

Claims

1. A method comprising, by a computing device:

receiving, from a client device of a first user, a text query inputted by the first user;

generating a set of structured queries based on the text query, each structured query in the set corresponding to a grammar of a context-free grammar model, wherein each structured query is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more tokens, wherein one or more of the tokens of each structured query correspond to one or more objects associated with the online social network, respectively;

filtering the set to remove one or more structured queries from the set, each removed structured query having a quality score less than a threshold quality score; and

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

2. The method of claim 1, further comprising:

receiving, from the client device of the first user, a selection of one of the sent structured queries; and

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

3. The method of claim 1, wherein, for each sent structured query, the grammar used to generate the structured 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 text query.

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

5. The method of claim 4, 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.

6. The method of claim 1, further comprising:

calculating, for each structured query in the set, a quality score based on the text query and the structured 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 each structured query sent to the first user has a quality score greater than or equal to the threshold quality score.

7. The method of claim 6, wherein calculating a quality score comprises, for each structured query:

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

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

calculating a normalized cost based on the ratio of the first number to the second number, wherein the quality score is based on the normalized cost.

8. The method of claim 6, wherein calculating a quality score comprises, for each structured query:

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

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

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

calculating a grammar-insertion cost based on the ratio of the second number to the third number normalized by the first number, wherein the quality score is based on the grammar-insertion cost.

9. The method of claim 6, wherein calculating a quality score comprises, for each structured query:

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

calculating an entity-numerosity cost based on the first number, wherein the quality score is based on the entity-numerosity cost.

10. The method of claim 6, wherein calculating a quality score comprises, for each structured query:

for each query token of the structured query, wherein the query token corresponds to a first term of the text query, determining a probability that the query token pairs with one or more other query tokens of the structured query that correspond to one or more second terms of the text query, wherein the one or more second terms are adjacent to the first term in the text query; and

calculating a language-model score based on the probabilities for each query token, wherein the quality score is based on the language-model score.

11. The method of claim 1, wherein:

the text query comprises one or more n-grams, and wherein each social-graph token corresponds to at least one of the n-grams; and

calculating an entity-insertion cost for each social-graph token based on a first number of terms inserted by the grammar to match the social-graph token with its corresponding n-gram, wherein the quality score is based on the entity-insertion cost.

12. The method of claim 1, wherein if fewer than a threshold number of structured queries remain after filtering the set, then generating a web search query based on the text query.

13. 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 query;

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

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

14. The method of claim 13, further comprising:

determining a first score for each identified grammar; and

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

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

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

determining a second score for each n-gram that the n-gram corresponds to an object, wherein the second score for each n-gram is a probability that the n-gram corresponds to an object; and

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

17. The method of claim 1, wherein the structured queries are sent to a interface associated with a query field for display to the first user.

18. The method of claim 1, wherein the text query is inputted by the first user at a query field of a webpage or a native application associated with the online social network.

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 query inputted by the first user;

generate a set of structured queries based on the text query, each structured query in the set corresponding to a grammar of a context-free grammar model, wherein each structured query is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more tokens, wherein one or more of the tokens of each structured query correspond to one or more objects associated with the online social network, respectively;

filter the set to remove one or more structured queries from the set, each removed structured query having a quality score less than a threshold quality score; and

send, to the client device of the first user for display, one or more of the structured 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 device of a first user, a text query inputted by the first user;

generate a set of structured queries based on the text query, each structured query in the set corresponding to a grammar of a context-free grammar model, wherein each structured query is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more tokens, wherein one or more of the tokens of each structured query correspond to one or more objects associated with the online social network, respectively;

filter the set to remove one or more structured queries from the set, each removed structured query having a quality score less than a threshold quality score; and

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