Grammar Model for Search Queries

Abstract

In one embodiment, a method includes receiving a text query inputted by a first user, identifying objects associated with the online social network, each identified object having a name string matching at least in part a portion of the text query, determining a probability score for each identified object that the identified object corresponds to a respective portion of the text query, selecting one or more of the identified objects based on the probability score of the identified object, identifying one or more grammars of a grammar model, each identified grammar having query tokens corresponding to at least one of the selected objects, and sending instructions for presenting suggested queries to the first user, each suggested query comprising the text string, a query token corresponding to one of the selected objects, and one or more additional query tokens of the identified grammar corresponding to the respective selected object.

What is claimed is: 
     
         1 . A method comprising, by a computing system:
 receiving, from a client system of a first user of an online social network, a text query inputted by the first user, wherein the text query comprises a text string;   identifying, based on the text query, one or more objects associated with the online social network, each identified object having a name string matching at least in part a portion of the text string;   determining, for each identified object, a probability score for the identified object that the identified object corresponds to a respective portion of the text string matching the identified object;   selecting one or more of the identified objects based on the probability score of the identified object, each of the one or more selected objects corresponding to at least one of the portions of the text string;   identifying one or more grammars of a grammar model, each identified grammar having one or more query tokens corresponding to at least one of the selected objects; and   sending, to the client system responsive to the text query inputted by the first user, instructions for presenting one or more suggested queries to the first user, each suggested query comprising the text string, a query token corresponding to one of the selected objects, and one or more additional query tokens of the identified grammar corresponding to the respective selected object.   
     
     
         2 . The method of  claim 1 , wherein the instructions for presenting the one or more suggested queries to the first user are sent to a frontend typeahead process of an application on the client system. 
     
     
         3 . The method of  claim 1 , wherein the one or more suggested queries are automatically populated by a frontend typeahead process into a query field of an application on the client system. 
     
     
         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 edge between two nodes establishing a single degree of separation between them, the plurality of nodes comprising:
 a first node corresponding to the first user; and 
 a plurality of second nodes corresponding to a plurality of associated with the online social network, respectively. 
   
     
     
         5 . The method of  claim 4 , wherein identifying one or more objects associated with the online network comprises identifying one or more edges or one or more nodes of the social graph, each of the identified edges or identified nodes corresponding to at least a portion of the text string. 
     
     
         6 . The method of  claim 5 , wherein selecting one or more of the identified objects based on the probability score of the identified object 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 a portion of the text string; 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 a portion of the text string.   
     
     
         7 . The method of  claim 5 , wherein, for each suggested query, one or more of the query tokens of the suggested query corresponds to at least one of the identified nodes or at least one of the identified edges of the social graph. 
     
     
         8 . The method of  claim 5 , wherein the probability score is a probability the identified edge or identified node corresponds to the respective portion of the text string matching the identified edge or identified node. 
     
     
         9 . The method of  claim 8 , further comprising:
 generating one or more suggested queries, each suggested 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 suggested query comprises a natural-language string generated by the corresponding grammar of the grammar model and further comprising the query tokens of the corresponding grammar of the grammar model.   
     
     
         10 . The method of  claim 1 , further comprising accessing the grammar model, wherein the grammar model is a context-free grammar model comprising a plurality of grammars, each grammar comprising one or more query tokens. 
     
     
         11 . The method of  claim 1 , further comprising determining a grammar-score for each identified grammar. 
     
     
         12 . The method of  claim 11 , wherein each suggested query corresponds to an identified grammar having grammar-score greater than a threshold grammar-score. 
     
     
         13 . The method of  claim 1 , wherein identifying the one or more grammars is based on a degree of separation on the online social network between the first user and the one or more selected objects corresponding to one or more query tokens of the grammar, respectively. 
     
     
         14 . The method of  claim 1 , wherein identifying the one or more grammars is based on a type of the selected objects corresponding to the query tokens of the grammar. 
     
     
         15 . The method of  claim 1 , wherein identifying the one or more grammars is based on a number of selected objects corresponding to the query tokens of the grammar. 
     
     
         16 . The method of  claim 1 , wherein identifying the one or more grammars is based on a search history associated with the first user. 
     
     
         17 . The method of  claim 1 , wherein the text string comprises one or more characters of text entered by the first user. 
     
     
         18 . The method of  claim 1 , wherein the determined probability score for each identified object is a probability that identified object corresponds to the respective portion of the text string matching to the identified object. 
     
     
         19 . One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
 receive, from a client system of a first user of an online social network, a text query inputted by the first user, wherein the text query comprises a text string;   identify, based on the text query, one or more objects associated with the online social network, each identified object having a name string matching at least in part a portion of the text string;   determine, for each identified object, a probability score for the identified object that the identified object corresponds to a respective portion of the text string matching the identified object;   select one or more of the identified objects based on the probability score of the identified object, each of the one or more selected objects corresponding to at least one of the portions of the text string;   identify one or more grammars of a grammar model, each identified grammar having one or more query tokens corresponding to at least one of the selected objects; and   send, to the client system responsive to the text query inputted by the first user, instructions for presenting one or more suggested queries to the first user, each suggested query comprising the text string, a query token corresponding to one of the selected objects, and one or more additional query tokens of the identified grammar corresponding to the respective selected object.   
     
     
         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 system of a first user of an online social network, a text query inputted by the first user, wherein the text query comprises a text string;   identify, based on the text query, one or more objects associated with the online social network, each identified object having a name string matching at least in part a portion of the text string;   determine, for each identified object, a probability score for the identified object that the identified object corresponds to a respective portion of the text string matching the identified object;   select one or more of the identified objects based on the probability score of the identified object, each of the one or more selected objects corresponding to at least one of the portions of the text string;   identify one or more grammars of a grammar model, each identified grammar having one or more query tokens corresponding to at least one of the selected objects; and   send, to the client system responsive to the text query inputted by the first user, instructions for presenting one or more suggested queries to the first user, each suggested query comprising the text string, a query token corresponding to one of the selected objects, and one or more additional query tokens of the identified grammar corresponding to the respective selected object.