Calculating flight plans for reservation-based ad serving

• US 9,053,492 B1
• Filed: 10/19/2006
• Issued: 06/09/2015
• Est. Priority Date: 10/19/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Aggarwal, Gagan, Manku, Gurmeet Singh, Agarwal, Anurag, Chamberlain, Dawn, Jain, Gaurav, Stanley, Barbara
• Primary Examiner(s): Reagan, James A
• Application Number:
  US11/551,151
• Time in Patent Office: 3,155 Days
• Field of Search: 705/1, 705/14
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/0224 based on user history

Abstract

The disclosure provides various embodiments of systems, methods, and software for supporting server-side product catalogs. Software for managing ad serving may comprise computer readable instructions embodied on media and be operable to identify a logically local directed graph representing a logically remote network property associated with a publisher. The network property is associated with at least one product catalog representing a package of network ad slots. The software may then generate an ad service flight plan for serving various ones of a plurality of ads associated with a first of the network ad slots using an iterative solution on the directed graph.

Claims

1. A computer-readable hardware storage device encoded with a computer program product for managing network ad availability, the computer program product comprising computer readable instructions that, when executed by one or more processors of an ad server, cause the one or more processors to:

generate, by the ad server, a directed graph representing a network property associated with a publisher, the network property associated with at least one product catalog representing a package of network ad slots, the directed graph including nodes representing sub-placements corresponding to various characteristic constraints of the network property and nodes representing sub-slots for network ad slots included in the sub-placements;

determine, by the ad server, a flow through the directed graph, with the flow being determined in accordance with one or more of (i) the characteristic constraints, (ii) a reservation impression constraint that specifies a number of impressions requested by an advertiser, (iii) a forecasted impression constraint that restricts a number of forecasted impressions assigned to the sub-slots, or (iv) an objective for the sub-slots;

wherein the flow is associated with a particular period of time in which ads are assigned to a plurality of forecasted impressions for a first of the network ad slots;

assign, by the ad server based on the determined flow, the ads to the plurality of forecasted impressions for the particular period of time;

generate, by the ad server based on assignment of the ads to the plurality of forecasted impressions, an ad service plan for serving various ones of the ads associated with the first of the network ad slots, wherein the ad service plan is a plan that specifies which ads will be served in each of the plurality of forecasted impressions for the first of the network ad slots during the particular period of time; and

cache the ad service plan prior to receipt of an ad request from the publisher for delivery of at least one of the ads associated with the first of the network ad slots.

2. The computer-readable hardware storage device of claim 1 further operable to communicate a particular ad to the publisher for service at the network property in response to the ad request from the publisher and based on the generated ad service plan.

3. The computer-readable hardware storage device of claim 2, the ad service plan associating a priority with each of the ads.

4. The computer-readable hardware storage device of claim 2 further operable to cache the ad service plan in a local cache, whereby response time to the ad request is decreased.

5. The computer-readable hardware storage device of claim 1 further operable to execute a smoothing process on the generated ad service plan.

6. The computer-readable hardware storage device of claim 5 further operable to generate an availability result for the network property in response to an availability query, the availability result substantially similar to the generated ad service plan.

7. The computer-readable hardware storage device of claim 6, further operable to receive the availability query from a portal operable to be accessed by a plurality of authorized publishers.

8. The computer-readable hardware storage device of claim 1 further operable to:

collect product catalog information about the network property, the product catalog information comprising a product catalog identifier, at least one placement identifier, and at least two ad slot identifiers; and

use the collected information when generating the directed graph.

9. An ad server for managing ad serving comprising:

one or more processors operable to;

generate, by the one or more processors, a directed graph representing a network property associated with a publisher, the network property associated with at least one product catalog representing a package of network ad slots, the directed graph including nodes representing sub-placements corresponding to various characteristic constraints of the network property and nodes representing sub-slots for network ad slots included in the sub-placements;

determine, by the one or more processors, a flow through the directed graph, with the flow being determined in accordance with one or more of (i) the characteristic constraints, (ii) a reservation impression constraint that specifies a number of impressions requested by an advertiser, (iii) a forecasted impression constraint that restricts a number of forecasted impressions assigned to the sub-slots, or (iv) an objective for the sub-slots;

wherein the flow is associated with a particular period of time in which ads are assigned to a plurality of forecasted impressions for a first of the network ad slots;

assign, by the one or more processors based the determined flow, the ads to the plurality of forecasted impressions for the particular period of time;

generate, by the one or more processors based on assignment of the ads to the plurality of forecasted impressions, an ad service plan for serving various ones of the ads associated with the first of the network ad slots, wherein the ad service plan is a plan that specifies which ads will be served in each of the plurality of forecasted impressions for the first of the network ad slots during the particular period of time; and

cache the ad service plan prior to receipt of an ad request from the publisher for delivery of at least one of the ads associated with the first of the network ad slots.

10. The ad server of claim 9, the one or more processors further operable to communicate a particular ad to the publisher for service at the network property in response to the ad request from the publisher and based on the generated ad service plan.

11. The ad server of claim 10, the ad service plan associating a priority with each of the ads.

12. The ad server of claim 10, the one or more processors further operable to cache the ad service plan in a local cache, whereby response time to the ad request is decreased.

13. The ad server of claim 9, the one or more processors further operable to execute a smoothing process on the generated ad service plan.

14. The ad server of claim 13, the one or more processors further operable to generate an availability result for the network property in response to an availability query, the availability result substantially similar to the generated ad service plan.

15. The ad server of claim 14, wherein the one or more processors are operable to receive the availability query from a portal operable to be accessed by a plurality of authorized publishers.

16. The ad server of claim 9, the one or more processors further operable to:

collect product catalog information about the network property, the product catalog information comprising a product catalog identifier, at least one placement identifier, and at least two ad slot identifiers; and

use the collected information when generating the directed graph.

17. The ad server of claim 9, wherein the iterative processing includes initializing the graph based, at least in part, on a number of forecasted impressions and a number of reserved impressions for sub-slots of the first ad slot.

18. The ad server of claim 9, wherein the ad service plan does not specify an advertisement for at least one forecasted impression for the first ad slot during the period of time.

19. The ad server of claim 9, wherein:

the graph further comprises a source node, a sink node, a respective edge between the source node and each node representing a sub placement, edges between the nodes representing the sub placements and nodes representing the sub slots, and a respective edge between the sink node and each node representing a sub slot; and

the iterative process determines a flow through the graph from the source node to the sink node.

20. The ad server of claim 19, wherein the one or more processors are further operable to:

initialize an edge weight for each edge between each node representing a sub slot and the sink node to be a forecasted number of impressions for the sub slot; and

initialize an edge weight for each edge between the source node and each node representing a sub placement to be a number of reserved impressions for the sub placement.

21. The ad server of claim 9, wherein determining a flow through the graph comprises determining a maximal flow through the graph.

22. A computer-implemented method for managing ad serving, the method comprising:

generating, by an ad server, a directed graph representing a network property associated with a publisher, the network property associated with at least one product catalog representing a package of network ad slots, the directed graph including nodes representing sub-placements corresponding to various characteristic constraints of the network property and nodes representing sub-slots for network ad slots included in the sub-placements;

determining, by one or more processors, a flow through the directed graph, with the flow being determined in accordance with one or more of (i) the characteristic constraints, (ii) a reservation impression constraint that specifies a number of impressions requested by an advertiser, (iii) a forecasted impression constraint that restricts a number of forecasted impressions assigned to the sub-slots, or (iv) an objective for the sub-slots;

wherein the flow is associated with a particular period of time in which ads are assigned to a plurality of forecasted impressions for a first of the network ad slots;

assigning, by the one or more processors based on the determined flow, the ads to the plurality of forecasted impressions for the particular period of time;

generating, by the ad server based on assignment of the ads to the plurality of forecasted impressions, an ad service plan for serving various ones of the ads associated with the first of the network ad slots, wherein the ad service plan is a plan that specifies which ads will be served in each of the plurality of forecasted impressions for the first of the network ad slots during the particular period of time; and

caching the ad service plan prior to receipt of an ad request from the publisher for delivery of at least one of the ads associated with the first of the network ad slots.