Online allocation of content items with smooth delivery

• US 10,402,861 B1
• Filed: 04/13/2012
• Issued: 09/03/2019
• Est. Priority Date: 04/15/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Banadaki, Seyed Vahab Mirrokni, Bhalgat, Anand, Feldman, Jon
• Primary Examiner(s): Bekerman, Michael
• Application Number:
  US13/446,901
• Time in Patent Office: 2,699 Days
• Field of Search: 705 1461, 705 1449, 705 1473
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 30/0264 based upon schedule
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

This specification describes technologies relating to displaying online content. In general, one aspect of the subject matter described in this specification can be embodied in methods that include determining a timing penalty for a content item, the timing penalty based in part on weights of previous impressions the content item has been allocated during a plurality of intervals within a delivery period. The methods may further include determining a weight associated with a pairing of the content item and an impression, the weight based in part on characteristics of the impression. The methods may further include determining a score for the content item, based in part on the weight and the timing penalty. The methods may further include selecting one of a set of matching content items, based in part on the score for the content item, and allocating the selected content item in response to a request.

Claims

1. A computer-implemented method performed by a data processing apparatus, the method comprising:

receiving, at a given time, a request for transmission of content, including characteristics of an impression corresponding to the request;

identifying, by one or more processing devices from a first data source over a distributed network, a set of matching content items that are eligible to be served in response to the request;

receiving, from a second data source over the distributed network, weight data indicating weights of previous impressions to which the matching content items have been allocated during a current interval of a delivery period, the current interval comprising the given time at which the request for transmission of the content is received;

for each matching content item, associating, in one or more data records, that matching content item of the set with timing constraint data that constrains transmission of that matching content item, the timing constraint data determined from the weight data received from the second data source over the distributed network;

controlling transmission of the set of matching content items to one or more remote computing systems over the distributed network by performing operations comprising;

for a matching content item in the set;

determining, by the one or more processing devices based on the weight data, a weight associated with a pairing of the matching content item and the impression, the weight further based in part on the characteristics of the impression;

determining, by the one or more processing devices, a timing penalty for the matching content item for the current interval of the delivery period, the delivery period having a delivery goal of a number of impressions to be allocated to the matching content item during the delivery period, the delivery period being divided into a plurality of intervals to smooth allocations of impressions in the delivery goal to the matching content item over the delivery period, each interval having a timing constraint in accordance with timing constraint data associated, in the one or more data records, with that matching content item, with the timing constraint specifying an amount of impressions from the delivery goal allocated to the matching content item during that interval of the delivery period, the timing penalty based in part on weights of previous impressions the matching content item has been allocated during the current interval of the delivery period; and

automatically enforcing the timing constraint for the current interval of the delivery period by automatically updating, by the one or more processing devices, a score for the matching content item, based in part on the weight and the timing penalty of the current interval;

for the current interval of the delivery period and in response to the request,

selecting one of the matching content items, based in part on updated scores for the matching content items; and

allocating the impression to the selected one of the matching content items, including causing presentation of the selected one of the matching content items in response to the request.

2. The method of claim 1, wherein the timing penalty is determined in part by determining an average of the weights of the previous impressions.

3. The method of claim 1, wherein the timing penalty is determined in part by determining a minimum of the weights of the previous impressions.

4. The method of claim 1, wherein the timing penalty is determined in part by determining an exponentially weighted sum of the weights of the previous impressions.

5. The method of claim 1, wherein the timing penalty depends on a subset of the previous impressions.

6. The method of claim 1, wherein determining the timing penalty comprises merging a subset of the previous impressions associated with a previous interval into a subset of previous impressions associated with the current interval.

7. The method of claim 1, wherein at least one of the characteristics of the impression on which the weights are based is a characteristic of a user who requested the impression.

8. The method of claim 1, wherein at least one of the characteristics of the impression on which the weights are based is a time associated with the request.

9. The method of claim 1, wherein the weight for one of the matching content items is a predicted click through rate for that matching content item in the impression.

10. The method of claim 1, wherein the score for the matching content item is determined in part by subtracting the timing penalty for the current interval from the weight.

11. The method of claim 1, wherein the plurality of intervals each has a maximum number of impressions requested.

12. The method of claim 1, wherein the plurality of intervals each has a budget for impressions.

13. A system, comprising:

a server system interface configured to receive, at a given time, a request for transmission of content including characteristics of an impression corresponding to the request;

a module configured to identify receive from a first data source over a distributed network a set of matching content items that are eligible to be served in response to the request;

a module configured to receive, from a second data source over the distributed network, weight data indicating weights of previous impressions to which the matching content items have been allocated during a current interval of a delivery period, the current interval comprising the given time at which the request for transmission of the content is received;

a module configured to, for each matching content item, associating, in one or more data records, that matching content item of the set with timing constraint data that constrains transmission of the matching content item, with timing constraint data determined from the weight data received from the second data source over the distributed network;

controlling transmission of the set of matching content items to one or more remote computing systems over the distributed network by performing operations comprising;

for a matching content item;

a module configured to determine based on the weight data, a weight associated with a pairing of the matching content item and the impression, the weight further based in part on characteristics of the impression;

a module for determining a timing penalty for the matching content item for the current interval of the delivery period, the delivery period having a delivery goal of a number of impressions to be allocated to the matching content item during the delivery period, the delivery period being divided into a plurality of intervals to smooth allocations of impressions in the delivery goal to the matching content item over the delivery period, each interval having a timing constraint in accordance with timing constraint data associated, in the one or more data records, with that matching content item, with the timing constraint specifying an amount of impressions from the delivery goal allocated to the matching content item during that interval of the delivery period, the timing penalty based in part on weights of previous impressions the matching content item has been allocated during the current interval of the delivery period;

a module for automatically enforcing the timing constraint for the current interval of the delivery period by automatically updating, by the one or more processing devices, a score for the matching content item, based in part on the weight and the timing penalty of the current interval;

a module configured to select, for the current interval of the delivery period and in response to the request, one of the matching content items, based in part on updated scores for the matching content items; and

a server system interface configured to allocate, for the current interval of the delivery period, the impression to the selected one of the matching content items, and cause presentation of the selected one of the matching content items in response to the request.

14. The system of claim 13, wherein the timing penalty is determined in part by determining an average of the weights of the previous impressions.

15. The system of claim 13, wherein the timing penalty is determined in part by determining a minimum of the weights of the previous impressions.

16. The system of claim 13, wherein the timing penalty is determined in part by determining an exponentially weighted sum of the weights of the previous impressions.

17. The system of claim 13, wherein determining the timing penalty comprises merging a subset of the previous impressions associated with a previous interval into a subset of previous impressions associated with the current interval.

18. The system of claim 13, wherein the plurality of intervals each has a maximum number of impressions requested.

19. The system of claim 13, wherein the plurality of intervals each has a budget for impressions.

20. One or more non-transitory computer readable media storing instructions that are executable by one or more processing devices to perform operations comprising:

receiving, at a given time, a request for transmission of content, including characteristics of an impression corresponding to the request;

identifying from a first data source over a distributed network, a set of matching content items that are eligible to be served in response to the request;

receiving, from a second data source over the distributed network, weight data indicating weights of previous impressions to which the matching content items have been allocated during a current interval of a delivery period, the current interval comprising the given time at which the request for transmission of the content is received;

for each matching content item, associating, in one or more data records, that matching content item of the set with timing constraint data that constrains transmission of that matching content item, the timing constraint data determined from the weight data received from the second data source over the distributed network;

controlling transmission of the set of matching content items to one or more remote computing systems over the distributed network by performing operations comprising;

for a matching content item in the set;

determining based on the weight data, a weight associated with a pairing of the matching content item and the impression, the weight further based in part on the characteristics of the impression;

determining a timing penalty for the matching content item for the current interval of the delivery period, the delivery period having a delivery goal of a number of impressions to be allocated to the matching content item during the delivery period, the delivery period being divided into a plurality of intervals to smooth allocations of impressions in the delivery goal to the matching content item over the delivery period, each interval having a timing constraint in accordance with timing constraint data associated, in the one or more data records, with that matching content item, with the timing constraint specifying an amount of impressions from the delivery goal allocated to the matching content item during that interval of the delivery period, the timing penalty based in part on weights of previous impressions the matching content item has been allocated during the current interval of the delivery period; and

automatically enforcing the timing constraint for the current interval of the delivery period by automatically updating a score for the matching content item, based in part on the weight and the timing penalty of the current interval;

for the current interval of the delivery period and in response to the request, selecting one of the matching content items, based in part on updated scores for the matching content items; and

allocating the impression to the selected one of the matching content items, including causing presentation of the selected one of the matching content items in response to the request.

21. A system, comprising:

a data processing apparatus; and

a memory coupled to the data processing apparatus having instructions stored thereon which, when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising;

receiving, at a given time, a request for transmission of content, including characteristics of an impression corresponding to the request;

identifying, from a first data source over a distributed network, a set of matching content items that are eligible to be served in response to the request;

receiving, from a second data source over the distributed network, weight data indicating weights of previous impressions to which the matching content items have been allocated during a current interval of a delivery period, the current interval comprising the given time at which the request for transmission of the content is received;

for each matching content item, associating, in one or more data records, that matching content item of the set with timing constraint data that constrains transmission of that matching content item, the timing constraint data determined from the weight data received from the second data source over the distributed network;

controlling transmission of the set of matching content items to one or more remote computing systems over the distributed network by performing operations comprising;

for a matching content item in the set;

determining based on the weight data, a weight associated with a pairing of the matching content item and the impression, the weight further based in part on the characteristics of the impression;

determining a timing penalty for the matching content item for the current interval of the delivery period, the delivery period having a delivery goal of a number of impressions to be allocated to the matching content item during the delivery period, the delivery period being divided into a plurality of intervals to smooth allocations of impressions in the delivery goal to the matching content item over the delivery period, each interval having a timing constraint in accordance with timing constraint data associated, in the one or more data records, with that matching content item, with the timing constraint specifying an amount of impressions from the delivery goal allocated to the matching content item during that interval of the delivery period, the timing penalty based in part on weights of previous impressions the matching content item has been allocated during the current interval of the delivery period; and

automatically enforcing the timing constraint for the current interval of the delivery period by automatically updating a score for the matching content item, based in part on the weight and the timing penalty of the current interval;

for the current interval of the delivery period and in response to the request, selecting one of the matching content items, based in part on updated scores for the matching content items; and

allocating the impression to the selected one of the matching content items, including causing presentation of the selected one of the matching content items in response to the request.

22. The system of claim 21, wherein the timing penalty is determined in part by determining an average of the weights of the previous impressions.

23. The system of claim 21, wherein the timing penalty is determined in part by determining a minimum of the weights of the previous impressions.

24. The system of claim 21, wherein the timing penalty is determined in part by determining an exponentially weighted sum of the weights of the previous impressions.

25. The system of claim 21, wherein determining the timing penalty comprises merging a subset of the previous impressions associated with a previous interval into a subset of previous impressions associated with the current interval.

26. The system of claim 21, wherein the plurality of intervals each has a maximum number of impressions requested.

27. The system of claim 21, wherein the plurality of intervals each has a budget for impressions.