Filtering structured search queries based on privacy settings

• US 10,140,338 B2
• Filed: 11/23/2015
• Issued: 11/27/2018
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lee, Yofay Kari, Cohen, Michael Benjamin, Boucher, Maxime, Azzolini, Alisson Gusatti, Li, Xiao, Rasmussen, Lars Eilstrup, Curtiss, Michael, Mishra, Chaitanya
• Primary Examiner(s): Burke, Jeffrey A
• Assistant Examiner(s): Vu, Thong
• Application Number:
  US14/949,345
• Publication Number:
  US 20160078096A1
• Time in Patent Office: 1,100 Days
• Field of Search: 707769, 707722, 707723, 707749, 709203
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: H04L 63/105 Multiple levels of security

Abstract

In particular embodiments, a method includes receiving an unstructured text query, identifying nodes and edges from a social graph that correspond to n-grams in the text query, generating structured queries that include references to the identified nodes and edges, receiving a selection of a structured query, identifying target nodes that correspond to the structured query, and then generating search results that include target nodes with privacy settings where the nodes and edges along the path connecting the target node and the querying user are all visible to the user.

Claims

1. A method comprising, by one or more computing devices:

accessing, by the one or more computing devices, 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-user 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, wherein each second node is associated with a privacy setting defining a visibility of each edge connected to the second node;

receiving, from a client system of the first user at the one or more computing devices, a structured query selected by the first user, wherein the structured query comprises references to one or more selected nodes from the one or more second nodes and one or more selected edges from the plurality of edges;

identifying, by the one or more computing devices, a set of target nodes corresponding to the structured query, wherein each target node in the set is a second node from the plurality of second nodes that is connected to at least one of the selected nodes by at least one of the selected edges;

filtering, by the one or more computing devices, the set of target nodes based on the privacy setting of each of the selected edges connecting each target node in the set to the selected nodes; and

generating, by the one or more computing devices, search results comprising references to each target node from the post-filtered set that is connected to the first-user node in the social graph by a series of selected nodes and selected edges that have a visibility that is visible to the first user, and wherein each target node is within a threshold degree of separation from the first-user node.

2. The method of claim 1, further comprising:

receiving from the first user a substantially unstructured text query comprising one or more n-grams;

identifying one or more of the second nodes, each of the identified second nodes corresponding to one or more of the n-grams;

identifying one or more of the edges, each of the identified edges being connected to at least one of the identified second nodes, each of the identified edges corresponding to one or more of the n-grams; and

generating one or more structured queries that each comprise references to one or more of the identified second nodes and one or more of the identified edges.

3. The method of claim 2, further comprising sending one or more of the structured queries for presentation to the first user.

4. The method of claim 3, further comprising presenting the one or more sent structured queries to the first user, wherein, for each sent structured query, one or more of the references of the sent structured query is highlighted as presented to indicate the reference corresponds to an identified node or an identified edge.

5. The method of claim 2, further comprising receiving from the first user a selection of one of the structured queries.

6. The method of claim 2, wherein receiving from the first user the unstructured text query comprises receiving one or more characters of a character string as the first user at a client device enters the character string into a user interface comprising a query field, and wherein the character string is entered by the first user into the query field.

7. The method of claim 6, wherein the user interface is displayed on an interface of a native application associated with the online social network.

8. The method of claim 6, wherein the user interface is displayed on a webpage associated with the online social network accessed by a browser client.

9. The method of claim 1, wherein the structured query comprises a first condition and one or more second conditions, wherein at least one of the second conditions is dependent on the first condition, and wherein identifying a set of target nodes corresponding to the structured query comprises identifying one or more second nodes that satisfy the first condition and applying the second nodes that satisfy the first condition to each second condition that is dependent on the first condition.

10. The method of claim 1, further comprising, for each target node in the set, generating a sub-graph comprising the first-user node, the target node, and each selected node and each selected edge connecting the first-user node and the target node in the social graph.

11. The method of claim 10, further comprising, for each sub-graph, identifying each terminal path in the sub-graph connecting the first-user node to the target node, each terminal path comprising a series of selected nodes and selected edges connecting the first-user node to the target node.

12. The method of claim 11, further comprising, for each terminal path in the sub-graph, determining whether each selected edge in the terminal path has a visibility that is visible to the first user.

13. The method of claim 11, wherein generating search results comprises:

identifying each sub-graph having at least one terminal path wherein each selected edge in the path has a visibility that is visible to the first user; and

generating search results comprising references to each target node from the post-filtered set and corresponding to each identified sub-graph.

14. The method of claim 1, wherein the privacy settings for each second node further define a visibility of the second node.

15. The method of claim 1, wherein the threshold degree of separation is one, two, three, or all.

16. The method of claim 1, wherein the structured query is received from a third-party system via a call through an application programming interface associated with the online social network.

17. The method of claim 1, wherein the structured query is received from a third-party system via a communication channel associated with the online social network.

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-user 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, wherein each second node is associated with a privacy setting defining a visibility of each edge connected to the second node;

receive, from a client system of the first user, a structured query selected by the first user, wherein the structured query comprises references to one or more selected nodes from the one or more second nodes and one or more selected edges from the plurality of edges;

identify a set of target nodes corresponding to the structured query, wherein each target node in the set is a second node from the plurality of second nodes that is connected to at least one of the selected nodes by at least one of the selected edges;

filter the set of target nodes based on the privacy setting of each of the selected edges connecting each target node in the set to the selected nodes; and

generate search results comprising references to each target node from the post-filtered set that is connected to the first-user node in the social graph by a series of selected nodes and selected edges that have a visibility that is visible to the first user, and wherein each target node is within a threshold degree of separation from the first-user node.

19. 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-user 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, wherein each second node is associated with a privacy setting defining a visibility of each edge connected to the second node;

receive, from a client system of the first user, a structured query comprising references to one or more selected nodes from the one or more second nodes and one or more selected edges from the plurality of edges;

identify a set of target nodes corresponding to the structured query, wherein each target node in the set is a second node from the plurality of second nodes that is connected to at least one of the selected nodes by at least one of the selected edges;

filter the set of target nodes based on the privacy setting of each of the selected edges connecting each target node in the set to the selected nodes; and

generate search results comprising references to each target node from the post-filtered set that is connected to the first-user node in the social graph by a series of selected nodes and selected edges that have a visibility that is visible to the first user, and wherein each target node is within a threshold degree of separation from the first-user node.