Filtering suggested structured queries on online social networks

• US 9,223,898 B2
• Filed: 05/08/2013
• Issued: 12/29/2015
• 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:
  US13/890,070
• Publication Number:
  US 20140337371A1
• Time in Patent Office: 965 Days
• Field of Search: 707/769, 707/767, 707/765
• 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 accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, receiving from a user an unstructured text query, generating a set of structured queries based on the text query, calculating a quality score based on the text query and the structured query for each structured query in the set, and filtering the set to remove each structured query having a quality score less than a threshold score.

Claims

1. A method comprising, by a computing device:

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 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 device of the first user, an unstructured text query inputted by the first user;

generating a first set of structured queries based on the text query, each structured query in the first set corresponding to a grammar of a context-free grammar model, wherein each structured query in the first set is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more grammar tokens and 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;

calculating, for each structured query in the first set, a quality score based on the text query and the structured query;

filtering the first set to remove each structured query from the first set having a quality score less than a threshold quality score; and

sending, to the client device of the first user, one or more of the structured queries from the post-filtered first set, wherein each structured query sent to the first user has a quality score greater than or equal to the threshold quality score.

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

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

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

determining a first number of social-graph tokens corresponding to nodes 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.

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

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

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

8. The method of claim 1, further comprising:

identifying one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to at least a portion of the unstructured text query;

accessing a context-free grammar model comprising a plurality of grammars, each grammar comprising one or more query tokens, wherein each query token is a grammar 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 second nodes or identified edges.

9. The method of claim 8, further comprising:

determining a first score for each identified grammar; and

wherein each structured query in the first 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 query tokens of the corresponding identified grammar, wherein one or more of the query tokens of the structured query corresponds to at least one of the identified second nodes or identified edges.

10. The method of claim 8, wherein the text query comprises one or more n-grams, and wherein each of the identified edges or identified nodes corresponds to at least one of the n-grams.

11. The method of claim 10, wherein each n-gram comprises one or more characters of text entered by the first user.

12. The method of claim 10, wherein each n-gram comprises a contiguous sequence of n items from the text query.

13. The method of claim 10, wherein identifying one or more edges or second nodes comprises:

determining a second score for each n-gram that the n-gram corresponds to an edge or a second node;

selecting one or more edges having a second score greater than an edge-threshold score, each of the identified edges corresponding to at least one of the n-grams; and

selecting one or more second nodes having a second score greater than a node-threshold score, each of the identified second nodes being connected to at least one of the identified edges, each of the identified second nodes corresponding to at least one of the n-grams.

14. The method of claim 13, wherein the second score for each n-gram is a probability that the n-gram corresponds to an edge or a second node.

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

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

17. The method of claim 1, further comprising:

receiving, from the client device of the first user, a selection of one of the 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 second nodes, respectively, each second node being connected by an edge corresponding to one of the social-graph tokens of the selected structured query to one of a node corresponding to one of the social-graph tokens of the selected structured query.

18. The method of claim 1, wherein, for each structured query sent to the first user, the grammar used to generate the structured query comprises one or more query tokens corresponding to one or more identified nodes or identified edges, each of the identified nodes or identified edges corresponding to at least a portion of the text query.

19. 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, 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 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 device of the first user, an unstructured text query inputted by the first user;

generate a first set of structured queries based on the text query, each structured query in the first set corresponding to a grammar of a context-free grammar model, wherein each structured query in the first set is based on a natural-language string generated by a grammar of the context-free grammar model and comprises one or more grammar tokens and 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;

calculate, for each structured query in the first set, a quality score based on the text query and the structured query;

filter the first set to remove each structured query from the first set having a quality score less than a threshold quality score; and

send, to the client device of the first user, one or more of the structured queries from the post-filtered first set, wherein each structured query sent to the first user has a quality score greater than or equal to the threshold quality score.

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;

access 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 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 device of the first user, an unstructured text query inputted by the first user;

generate a first set of structured queries based on the text query, each structured query in the first set corresponding to a grammar of a context-free grammar model, wherein each structured query in the first set comprises is based on a natural-language string generated by a grammar of the context-free grammar model and one or more grammar tokens and 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;

calculate, for each structured query in the first set, a quality score based on the text query and the structured query;

filter the first set to remove each structured query from the first set having a quality score less than a threshold quality score; and

send, to the client device of the first user, one or more of the structured queries from the post-filtered first set, wherein each structured query sent to the first user has a quality score greater than or equal to the threshold quality score.