Natural-language rendering of structured search queries

• US 9,367,607 B2
• Filed: 12/31/2012
• Issued: 06/14/2016
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Vee, Erik N., Chatot, Olivier
• Primary Examiner(s): LIAO, JASON G
• Application Number:
  US13/731,866
• Publication Number:
  US 20140188935A1
• Time in Patent Office: 1,261 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes accessing a social graph that includes a plurality of nodes and edges, receiving an unstructured text query, identifying nodes and edges that correspond to portions of the text query, accessing a context-free grammar model, identifying query tokens from the grammar model that correspond to the identified nodes and edges, selecting grammars having query tokens that corresponding to each of the identified nodes and edges, and generating structured queries based on the selected grammars, where the structure queries are based on strings generated by the grammars.

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

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

accessing a context-free grammar model comprising a grammar forest with a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, wherein the grammar forest is organized as an ordered tree comprising a plurality of non-terminal tokens and a plurality of query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token;

identifying, based on the identified edges and identified second nodes of the social graph, one or more query tokens in one or more grammars of the grammar forest, each identified query token corresponding to at least one of the identified second nodes or identified edges of the social graph;

selecting one or more grammars of the grammar forest, each selected grammar comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph;

generating one or more structured queries, each structured query corresponding to a selected grammar, wherein each structured query is based on a natural-language string generated by the corresponding selected grammar, each structured query comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph; and

sending, to the client system of the first user, one or more of the structured queries as suggested queries for display to the first user in response to the unstructured text query inputted by the first user.

2. The method of claim 1, wherein selecting one or more grammars comprises:

traversing, for each identified query token, the grammar forest to identify one or more non-terminal tokens that intersect with the traverse of one or more other identified query tokens; and

selecting one or more of the grammars in the semantic tree adjoining the identified non-terminal tokens.

3. The method of claim 1, wherein selecting one or more grammars comprises:

generating a semantic tree corresponding to the unstructured text query, the semantic tree comprising an intersect token and one or more query tokens, each query token connecting to the intersect by zero or more non-terminal tokens;

analyzing the grammar forest to identify one or more sets of non-terminal tokens and query tokens that substantially match the semantic tree, each set having a non-terminal token corresponding to the intersect token; and

selecting one or more of the grammars in the grammar forest adjoining the non-terminal tokens corresponding to the intersect token.

4. The method of claim 1, further comprising generating a query command based on the unstructured text query.

5. The method of claim 1, wherein generating one or more structured queries comprises:

generating, for each selected grammar, a natural-language string based on the selected grammar, wherein the natural-language string comprises the one or more identified query tokens; and

rendering, for each natural-language string, a structured query based on the natural-language string, wherein the structured query comprises references to each identified second node or identified edge corresponding to identified query tokens.

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

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

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

9. The method of claim 6, wherein identifying one or more edges and second nodes comprises:

determining a score for each n-gram that indicates that the n-gram corresponds to an edge or a second node, wherein at least one score is determined corresponding to at least one edge and wherein at least one score is determined corresponding to at least one second node;

selecting one or more edges having a 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 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.

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

11. The method of claim 1, further comprising:

determining a score for each selected grammar; and

wherein generating one or more structured queries comprises generating one or more structured queries corresponding to each selected grammar having score greater than a grammar-threshold score.

12. The method of claim 11, wherein determining the score for each grammar is based on a degree of separation between the first node and the identified second nodes corresponding to the query tokens of the grammar.

13. The method of claim 11, wherein determining the score for each grammar is based on the identified edges corresponding to the query tokens of the grammar.

14. The method of claim 11, wherein determining the score for each grammar is based on the number of identified edges connected to the identified second nodes corresponding to the query tokens of the grammar.

15. The method of claim 11, wherein determining the score for each grammar is based on a search history associated with the first user.

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

identify, based on the unstructured text query, one or more edges and one or more second nodes of the social graph, each of the identified edges and identified second nodes corresponding to at least a portion of the unstructured text query;

access a context-free grammar model comprising a grammar forest with a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, wherein the grammar forest is organized as an ordered tree comprising a plurality of non-terminal tokens and a plurality of query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token;

identify, based on the identified edges and identified second nodes of the social graph, one or more query tokens in one or more grammars of the grammar forest, each identified query token corresponding to at least one of the identified second nodes or identified edges of the social graph;

select one or more grammars of the grammar forest, each selected grammar comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph;

generate one or more structured queries, each structured query corresponding to a selected grammar, wherein each structured query is based on a natural-language string generated by the corresponding selected grammar, each structured query comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph; and

send, to the client system of the first user, one or more of the structured queries as suggested queries for display to the first user in response to the unstructured text query inputted by the first user.

17. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors 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 system of the first user, an unstructured text query inputted by the first user;

identify, based on the unstructured text query, one or more edges and one or more second nodes of the social graph, each of the identified edges and identified second nodes corresponding to at least a portion of the unstructured text query;

access a context-free grammar model comprising a grammar forest with a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, wherein the grammar forest is organized as an ordered tree comprising a plurality of non-terminal tokens and a plurality of query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token;

identify, based on the identified edges and identified second nodes of the social graph, one or more query tokens in one or more grammars of the grammar forest, each identified query token corresponding to at least one of the identified second nodes or identified edges of the social graph;

select one or more grammars of the grammar forest, each selected grammar comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph;

generate one or more structured queries, each structured query corresponding to a selected grammar, wherein each structured query is based on a natural-language string generated by the corresponding selected grammar, each structured query comprising at least one query token corresponding to each of the identified edges and identified second nodes of the social graph; and

send, to the client system of the first user, one or more of the structured queries as suggested queries for display to the first user in response to the unstructured text query inputted by the first user.