Patent ID: 9679080
Date: 2017-06-13
CPC Classifications: G06F,G06Q

Claim:
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.