Modifying structured search queries on online social networks

• US 10,268,649 B2
• Filed: 05/16/2017
• Issued: 04/23/2019
• Est. Priority Date: 12/31/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Whitnah, Thomas S., Chatot, Olivier, Vee, Erik N., Maschmeyer, William R., Peiris, Keith L., Langenfeld, Alexander
• Primary Examiner(s): Rostami, Mohammad S
• Application Number:
  US15/596,888
• Publication Number:
  US 20170249307A1
• Time in Patent Office: 707 Days
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90328 using search space presentation or visualization, e.g. category or range presentation and selection
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes receiving a query input from a client system comprising one or more n-grams, sending instructions for presenting one or more suggested modifications for the query input, each suggested modification comprising references to one or more objects associated with the online social network, receiving an indication of a selection of one of the suggested modifications, parsing the query input and the selected suggested modification using a context-free grammar model to generate an executable query command, and sending instructions to the client system for presenting one or more search results corresponding to the query command.

Claims

1. A method comprising, by a computing system:

receiving, from a client system of a first user of an online social network, a query input comprising one or more n-grams;

sending, to the client system of the first user, instructions for presenting one or more suggested modifications for the query input, each suggested modification comprising references to one or more objects associated with the online social network;

receiving, from the client system of the first user, an indication of a selection of one of the suggested modifications;

parsing, using a context-free grammar model, the query input and the selected suggested modification to generate an executable query command, wherein the context-free grammar model comprising a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token, and wherein the query command corresponds to a particular grammar of the plurality of grammars, the query command comprising one or more defined functions corresponding to one or more of the query tokens of the particular grammar, wherein at least one of the defined functions corresponds to one or more of the objects referenced in the selected suggested modification;

generating, by the computing system, one or more search results corresponding to the query command corresponding to the particular grammar, wherein each search result corresponds to an object associated with the online social network that is connected to at least one of the referenced objects in the selected suggested modification; and

sending, to the client system of the first user, instructions for presenting one or more search results corresponding to the query command.

2. The method of claim 1, wherein the query input is a natural-language string generated by a grammar model of the context-free grammar model and references to one or more objects associated with the online social network.

3. The method of claim 2, wherein each suggested modification is selectable by the first user to modify the natural-language string of the query input to further comprise references to the one or more of the objects referenced in the suggested modification.

4. The method of claim 1, wherein the query input is an unstructured text query comprising one or more characters inputted by the first user.

5. The method of claim 1, wherein each suggested modification comprises one or more additional n-grams for the query input.

6. The method of claim 1, wherein each suggested modification comprises one or more alternative n-grams for the query input.

7. The method of claim 1, further comprising:

generating, responsive to receiving the query input, one or more suggested modifications for the query input; and

calculating a score for each suggested modification, wherein a threshold number of top scoring suggested modifications are sent to the client system of the first user.

8. The method of claim 7, wherein calculating the score for each suggested modification is based on a search history associated with the first user.

9. The method of claim 7, wherein calculating the score for each suggested modification is based on a social relevance of the suggested modification to the query input.

10. The method of claim 7, wherein calculating the score for each suggested modification is based on a number of possible search results corresponding to the suggested modification.

11. The method of claim 1, wherein each search result comprises one or more snippets, each snippet comprising contextual information about the object corresponding to the search result.

12. The method of claim 1, wherein if the one or more search results corresponding to the query command is a number below a threshold number of search result, then:

generating one or more one or more additional suggested modifications for the query input, each additional suggested modifications comprising at least one fewer reference to the objects than the selected suggested modification; and

sending, to the client system of the first user, instructions for presenting the one or more additional suggested modifications for display to the first user.

13. The method of claim 1, further comprising:

generating one or more additional suggested modifications based on the query input and the selected suggested modification; and

sending, to the client system of the first user, instructions for presenting the one or more additional suggested modifications.

14. The method of claim 1, wherein parsing the query input and the selected suggested modification to generate the executable query command comprises:

accessing the context-free grammar model;

comparing the query input and the selected suggested modification to one or more grammars of the context-free grammar model; and

generating the query command based on the particular grammar having one or more query tokens corresponding to one or more objects matching the query input or the selected suggested modification.

15. The method of claim 1, further comprising:

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 node corresponding to the first user; and

a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively.

16. The method of claim 15, wherein the one or more objects referenced in the suggested modifications correspond to one or more nodes from the plurality of second nodes or one or more edges from the plurality of edges.

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

receive, from a client system of a first user of an online social network, a query input comprising one or more n-grams;

send, to the client system of the first user, instructions for presenting one or more suggested modifications for the query input, each suggested modification comprising references to one or more objects associated with the online social network;

receive, from the client system of the first user, an indication of a selection of one of the suggested modifications;

parse, using a context-free grammar model, the query input and the selected suggested modification to generate an executable query command, wherein the context-free grammar model comprising a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token, and wherein the query command corresponds to a particular grammar of the plurality of grammars, the query command comprising one or more defined functions corresponding to one or more of the query tokens of the particular grammar, wherein at least one of the defined functions corresponds to one or more of the objects referenced in the selected suggested modification;

generate one or more search results corresponding to the query command corresponding to the particular grammar, wherein each search result corresponds to an object associated with the online social network that is connected to at least one of the referenced objects in the selected suggested modification; and

send, to the client system of the first user, instructions for presenting one or more search results corresponding to the query command.

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, from a client system of a first user of an online social network, a query input comprising one or more n-grams;

send, to the client system of the first user, instructions for presenting one or more suggested modifications for the query input, each suggested modification comprising references to one or more objects associated with the online social network;

receive, from the client system of the first user, an indication of a selection of one of the suggested modifications;

parse, using a context-free grammar model, the query input and the selected suggested modification to generate an executable query command, wherein the context-free grammar model comprising a plurality of grammars, each grammar comprising one or more non-terminal tokens and one or more query tokens, each grammar being an ordered sub-tree adjoining one or more other grammars via a non-terminal token, and wherein the query command corresponds to a particular grammar of the plurality of grammars, the query command comprising one or more defined functions corresponding to one or more of the query tokens of the particular grammar, wherein at least one of the defined functions corresponds to one or more of the objects referenced in the selected suggested modification;

generate one or more search results corresponding to the query command corresponding to the particular grammar, wherein each search result corresponds to an object associated with the online social network that is connected to at least one of the referenced objects in the selected suggested modification; and

send, to the client system of the first user, instructions for presenting one or more search results corresponding to the query command.

19. The system of claim 18, wherein the query input is a natural-language string generated by a grammar model of the context-free grammar model and references to one or more objects associated with the online social network.

20. The system of claim 19, wherein each suggested modification is selectable by the first user to modify the natural-language string of the query input to further comprise references to the one or more of the objects referenced in the suggested modification.

21. The system of claim 18, wherein the query input is an unstructured text query comprising one or more characters inputted by the first user.

22. The system of claim 18, wherein each suggested modification comprises one or more additional n-grams for the query input.

23. The system of claim 18, wherein each suggested modification comprises one or more alternative n-grams for the query input.

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

generate, responsive to receiving the query input, one or more suggested modifications for the query input; and

calculate a score for each suggested modification, wherein a threshold number of top scoring suggested modifications are sent to the client system of the first user.

25. The system of claim 24, wherein calculating the score for each suggested modification is based on a search history associated with the first user.

26. The system of claim 24, wherein calculating the score for each suggested modification is based on a social relevance of the suggested modification to the query input.

27. The system of claim 24, wherein calculating the score for each suggested modification is based on a number of possible search results corresponding to the suggested modification.

28. The system of claim 18, wherein each search result comprises one or more snippets, each snippet comprising contextual information about the object corresponding to the search result.

29. The system of claim 18, wherein if the one or more search results corresponding to the query command is a number below a threshold number of search result, then the processors are further operable when executing the instructions to:

generate one or more one or more additional suggested modifications for the query input, each additional suggested modifications comprising at least one fewer reference to the objects than the selected suggested modification; and

send, to the client system of the first user, instructions for presenting the one or more additional suggested modifications for display to the first user.

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

generate one or more additional suggested modifications based on the query input and the selected suggested modification; and

send, to the client system of the first user, instructions for presenting the one or more additional suggested modifications.

31. The system of claim 18, wherein the instruction to parse the query input and the selected suggested modification to generate the executable query command comprises instruction to:

access the context-free grammar model;

compare the query input and the selected suggested modification to one or more grammars of the context-free grammar model; and

generate the query command based on the particular grammar having one or more query tokens corresponding to one or more objects matching the query input or the selected suggested modification.

32. The system of claim 18, wherein the processors are further 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 node corresponding to the first user; and

a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively.

33. The system of claim 32, wherein the one or more objects referenced in the suggested modifications correspond to one or more nodes from the plurality of second nodes or one or more edges from the plurality of edges.