Approximate privacy indexing for search queries on online social networks

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

retrieving, from one or more data stores, one or more objects requested by an application accessed by a first user of an online social network, wherein each object is associated with a privacy setting, and wherein a percentage of the retrieved objects have a privacy setting likely to make the object visible to the first user;

determining, for each retrieved object, a visibility of the object with respect to the first user; and

sending, to the application accessed by the first user, one or more of the retrieved objects, wherein each sent object has a visibility that is visible to the first user, and wherein objects having a visibility that is not visible to the first user are not sent.

2. The method of claim 1 , further comprising:

receiving, via the application accessed by the first user, a search query from a first user of the online social network;

searching the one or more data stores to identify one or more objects that substantially match the search query, wherein the retrieved objects are selected from the identified objects; and

generating one or more search results corresponding to the search query, wherein each search result corresponds to one of the retrieved objects having visibility that is visible to the first user, wherein sending one or more of the retrieved objects comprises sending one or more of the search results.

3. The method of claim 2 , further comprising generating a query command based on the search query, the query command comprising one or more query constraints, wherein:

the query command comprises a privacy query constraint requesting objects having a first privacy setting; and

searching the one or more data stores to identify one or more objects that substantially match the search query comprises determining whether the privacy setting of the object matches the first privacy setting.

4. The method of claim 1 , further comprising filtering each object that is not visible to the first user from the sent objects.

5. The method of claim 1 , further comprising scoring each retrieved object based on the privacy setting associated with the object.

6. The method of claim 1 , further comprising scoring each retrieved object based on a social-graph affinity associated with the first user with respect to the identified object.

7. The method of claim 1 , wherein the privacy setting defines a visibility of the object with respect to users accessing the online social network.

8. The method of claim 1 , wherein retrieving the one or more objects comprises determining whether the privacy setting of the object is likely to make the object visible to the first user.

9. The method of claim 1 , wherein retrieving the one or more objects comprises identifying a first percentage of objects having a privacy setting likely to make the object visible to the first user.

10. 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, wherein each node of the plurality of nodes corresponds to a particular object, 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.

11. The method of claim 10 , wherein each retrieve object corresponds to a second node within a threshold degree of separation of the first node.

12. The method of claim 10 , wherein determining, for each retrieved object, a visibility of the object with respect to the first user comprises, for each retrieved object:

identifying a second node of the plurality of second nodes corresponding to the identified object; and

determining whether the identified node is connected to the first node in the social graph by a series of nodes and edges that each have a visibility that is visible to the first user.

13. The method of claim 10 , wherein determining, for each retrieved object, a visibility of the object with respect to the first user comprises, for each retrieved object:

identifying a second node of the plurality of second nodes corresponding to the identified object; and

determining whether the identified node is within a threshold degree of separation from the first node in the social graph.

14. The method of claim 10 , wherein the privacy setting associated with each object defines a visibility of the node corresponding to the object or a visibility of one or more of the edges connected to the node corresponding to the object.

15. The method of claim 1 , wherein the sent objects are presented to the first user as part of a newsfeed of the first user.

16. The method of claim 1 , wherein the sent objects are presented to the first user as part of a content stream.

17. The method of claim 1 , wherein the sent objects are presented to the first user as part of a search-results page.

18. The method of claim 1 , wherein the sent objects are presented to the first user as part of a push notification pushed to client system of the first user.

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

retrieve, from one or more data stores, one or more objects requested by an application accessed by a first user of an online social network, wherein each object is associated with a privacy setting, and wherein a percentage of the retrieved objects have a privacy setting likely to make the object visible to the first user;

determine, for each retrieved object, a visibility of the object with respect to the first user; and

send, to the application accessed by the first user, one or more of the retrieved objects, wherein each sent object has a visibility that is visible to the first user, and wherein objects having a visibility that is not visible to the first user are not sent.

20. 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:

retrieve, from one or more data stores, one or more objects requested by an application accessed by a first user of an online social network, wherein each object is associated with a privacy setting, and wherein a percentage of the retrieved objects have a privacy setting likely to make the object visible to the first user;

determine, for each retrieved object, a visibility of the object with respect to the first user; and

send, to the application accessed by the first user, one or more of the retrieved objects, wherein each sent object has a visibility that is visible to the first user, and wherein objects having a visibility that is not visible to the first user are not sent.