Natural-language rendering of structured search queries

• US 10,445,352 B2
• Filed: 03/17/2016
• Issued: 10/15/2019
• 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:
  US15/073,374
• Publication Number:
  US 20160196335A1
• Time in Patent Office: 1,307 Days
• Field of Search: None
• 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 receiving an unstructured text query inputted by a first user, identifying one or more objects associated with the online social network matching at least a portion of the unstructured text query, accessing a context-free grammar model comprising a plurality of grammars, generating one or more structured queries, each structured query corresponding to a selected grammar of a context-free grammar model, wherein each structured query is based on a natural-language string generated by the selected grammar, each structured query comprising at least one query token corresponding to each of the identified object, and sending 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.

Claims

1. A method comprising, by a computing device:

receiving, from a client system of a first user of an online social network, an unstructured text query inputted by the first user;

identifying, based on the unstructured text query, one or more objects associated with the online social network matching 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 non-terminal tokens and one or more query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token;

generating one or more structured queries, each structured query corresponding to a selected grammar of the context-free grammar model, wherein each structured query comprises a natural-language string generated by the selected grammar, each structured query comprising at least one query token corresponding to each of the identified object, wherein each structured query consists of the natural-language string generated by the selected grammar and one or more query tokens within the natural-language string corresponding to one or more of the identified objects, respectively; 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, 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.

3. The method of claim 1, wherein the plurality of grammars of the context-free grammar model is a grammar forest 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.

4. The method of claim 3, further comprising:

identifying, based on the identified objects, 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 objects; and

selecting one or more grammars of the grammar forest, each selected grammar comprising at least one query token corresponding to each of the identified objects.

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

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

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

8. 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 query tokens of the selected grammar; 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 objects corresponding to query tokens of the selected grammar.

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

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

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

12. The method of claim 9, wherein identifying one or more objects comprises:

determining a score for each n-gram that indicates that the n-gram corresponds to an object associated with the online social network; and

selecting one or more objects having a score greater than a threshold score, each of the selected objects corresponding to at least one of the n-grams.

13. The method of claim 12, wherein the score for each n-gram is a probability that the n-gram corresponds to the object associated with the online social network.

14. The method of claim 1, further comprising:

determining a score for one or more grammars of the plurality of grammars; and

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

15. The method of claim 14, wherein determining the score for each grammar is based on a degree of separation in a social graph between the first user and at least one identified object corresponding to at least one query token of the grammar.

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

17. The method of claim 1, wherein the structured queries are displayed in a user interface of an application associated with the online social network installed on the client system of the first user.

18. The method of claim 1, wherein the structured queries are displayed in a webpage accessed by a web browser on the client system of the first user.

19. One or more computer-readable non-transitory storage media comprising computer instructions that are operable when executed to:

receive, from a client system of a first user of an online social network, an unstructured text query inputted by the first user;

identify, based on the unstructured text query, one or more objects associated with the online social network matching at least a portion of the unstructured text query;

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

generate one or more structured queries, each structured query corresponding to a selected grammar of the context-free grammar model, wherein each structured query comprises a natural-language string generated by the selected grammar, each structured query comprising at least one query token corresponding to each of the identified object, wherein each structured query consists of the natural-language string generated by the selected grammar and one or more query tokens within the natural-language string corresponding to one or more of the identified objects, respectively; 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.

20. 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;

receive, from a client system of a first user of an online social network, an unstructured text query inputted by the first user;

identify, based on the unstructured text query, one or more objects associated with the online social network matching at least a portion of the unstructured text query;

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

generate one or more structured queries, each structured query corresponding to a selected grammar of the context-free grammar model, wherein each structured query comprises a natural-language string generated by the selected grammar, each structured query comprising at least one query token corresponding to each of the identified object, wherein each structured query consists of the natural-language string generated by the selected grammar and one or more query tokens within the natural-language string corresponding to one or more of the identified objects, respectively; 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.