Patent ID: 8392248

Claim:
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.