Network-based systems and methods for defining and managing multi-dimensional, advertising impression inventory
View Patent ↗A method for representing and managing an inventory of overlapping multi-dimensional items such as advertising or ad impressions. The method uses an inventory management module to generate unique segment identifiers for sets of inventory items by processing descriptions of the sets of impressions including defining criteria. The method includes processing the unique segment identifiers to create a representation of the inventory as a plurality of inventory regions, which may include non-overlapping regions that correspond to inventory items in a single set of the inventory and also include overlapping regions that correspond to inventory items in two or more of the sets (e.g., items that match two or more sets of defining criteria or attributes). Availability and selection of inventory is determined using the information on inventory regions to control effects of cannibalization, such as by implementing logically necessary allocation to only cannibalize a region on a limited or forced basis.
1. A system for managing ad impression product inventory, comprising:
a data store storing a plurality of aggregated forecast vectors, wherein each of the aggregated forecast vectors comprises
a product vector identifier representing a discrete region of the ad impression product inventory, and a corresponding ad impression product inventory count over a time period;
each discrete region being defined as overlapping and non-overlapping portions of two or more segments of the ad impression product inventory with each of the segments including ad impression products that are characterized by a set of attributes; and
a processor configured for allocating from one or more of the regions a requested number of the ad impressions products for one or more of the segments by processing the product vector identifier and the ad impression product inventory count for each of the regions to control cannibalization of the ad impressions products globally in all of the regions of the ad impression product inventory;
the processor further configured for representing ad impression product constraint relationships in order of increasing cardinality using a traversal structure of a DAG (directed acyclic graph) on a subset of nodes in the DAG for the ad impression product being allocated to order the traversal by implementing a lowest cardinality assignment method for determining ad impression product availability in each region as a count of said ad impression product associated with each said region, including ordering the regions in ascending cardinality order and allocating ad impression product inventory from the ad impressions products for the requested number to the regions of the ad impression product inventory in ascending cardinality order, as necessary dividing the allocation of inventory across regions of the same cardinality by choosing a region that is least constrained, allocating all inventory for a current ad impression product, computing a base inventory availability by summing unallocated inventory for each ad impression product, for each advertising ad impression product creating a list of all ad impression products that have allocated inventory on its regions and an amount allocated to each ad impression product, for each cannibalizing ad impression product looking at said product's inventory regions to determine if it has any free inventory that can be exchanged for the inventory that it is currently holding of a current ad impression product, adding this inventory to the count of inventory for the current product if there is enough inventory, applying this process recursively to the cannibalizing product's neighbors if the current product does not have enough inventory, and continuing until all needed inventory has been allocated to produce a lowest consumption on remaining ad impression products when taken globally.
2. The system of claim 1 , further comprising:
said processor configured for implementing a greedy algorithm to allocate inventory to each ad impression product in turn by allocating inventory to the region of inventory in order of ascending cardinality, once a product processing order is established.