Query construction on online social networks

• US 10,268,765 B2
• Filed: 09/20/2016
• Issued: 04/23/2019
• 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:
  US15/270,896
• Publication Number:
  US 20170011122A1
• Time in Patent Office: 945 Days
• Field of Search: 707706, 707722, 707736, 707758, 707759, 707760, 707769, 707781, 707999003-999005
• 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 presenting, by a client system, grammar tokens, each grammar token being based on a natural-language string and comprising references to objects associated with an online social network, receiving, at the client system, a selection of one of the presented grammar tokens, the selected grammar token being based on a first natural-language string, presenting, by the client system, completion tokens, wherein each completion token is based on a natural-language string corresponding to the first natural-language string and comprises references to objects associated with the online social network, receiving, at the client system, a selection of one of the 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 and completion tokens, the structured query comprising references to the objects referenced in the selected grammar and completion tokens.

Claims

1. A method comprising:

presenting, by a client system, one or more grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user, wherein each grammar token is based on a natural-language string generated by a grammar of a context-free grammar model and comprises references to one or more objects associated with an online social network;

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 generated by a first grammar of the context-free grammar model;

presenting, by the client system, one or more completion tokens to the first user, each of the presented completion tokens being selectable by the first user, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token and comprises references to one or more objects associated with the online social network;

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 generated by a second grammar of the context-free grammar model; 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 one or more objects referenced in the selected grammar token and the selected completion token.

2. The method of claim 1, further comprising:

sending, by the client system in response to the selection of one of the completion tokens by the first user, 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 objects referenced by the grammar token.

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 object referenced by 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 object referenced by 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 presenting, 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 presented 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 objects referenced by the selected grammar token; and

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

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:

presenting, at 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, wherein each modifying completion token is based on a natural-language string corresponding to the first and second natural-language strings and comprises references to one or more objects associated with the online social network;

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 one or more object referenced in the selected modifying completion token.

17. The method of claim 16, 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.

18. The method of claim 1, further comprising:

accessing, by the client system, 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, wherein each grammar token comprises references to zero or more nodes and one or more edges, and each grammar token corresponds to a particular type of completion token, and wherein each completion token comprises 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, and wherein 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.

19. The method of claim 1, wherein the first grammar and the second grammar are the same grammar of the context-free grammar model.

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

present, by a client system, one or more grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user, wherein each grammar token is based on a natural-language string generated by a grammar of a context-free grammar model and comprises references to one or more objects associated with an online social network;

receive, 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 generated by a first grammar of the context-free grammar model;

present, by the client system, one or more completion tokens to the first user, each of the presented completion tokens being selectable by the first user, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token and comprises references to one or more objects associated with the online social network;

receive, 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 generated by a second grammar of the context-free grammar model; and

generate, 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 one or more objects referenced in the selected grammar token and 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;

present, by a client system, one or more grammar tokens to the first user, each of the presented grammar tokens being selectable by the first user, wherein each grammar token is based on a natural-language string generated by a grammar of a context-free grammar model and comprises references to one or more objects associated with an online social network;

receive, 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 generated by a first grammar of the context-free grammar model;

present, by the client system, one or more completion tokens to the first user, each of the presented completion tokens being selectable by the first user, wherein each completion token is based on a natural-language string corresponding to the first natural-language string of the selected grammar token and comprises references to one or more objects associated with the online social network;

receive, 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 generated by a second grammar of the context-free grammar model; and

generate, 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 one or more objects referenced in the selected grammar token and the selected completion token.

22. The system of claim 21, wherein the processors are further operable when executing the instructions to:

send, by the client system in response to the selection of one of the completion tokens by the first user, the structured query to a search engine associated with the online social network; and

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

23. The system of claim 21, 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.

24. The system of claim 21, wherein the processors are further operable when executing the instructions to:

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

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

identify, 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 objects referenced by the grammar token.

25. The system of claim 24, wherein the matching comprises matching one or more of the n-grams to a character string associated with the object referenced by the grammar token.

26. The system of claim 24, wherein the processors are further operable when executing the instructions to filter, 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 object referenced by the grammar token.

27. The system of claim 24, wherein the processors are further operable when executing the instructions to identify, 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.

28. The system of claim 24, wherein the instructions to receive the unstructured text query comprises instructions to receive, 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.

29. The system of claim 28, wherein the graphical user interface comprises a search-query field of a native application associated with the online social network.

30. The system of claim 21, wherein the processors are further operable when executing the instructions to present, 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 presented completion token being associated with the selected grammar token.

31. The system of claim 21, wherein the instructions to access one or more of the completion tokens comprise instructions to:

identify, by the client system, a type associated with the objects referenced by the selected grammar token; and

identify, by the client system, one or more completion tokens associated with the determined type of the objects.

32. The system of claim 21, wherein the processors are further operable when executing the instructions to rank, 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.

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

34. The system of claim 21, wherein the processors are further operable when executing the instructions to rank, 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.

35. The system of claim 34, wherein the ranking is further based on a combination of the selected grammar token and the calculated affinity to each completion token.

36. The system of claim 21, wherein the processors are further operable when executing the instructions to:

present, at the client system, one or more modifying completion tokens in response to the reception of one or more characters subsequent to the selection of the completion token, wherein each modifying completion token is based on a natural-language string corresponding to the first and second natural-language strings and comprises references to one or more objects associated with the online social network;

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

generate, 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 one or more object referenced in the selected modifying completion token.

37. The system of claim 36, wherein the processors are further operable when executing the instructions to:

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

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

38. The system of claim 21, wherein the processors are further operable when executing the instructions to:

access, by the client system, 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, wherein each grammar token comprises references to zero or more nodes and one or more edges, and each grammar token corresponds to a particular type of completion token, and wherein each completion token comprises 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, and wherein 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.

39. The system of claim 21, wherein the first grammar and the second grammar are the same grammar of the context-free grammar model.