Estimating the reach performance of an advertising campaign
A social networking system receives information describing locations associated with a plurality of its users. Based on information identifying each user and a location associated with each user, the social networking system generates and stores hash values. For example, the social networking system maintains various geo-tiles that each identify geographic areas and generates a hash value based on a user identifier and an identifier of a geo-tile including the location associated with the user. Based on the hash values and locations associated with one or more users, the online system determines a number of unique users associated with locations included in a geographic region. When determining the number of unique users, the online system accounts for a rate at which the online system updates location information associated with various users.
1. A method comprising:
receiving, at an online system, information regarding a plurality of locations associated with a user of the online system;
generating cryptographic hash values for the users, each cryptographic hash value based at least in part on a location from the plurality of locations associated with the user and information identifying the user;
storing the generated cryptographic hash values and an association between each of the generated cryptographic hash values and a corresponding location; and
for each location of the plurality of locations:
determining a sampling probability based at least in part on a number of times the online system previously received location information associated with the user, wherein the sampling probability increases as the number of times location information associated with the user received after a time when the online system most recently stored location information associated with the user increases;
determining whether to store the location associated with the user based on the sampling probability; and
responsive to determining to store the location, storing the location at the online system in association with the user.
2. The method of claim 1 , wherein the sampling probability is inversely dependent on a difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user.
3. The method of claim 2 , wherein the sampling probability is equal to one when the difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user equals zero.
4. The method of claim 1 , wherein the sampling probability is based at least in part on an average number of times location information associated with the user is received by the online system during a specified time interval.
5. The method of claim 1 , wherein storing the generated hash values comprises:
storing the generated hash values without an association between the hash values and information identifying the user.
6. The method of claim 1 , wherein storing the location comprises:
storing identification information for a geo-tile containing the location received from the user.
7. A non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:
receive, at an online system, information regarding a plurality of locations associated with a user of the online system;
generate cryptographic hash values for the users, each cryptographic hash value based at least in part on a location from the plurality of locations associated with the user and information identifying the user;
store the generated cryptographic hash values and an association between each of the generated cryptographic hash values and a corresponding location; and
for each location of the plurality of locations:
determine a sampling probability based at least in part on a number of times the online system previously received location information associated with the user, wherein the sampling probability increases as the number of times location information associated with the user received after a time when the online system most recently stored location information associated with the user increases;
determine whether to store the location associated with the user based on the sampling probability; and
responsive to determining to store the location, store the location at the online system in association with the user.
8. The non-transitory computer-readable storage medium of claim 7 , wherein the sampling probability is inversely dependent on a difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user.
9. The non-transitory computer-readable storage medium of claim 8 , wherein the sampling probability is equal to one when the difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user equals zero.
10. The non-transitory computer-readable storage medium of claim 7 , wherein the sampling probability is based at least in part on an average number of times location information associated with the user is received by the online system during a specified time interval.
11. The non-transitory computer-readable storage medium of claim 7 , wherein storing the generated hash values comprises:
storing the generated hash values without an association between the hash values and information identifying the user.
12. The non-transitory computer-readable storage medium of claim 11 , wherein storing the location comprises:
store identification information for a geo-tile containing the location received from the user.
13. A system comprising:
a processor; and
a non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:
receive, at an online system, information regarding a plurality of locations associated with a user of the online system;
generate cryptographic hash values for the users, each cryptographic hash value based at least in part on a location from the plurality of locations associated with the user and information identifying the user;
store the generated cryptographic hash values and an association between each of the generated cryptographic hash values and a corresponding location; and
for each location of the plurality of locations:
determine a sampling probability based at least in part on a number of times the online system previously received location information associated with the user, wherein the sampling probability increases as the number of times location information associated with the user received after a time when the online system most recently stored location information associated with the user increases;
determine whether to store the location associated with the user based on the sampling probability; and
responsive to determining to store the location, store the location at the online system in association with the user.
14. The system of claim 13 , wherein the sampling probability is inversely dependent on a difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user.
15. The system of claim 14 , wherein the sampling probability is equal to one when the difference between an average number of times location information associated with the user is received by the online system during a specified time interval and the number of times location information associated with the user was received after a time when the online system most recently stored location information associated with the user equals zero.
16. The system of claim 13 , wherein the sampling probability is based at least in part on an average number of times location information associated with the user is received by the online system during a specified time interval.
17. The system of claim 13 , wherein storing the generated hash values comprises:
storing the generated hash values without an association between the hash values and information identifying the user.