Estimating the reach performance of an advertising campaign

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.

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.