Query construction on online social networks

• US 9,477,760 B2
• Filed: 02/12/2014
• Issued: 10/25/2016
• Est. Priority Date: 02/12/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, Maschmeyer, William R., Dunn, Colin William, Boucher, Maxime, Kalani, Christopher Joseph
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/179,357
• Publication Number:
  US 20150227619A1
• Time in Patent Office: 986 Days
• Field of Search: 707/706, 707/722, 707/736, 707/758, 707/759, 707/760, 707/769, 707/781
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes accessing a set of nodes of a social graph of an online social network. The social graph includes a number of nodes and a number of edges connecting the nodes. Each of the edges between two of the nodes representing a single degree of separation between them. The nodes include a first node that corresponds to the first user and a number of nodes that each correspond to a concept or a second user associated with the online social network. The method also includes accessing one or more grammar tokens. Each grammar token includes references to zero or more nodes and one or more edges. Each grammar token corresponds to a particular type of completion token. Each grammar token may be based on a natural-language string. The method also includes receiving from the first user a selection of one or more of the grammar tokens and one or more of the completion tokens.

Claims

1. A method comprising:

accessing, by a client system, a set of nodes of a social graph of an online social network, the 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;

accessing, by the client system, one or more grammar tokens, each grammar token comprising references to zero or more nodes and one or more edges, and each grammar token corresponding to a particular type of completion token, wherein each grammar token is based on a natural-language string;

presenting, by the client system, one or more of the grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user;

receiving, at the client system, from the first user a selection of one of the presented grammar tokens, the selected grammar token being based on a first natural-language string;

accessing, by the client system, one or more completion tokens, each completion token comprising references to one or more nodes and zero or more edges, and each completion token being of the particular type corresponding to the selected grammar token, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token;

presenting, by the client system, one or more of the completion tokens to the first user, each of the presented completion tokens being selectable by the first user;

receiving, at the client system, from the first user a selection of one of the presented completion tokens, the selected completion token being based on a second natural-language string; and

generating, by the client system, a structured query corresponding to the selected grammar token and the selected completion token, the structured query comprising references to the zero or more of the nodes and the one or more edges referenced in the selected grammar token and references to the one or more of the nodes and the zero or more of the edges of the selected completion token.

2. The method of claim 1, further comprising:

sending, by the client system, the structured query to a search engine associated with the online social network; and

receiving, at the client system, one or more search results generated by the search engine, each search result corresponding to the structured query.

3. The method of claim 1, wherein:

the structured query is based on the natural-language string corresponding to the first natural-language string of the selected grammar token and the second natural-language string of the selected completion token.

4. The method of claim 1, further comprising:

receiving, at the client system, an unstructured text query from the first user;

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

identifying, by the client system, one or more of the grammar tokens based at least in part on one or more of the n-grams matching one or more of the nodes or edges of the grammar token, wherein the accessing of each grammar token is based at least in part on the identification of one or more of the grammar tokens corresponding to the unstructured text query.

5. The method of claim 4, wherein the matching comprises matching one or more of the n-grams to a character string associated with the nodes or edges of the grammar token.

6. The method of claim 4, further comprising filtering, by the client system, one or more of the grammar tokens based at least in part on one or more of the n-grams not matching the nodes or edges of the grammar token.

7. The method of claim 4, further comprising identifying, by the client system, one or more of the completion tokens based at least in part on one or more n-grams subsequently provided in response to the selection of the grammar token.

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

9. The method of claim 8, wherein the graphical user interface comprises a search-query field of a native application associated with the online social network.

10. The method of claim 1, further comprising displaying, at the client system, one or more of the completion tokens, wherein one or more of the completion tokens are selected based at least in part on each displayed completion token being associated with the selected grammar token.

11. The method of claim 1, wherein accessing one or more of the completion tokens comprises:

identifying, by the client system, a type associated with the nodes or edges of the selected grammar token; and

identifying, by the client system, one or more completion tokens associated with the determined type of the nodes or edges.

12. The method of claim 1, further comprising ranking, by the client system, the completion tokens based at least in part on a popularity measure associated with a combination of the selected grammar token and each completion token.

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

14. The method of claim 1, further comprising ranking, by the client system, the completion tokens based at least in part on a calculated affinity of the selected grammar token to each completion token.

15. The method of claim 14, wherein the ranking is further based on a combination of the selected grammar token and the calculated affinity to each completion token.

16. The method of claim 1, further comprising:

in response to the selection of one of the grammar tokens by the first user, sending, by the client system, the structured query to the online social network; and

receiving, by the client system, one or more search results in response to the structured query being sent to the online social network.

17. The method of claim 1, further comprising:

accessing, by the client system, one or more modifying completion tokens in response to receiving one or more characters subsequent to the selection of the completion token;

receiving, at the client system, an input corresponding to a selection of at least one of the modifying completion tokens; and

generating, by the client system, one or more modified structured queries corresponding to the selected modifying completion token, each modified structured query comprising references to the zero or more of the nodes and the one or more edges referenced in the selected modifying completion token.

18. The method of claim 17, further comprising:

sending, by the client system, the modified structured query to the online social network; and

receiving, by the client system, one or more search results in response to the modified structured query being sent to the online social network.

19. The method of claim 1, wherein the plurality of nodes comprises:

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.

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

access a set of nodes of a social graph of an online social network, the 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;

access one or more grammar tokens, each grammar token comprising references to zero or more nodes and one or more edges, and each grammar token corresponding to a particular type of completion token, wherein each grammar token is based on a natural-language string;

present one or more of the grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user;

receive from the first user a selection of one of the presented grammar tokens, the selected grammar token being based on a first natural-language string;

access one or more completion tokens, each completion token comprising references to one or more nodes and zero or more edges, and each completion token being of the particular type corresponding to the selected grammar token, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token;

present one or more of the completion tokens to the first user, each of the presented completion tokens being selectable by the first user;

receive from the first user a selection of one of the presented completion tokens, the selected completion token being based on a second natural-language string; and

generate one or more structured queries corresponding to the selected grammar token and the selected completion token, each structured query comprising references to the zero or more of the nodes and the one or more edges referenced in the selected grammar token and references to the one or more of the nodes and the zero or more of the edges of the selected completion token.

21. 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 set of nodes of a social graph of an online social network, the 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;

access one or more grammar tokens, each grammar token comprising references to zero or more nodes and one or more edges, and each grammar token corresponding to a particular type of completion token, wherein each grammar token is based on a natural-language string;

present one or more of the grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user;

receive from the first user a selection of one of the presented grammar tokens, the selected grammar token being based on a first natural-language string;

access one or more completion tokens, each completion token comprising references to one or more nodes and zero or more edges, and each completion token being of the particular type corresponding to the selected grammar token, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token;

present one or more of the completion tokens to the first user, each of the presented completion tokens being selectable by the first user;

receive from the first user a selection of one of the presented completion tokens, the selected completion token being based on a second natural-language string; and

generate one or more structured queries corresponding to the selected grammar token and the selected completion token, each structured query comprising references to the zero or more of the nodes and the one or more edges referenced in the selected grammar token and references to the one or more of the nodes and the zero or more of the edges of the selected completion token.