Modifying structured search queries on online social networks

• US 9,361,363 B2
• Filed: 12/31/2012
• Issued: 06/07/2016
• 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: Langenfeld, Alexander, Whitnah, Thomas S., Chatot, Olivier, Vee, Erik N., Maschmeyer, William R., Peiris, Keith L.
• Primary Examiner(s): Rostami, Mohammad S
• Application Number:
  US13/731,910
• Publication Number:
  US 20140188899A1
• Time in Patent Office: 1,254 Days
• US Class Current: 1/1
• 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 accessing a social graph that includes a plurality of nodes and edges, receiving a structured query that includes references to selected nodes and edges, and generating one or more query modification for the structured query, where each query modification includes references to modified nodes or modified edges from the plurality of nodes and edges.

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 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 a client system of the first user, a first structured query comprising a natural-language string generated by a grammar model and references to one or more selected nodes from the plurality of second nodes and one or more selected edges from the plurality of edges;

generating one or more query modifications for the first structured query, each query modification comprising references to one or more modifying nodes from the plurality of second nodes or one or more modifying edges from the plurality of edges; and

sending, to the client system of the first user, one or more of the query modifications as suggested modifications to the first structured query for display to the first user in response to receiving the first structured query, each query modification being selectable by the first user to modify the natural-language string of the first structured query to further comprise references to the one or more modifying nodes or one or more modifying edges referenced in the selected query modification.

2. The method of claim 1, wherein the references to the modifying nodes and the modifying edges are references to additional nodes or additional edges for the first structured query.

3. The method of claim 1, wherein the references to the modifying nodes and the modifying edges are references to alternative nodes or alternative edges for the first structured query, each reference to an alternative node replacing a reference to a selected node of the first structured query, each reference to an alternative edge replacing a reference to a selected edge of the first structured query.

4. The method of claim 1, further comprising:

determining a score for each query modification; and

transmitting one or more of the query modifications having a score greater than a threshold score to the first user.

5. The method of claim 4, wherein determining the score for each query modification is based on a search history associated with the first user.

6. The method of claim 4, wherein determining the score for each query modification is based on a social relevance of the query modification to the first structured query.

7. The method of claim 4, wherein determining the score for each query modification is based on a number of possible search results corresponding to the query modification.

8. The method of claim 1, further comprising generating one or more search results corresponding to the first structured query, wherein each search result corresponds to a second node of the plurality of second nodes that is connected to at least one of the selected nodes by at least one of the selected edges.

9. The method of claim 8, wherein each search result comprises one or more snippets, each snippet comprising contextual information about the second node corresponding to the search result.

10. The method of claim 8, wherein each search result comprises a query modification for the first structured query comprising a reference to the second node corresponding to the search result.

11. The method of claim 8, wherein each search result comprises a second structured query comprising a reference to the second node corresponding to the search result.

12. The method of claim 8, further comprising transmitting one or more of the search results to the first user.

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

generating one or more second structured queries comprising references to zero or more selected nodes and zero or more selected edges from the first structured query, each second structured query comprising at least one fewer reference to the selected nodes or the selected edges than the first structured query; and

transmitting the one or more second structured queries to the first user.

14. The method of claim 1, further comprising:

generating one or more second structured queries based on the first structured query; and

transmitting the one or more second structured queries to the first user.

15. The method of claim 1, wherein generating the one or more query modifications for the first structured query comprises:

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 query tokens corresponding to each of the selected nodes and selected edges referenced in the first structured query and at least one additional query token or alternate query token; and

generating one or more query modifications corresponding to one or more of the additional query tokens or one or more of the alternate query tokens from the identified grammars.

16. The method of claim 1, further comprising:

receiving a selection of one or more of the query modification from the first user; and

generating a second structured query comprising references to the selected nodes, the selected edges, and each additional node or additional edge referenced in the selected query modifications.

17. 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 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 a client system of the first user, a first structured query comprising a natural-language string generated by a grammar model and references to one or more selected nodes from the plurality of second nodes and one or more selected edges from the plurality of edges;

generate one or more query modifications for the first structured query, each query modification comprising references to one or more modifying nodes from the plurality of second nodes or one or more modifying edges from the plurality of edges; and

sending, to the client system of the first user, one or more of the query modifications as suggested modifications to the first structured query for display to the first user in response to receiving the first structured query, each query modification being selectable by the first user to modify the natural-language string of the first structured query to further comprise references to the one or more modifying nodes or one or more modifying edges referenced in the selected query modification.

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;

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 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 a client system of the first user, a first structured query comprising a natural-language string generated by a grammar model and references to one or more selected nodes from the plurality of second nodes and one or more selected edges from the plurality of edges;

generate one or more query modifications for the first structured query, each query modification comprising references to one or more modifying nodes from the plurality of second nodes or one or more modifying edges from the plurality of edges; and

send, to the client system of the first user, one or more of the query modifications as suggested modifications to the first structured query for display to the first user in response to receiving the first structured query, each query modification being selectable by the first user to modify the natural-language string of the first structured query to further comprise references to the one or more modifying nodes or one or more modifying edges referenced in the selected query modification.