Grammar model for structured search queries

• US 9,679,080 B2
• Filed: 06/26/2015
• Issued: 06/13/2017
• Est. Priority Date: 11/12/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: Lee, Yofay Kari, Boucher, Maxime, Hymes, Kathryn, Li, Xiao, Campbell, Amy, Cohen, Michael Benjamin, Azzolini, Alisson Gusatti, Rasmussen, Lars Eilstrup
• Primary Examiner(s): Andersen, Kris
• Application Number:
  US14/752,407
• Publication Number:
  US 20150293931A1
• Time in Patent Office: 718 Days
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/33 Querying
• 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
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• 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 n-grams of the text query, accessing a context-free grammar model, identifying grammars having query tokens that correspond to the identified nodes and edges, determining a score for each identified grammar, and then generating structured queries based on the identified grammars based on strings generated by the grammars.

Claims

1. A method comprising, by a computing device:

receiving, from a client device of a first user of an online social network, an unstructured text query inputted by the first user, wherein the unstructured text query comprises a plurality of n-grams, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

identifying, based on the unstructured text query, one or more edges and one or more nodes of the social graph, each of the n-grams of the plurality of n-grams matching at least in part a name string of at least one of the identified edges or identified nodes;

determining, for each identified node, a probability score for the identified node that the identified node corresponds to a respective n-gram matching the identified node;

determining, for each identified edge, a probability score for the identified edge that the identified edge corresponds to a respective n-gram matching the identified edge;

selecting one or more of the identified edges and one or more of the identified nodes based the probability score of the identified edge and the probability score of the identified node, each of the one or more selected edges or selected nodes corresponding to at least one of the n-grams;

generating, responsive to the selection of the one or more selected edges and selected and nodes, one or more structured queries, each structured query corresponding to a grammar of a context-free grammar model having one or more query tokens corresponding each of the selected edges and nodes, wherein each structured query comprises a natural-language string generated by the corresponding grammar of the grammar model and further comprises the query tokens of the corresponding grammar of the grammar model; and

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

2. The method of claim 1, further comprising accessing the context-free grammar model, wherein the context-free grammar model comprises a plurality of grammars, each grammar comprising one or more query tokens.

3. The method of claim 2, further comprising identifying one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the selected nodes and at least one of the selected edges.

4. The method of claim 3, further comprising determining a grammar-score for each identified grammar.

5. The method of claim 4, wherein each structured query corresponds to an identified grammar having grammar-score greater than a threshold grammar-score.

6. The method of claim 4, wherein determining the grammar-score for each identified grammar is based on a degree of separation between a first node of the social graph corresponding to the first user and one or more second nodes of the social graph corresponding to one or more query tokens of the grammar, respectively.

7. The method of claim 4, wherein determining the grammar-score for each identified grammar is based on the selected edges corresponding to the query tokens of the grammar.

8. The method of claim 4, wherein determining the grammar-score for each identified grammar is based on the number of selected edges connected to the selected nodes corresponding to the query tokens of the grammar.

9. The method of claim 4, wherein determining the grammar-score for each identified grammar is based on a search history associated with the first user.

10. The method of claim 1, wherein, for each structured query, one or more of the query tokens of the structured query corresponds to at least one of the identified nodes and at least one of the identified edges of the social graph.

11. The method of claim 1, further comprising accessing the social graph, wherein each of the edges between two of the nodes represents a single degree of separation between them, the nodes comprising:

a first node corresponding to the first user; and

a plurality of second nodes that each correspond to a concept or a second user associated with the online social network.

12. The method of claim 1, wherein selecting one or more of the identified edges and one or more of the identified nodes based on their determined probability scores comprises:

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

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

13. The method of claim 1, wherein the unstructured text query comprises a string of characters, and wherein the one or more of the structured queries are sent in response to each character being inputted by the first user.

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

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

16. 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 of an online social network, an unstructured text query inputted by the first user, wherein the unstructured text query comprises a plurality of n-grams, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

identify, based on the unstructured text query, one or more edges and one or more nodes of the social graph, each of the n-grams of the plurality of n-grams matching at least in part a name string of at least one of the identified edges or identified nodes;

determine, for each identified node, a probability score for the identified node that the identified node corresponds to a respective n-gram matching the identified node;

determine, for each identified edge, a probability score for the identified edge that the identified edge corresponds to a respective n-gram matching the identified edge;

select one or more of the identified edges and one or more of the identified nodes based on the probability score of the identified edge and the probability score of the identified node, each of the one or more selected edges or selected nodes corresponding to at least one of the n-grams;

generate, responsive to the selection of the one or more selected edges and selected and nodes, one or more structured queries, each structured query corresponding to a grammar of a context-free grammar model having one or more query tokens corresponding each of the selected edges and nodes, wherein each structured query comprises a natural-language string generated by the corresponding grammar of the grammar model and further comprises the query tokens of the corresponding grammar of the grammar model; and

send, to the client system of the first user in response to the unstructured text query inputted by the first user, one or more of the generated structured queries for display to 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 operable when executing the instructions to;

receive, from a client device of a first user of an online social network, an unstructured text query inputted by the first user, wherein the unstructured text query comprises a plurality of n-grams, the online social network being associated with a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes;

identify, based on the unstructured text query, one or more edges and one or more nodes of the social graph, each of the n-grams of the plurality of n-grams matching at least in part a name string of at least one of the identified edges or identified nodes;

determine, for each identified node, a probability score for the identified node that the identified node corresponds to a respective n-gram matching the identified node;

determine, for each identified edge, a probability score for the identified edge that the identified edge corresponds to a respective n-gram matching the identified edge;

select one or more of the identified edges and one or more of the identified nodes based on the probability score of the identified edge and the probability score of the identified node, each of the one or more selected edges or selected nodes corresponding to at least one of the n-grams;

generate, responsive to the selection of the one or more selected edges and selected and nodes, one or more structured queries, each structured query corresponding to a grammar of a context-free grammar model having one or more query tokens corresponding each of the selected edges and nodes, wherein each structured query comprises a natural-language string generated by the corresponding grammar of the grammar model and further comprises the query tokens of the corresponding grammar of the grammar model; and

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