Client-side search templates for online social networks

• US 9,336,300 B2
• Filed: 01/17/2014
• Issued: 05/10/2016
• Est. Priority Date: 01/17/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Xie, Tao, Kazi, Rousseau Newaz, Boucher, Maxime, Wu, Yunnan
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US14/158,594
• Publication Number:
  US 20150205858A1
• Time in Patent Office: 844 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15

Abstract

In one embodiment, a method includes receiving an unstructured text query from a first user of an online social network; and accessing, from a data store of the mobile client system, a set of nodes of a social graph of the online social network. The social graph includes a number of nodes and edges connecting the nodes. The nodes include a first node corresponding to the first user and a number of second nodes that each correspond to a concept or a second user associated with the online social network. The method also includes accessing, from the data store of the mobile client system, a set of grammar templates. Each grammar template includes one or more non-terminal tokens and one or more query tokens. The query tokens include references to zero or more second nodes and one or more edges and each grammar template is based on a natural-language string.

Claims

1. A method comprising, by one or more processors associated with a mobile client system:

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

parsing, by the mobile client system, the unstructured text query into one or more n-grams;

accessing, from a data store of the mobile client system, a set of nodes of a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, 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;

accessing, from the data store of the mobile client system, a set of grammar templates, each grammar template comprising one or more non-terminal tokens and one or more query tokens, wherein the query tokens comprise references to zero or more second nodes and one or more edges, and wherein each grammar template is based on a natural-language string;

generating, by the mobile client system, one or more structured queries by matching the unstructured text query to one or more of the accessed nodes and one or more of the grammar templates having non-terminal tokens corresponding to the matched nodes, each structured query comprising references to one or more of the accessed nodes matched to the one or more non-terminal tokens and the zero or more of the second nodes and the one or more edges referenced in the corresponding grammar template;

calculating, by the mobile client system, a cost for each grammar template based at least in part on one or more of the n-grams not corresponding to one of the non-terminal tokens or query tokens; and

displaying, at the mobile client system, one or more structured queries to the first user;

wherein each non-terminal token and query token has an associated insertion cost; and

wherein calculating the cost comprises incurring an insertion cost for each of the non-terminal tokens or query tokens not corresponding to one or more n-grams.

2. The method of claim 1, wherein the calculating the cost comprises identifying, by the mobile client system, a particular non-terminal token from one or more of the non-terminal tokens that correspond to a particular n-gram based at least in part on the insertion cost of each non-terminal token.

3. The method of claim 1, wherein the calculating the cost comprises:

associating, by the mobile client system, one of the accessed nodes to one of the non-terminal tokens; and

incurring the insertion cost for the non-terminal token and the associated accessed node based on the associated accessed node not corresponding to one of the n-grams.

4. The method of claim 1, further comprising ranking, by the mobile client system, one or more of the structured queries based at least in part on the calculated cost of the associated grammar template.

5. The method of claim 1, wherein the calculating the cost comprises incurring a base cost associated with each grammar template, the base cost having an inverse relationship to a popularity measure associated with one or more search queries that are a basis of each grammar template.

6. The method of claim 5, wherein the popularity measure is based at least in part on a search-query history of the first user.

7. The method of claim 6, wherein the popularity measure is based at least in part on a search-query history of users of the online social network.

8. The method of claim 1, wherein each of the displayed structured queries has a calculated cost below a threshold cost value.

9. The method of claim 1, wherein the receiving, by the mobile client system, from the first user the unstructured text query comprises receiving one or more characters of a character string as the user enters the character string into a graphical user interface.

10. The method of claim 9, further comprising updating, by the mobile client system, one or more of the structured queries by matching a unstructured text query that is modified as the user enters one or more subsequent characters into the graphical user interface.

11. The method of claim 1, wherein each node of the set of nodes has a coefficient above a threshold value.

12. The method of claim 1, further comprising receiving, by the mobile computing device, an updated set of grammar templates or an updated set of nodes from the online social network at a pre-determined interval.

13. The method of claim 1, further comprising, in response to a selection of one of the displayed structured queries from the first user, sending, by the mobile client system, the selected structured query to the online social network.

14. The method of claim 13, further comprising receiving, by the mobile client system, one or more search results in response to the selected structured query being sent to the online social network.

15. The method of claim 14, wherein each of the search results corresponds to a particular second node of the plurality of second nodes.

16. The method of claim 1, wherein:

the set of nodes comprises a pre-determined number of nodes; and

the set of grammar templates comprises a pre-determined number of grammar templates.

17. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

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

parse, by the mobile client system, the unstructured text query into one or more n-grams;

access, from a data store of the mobile client system, a set of nodes of a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, 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;

access, from the data store of the mobile client system, a set of grammar templates, each grammar template comprising one or more non-terminal tokens and one or more query tokens, wherein the query tokens comprise references to zero or more second nodes and one or more edges, and wherein each grammar template is based on a natural-language string;

generate, by the mobile client system, one or more structured queries by matching the unstructured text query to one or more of the accessed nodes and one or more of the grammar templates having non-terminal tokens corresponding to the matched nodes, each structured query comprising references to one or more of the accessed nodes matched to the one or more non-terminal tokens and the zero or more of the second nodes and the one or more edges referenced in the corresponding grammar template;

calculate, by the mobile client system, a cost for each grammar template based at least in part on one or more of the n-grams not corresponding to one of the non-terminal tokens or query tokens; and

display, at the mobile client system, one or more structured queries to the first user;

wherein each non-terminal token and query token has an associated insertion cost; and

wherein calculating the cost comprises incurring an insertion cost for each of the non-terminal tokens or query tokens not corresponding to one or more n-grams.

18. 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, at the mobile client system, an unstructured text query from a first user of an online social network;

parse, by the mobile client system, the unstructured text query into one or more n-grams;

access, from a data store of the mobile client system, a set of nodes of a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, 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;

access, from the data store of the mobile client system, a set of grammar templates, each grammar template comprising one or more non-terminal tokens and one or more query tokens, wherein the query tokens comprise references to zero or more second nodes and one or more edges, and wherein each grammar template is based on a natural-language string;

generate, by the mobile client system, one or more structured queries by matching the unstructured text query to one or more of the accessed nodes and one or more of the grammar templates having non-terminal tokens corresponding to the matched nodes, each structured query comprising references to one or more of the accessed nodes matched to the one or more non-terminal tokens and the zero or more of the second nodes and the one or more edges referenced in the corresponding grammar template;

calculate, by the mobile client system, a cost for each grammar template based at least in part on one or more of the n-grams not corresponding to one of the non-terminal tokens or query tokens; and

display, at the mobile client system, one or more structured queries to the first user;

wherein each non-terminal token and query token has an associated insertion cost; and

wherein calculating the cost comprises incurring an insertion cost for each of the non-terminal tokens or query tokens not corresponding to one or more n-grams.