IP Library › Granted Patent US 10,366,406
Granted Patent B2
US 10,366,406 · App. 14/563,858 · Granted Jul 30, 2019

Estimating the reach performance of an advertising campaign

Inventors: Charles Joseph Hughes (San Francisco, CA); Xiao Zhang (Mountain View, CA); Patrick Brendan Maginnis (San Francisco, CA)
Assignee: Facebook, Inc.
G06Q30/0246G06Q30/0205H04L67/02H04L67/125H04L67/18H04L67/20H04L67/22H04L67/306
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,366,406
App. No.
14/563,858
Granted
Jul 30, 2019
Kind
B2
Abstract

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.

Claims (60)

1. A method comprising:

receiving information describing locations of a plurality of users;

updating locations associated with each of the plurality of users based on the received information;

generating cryptographic hash values for each of the plurality of users, a hash value for a user based at least in part on received information describing a location of the user and information identifying the user;

storing the generated hash values and an association between the generated hash value and a corresponding location;

identifying a geographic region including a set of geo-tiles, each geo-tile identifying a portion of the geographic region;

determining a set of distinct users based at least in part on the generated hash values, each distinct user having a location within a geo-tile included in the identified geographic region;

determining an average sampling rate for the set of geo-tiles based at least in part on a number of hash values associated with locations within each of the geo-tiles in the set of geo-tiles and a number of distinct users associated with locations within each of the geo-tiles in the set of geo-tiles; and

determining an estimated number of users associated with locations within the identified geographic region based on a number of users in the set of distinct users and the determined average sampling rate for the set of geo-tiles.

2. The method of claim 1 , wherein determining the average sampling rate for the set of geo-tiles comprises:

determining a sampling rate for each a plurality of subsets of geo-tiles of the set of geo-tiles included in the geographic region; and

determining the average sampling rate for the set of geo-tiles based on the sampling rates for each of the plurality of subsets of geo-tiles.

3. The method of claim 1 , wherein determining the average sampling rate for the set of geo-tiles comprises:

determining a number of geo-tiles in the set of geo-tiles included in the geographic region;

determining a geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles;

determining a set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region; and

determining an average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region.

4. The method of claim 3 , wherein determining the average sampling rate for the set of geo-tiles further comprises:

determining an additional geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles;

determining an additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region;

determining an additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region; and

determining the average sampling rate based on the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region.

5. The method of claim 4 , wherein determining the average sampling rate based on the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region comprises:

associating weights with the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region based at least in part on the number of geo-tiles in the set of geo-tiles included in the geographic region; and

determining the average sampling rate based at least in part on the weights.

6. The method of claim 4 , wherein determining the geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles comprises:

determining a resolution of the geo-tiles in the set of geo-tiles;

determining a value based on the number of geo-tiles in the set of geo-tiles included in the geographic region; and

determining the geo-tile resolution based on the resolution of the geo-tile in the set of geo-tiles and the determined value.

7. The method of claim 6 , wherein determining the geo-tile resolution based on the resolution of the geo-tile in the set of geo-tiles and the determined value comprises:

determining the geo-tile resolution as a difference between the resolution of the geo-tiles in the set of geo-tiles and the determined value.

8. The method of claim 6 , wherein determining the additional geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles comprises:

determining an alternative value based on the a number of geo-tiles in the set of geo-tiles included in the geographic region; and

determining the additional geo-tile resolution based on the resolution of the geo-tile in the set of geo-tiles and the alternative value.

9. The method of claim 8 , wherein determining the additional geo-tile resolution based on the resolution of the geo-tiles in the set of geo-tiles and the alternative value comprises:

determining the additional geo-tile resolution as a difference between the resolution of the geo-tiles in the set of geo-tiles and the alternative value.

10. The method of claim 9 , wherein the determined value comprises an integer value less than a logarithm of the number of determined number of geo-tiles in the set of geo-tiles and wherein the alternative value comprises an integer value greater than the logarithm of the number of determined number of geo-tiles in the set of geo-tiles.

11. The method of claim 1 , wherein the estimated number of users associated with locations within the identified geographic region is a product of the number of users in the set of distinct users and the determined average sampling rate for the set of geo-tiles.

12. A non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:

receive information describing locations of a plurality of users;

update locations associated with each of the plurality of users based on the received information;

generate cryptographic hash values for each of the plurality of users, a hash value for a user based at least in part on received information describing a location of the user and information identifying the user;

store the generated hash values and an association between the generated hash value and a corresponding location;

identify a geographic region including a set of geo-tiles, each geo-tile identifying a portion of the geographic region;

determine a set of distinct users based at least in part on the generated hash values, each distinct user having a location within a geo-tile included in the identified geographic region;

determine an average sampling rate for the set of geo-tiles based at least in part on a number of hash values associated with locations within each of the geo-tiles in the set of geo-tiles and a number of distinct users associated with a location within each of the geo-tiles in the set of geo-tiles; and

determine an estimated number of users associated with locations within the identified geographic region based on a number of users in the set of distinct users and the determined average sampling rate for the set of geo-tiles.

13. The non-transitory computer-readable storage medium of claim 12 , wherein the estimated number of users associated with locations within the identified geographic region is a product of the number of users in the set of distinct users and the determined average sampling rate for the set of geo-tiles.

14. The non-transitory computer-readable storage medium of claim 12 , wherein determine the average sampling rate for the set of geo-tiles comprises:

determine a number of geo-tiles in the set of geo-tiles included in the geographic region;

determine a geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles;

determine an additional geo-tile resolution based on the determined number of geo-tiles in the set of geo-tiles;

determine a set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region;

determine an additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region;

determine an average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region;

determine an additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region; and

determine the average sampling rate based on the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region.

15. The non-transitory computer-readable storage medium of claim 14 , wherein determine the average sampling rate based on the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region comprises:

associate weights with the average sampling rate for the set of geo-tiles having the determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region and the additional average sampling rate for the additional set of geo-tiles having the additional determined geo-tile resolution and including the geo-tiles in the set of geo-tiles included in the geographic region based at least in part on the number of geo-tiles in the set of geo-tiles included in the geographic region; and

determine the average sampling rate based at least in part on the weights.

Assignments (2)
CHANGE OF NAME Recorded Nov 18, 2021
From: FACEBOOK, INC.
To: META PLATFORMS, INC.
Reel/Frame 058897/0824 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2015
From: HUGHES, CHARLES JOSEPH; ZHANG, XIAO; MAGINNIS, PATRICK BRENDAN
To: FACEBOOK, INC.
Reel/Frame 035798/0366 →
Continuity (1)
Related Publication 20160162932A1 · Jun 9, 2016