Grammar Model for Structured Search Queries
First Claim
Patent Images
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-user 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 the first user an unstructured text query;
identifying one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to 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 query tokens;
identifying one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the identified second nodes or identified edges;
determining a first score for each identified grammar; and
generating one or more structured queries, each structured query corresponding to an identified grammar having first score greater than a grammar-threshold score wherein the structured query is based on a string generated by the identified grammar, each structured query comprising the query tokens of the corresponding identified grammar, wherein one or more of the query tokens of the structured query corresponds to at least one of the identified second nodes or identified edges.
2 Assignments
0 Petitions
Accused Products
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.
11 Citations
20 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-user 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 the first user an unstructured text query; identifying one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to 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 query tokens; identifying one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the identified second nodes or identified edges; determining a first score for each identified grammar; and generating one or more structured queries, each structured query corresponding to an identified grammar having first score greater than a grammar-threshold score wherein the structured query is based on a string generated by the identified grammar, each structured query comprising the query tokens of the corresponding identified grammar, wherein one or more of the query tokens of the structured query corresponds to at least one of the identified second nodes or identified edges. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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-user 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 the first user a unstructured text query; identify one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to 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 query tokens; identify one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the identified second nodes or identified edges; determine a first score for each identified grammar; and generate one or more structured queries, each structured query corresponding to an identified grammar having first score greater than a grammar-threshold score wherein the structured query is based on a string generated by the identified grammar, each structured query comprising the query tokens of the corresponding identified grammar, wherein one or more of the query tokens of the structured query corresponds to at least one of the identified second nodes or identified edges. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
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;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-user 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 the first user a unstructured text query; identify one or more edges or one or more second nodes, each of the identified edges or identified nodes corresponding to 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 query tokens; identify one or more grammars, each identified grammar having one or more query tokens corresponding to at least one of the identified second nodes or identified edges; determine a first score for each identified grammar; and generate one or more structured queries, each structured query corresponding to an identified grammar having first score greater than a grammar-threshold score wherein the structured query is based on a string generated by the identified grammar, each structured query comprising the query tokens of the corresponding identified grammar, wherein one or more of the query tokens of the structured query corresponds to at least one of the identified second nodes or identified edges.
- one or more processors; and
Specification