WO2001001318A2 - Media planning and scheduling over a computer network - Google Patents

Abstract

In one embodiment, access is authorized to a database comprising demographic data concerning network users. The database provides a complete inventory of impressions that can be supplied to users. A sample database is created to reflect the complete inventory. The sample database is smaller than the inventory database. A request is received to access an available part of the complete inventory, the request specifying at least one of the demographic characteristics. A proportion of the sample database is determined. The proportion of the sample database has the same demographic characteristics as the query. The available inventory is approximated based on the proportion of the database with demographic characteristics.

Description

MEDIA PLANNING AND SCHEDULING OVER A COMPUTER

NETWORK

BACKGROUND OF THE INVENTION

Field of the Invention This invention relates to the field of advertising management systems over networks. In particular, the invention relates to predictive media planning and scheduling over a network such as the Internet.

SUMMARY OF THE INVENTION

An embodiment of the invention includes a method or system for planning and scheduling advertisement media over a network. In an embodiment, access is provides to a database comprising demographic information about users on the network. The database indicates a total inventory of impressions that are deliverable to the users. A sample database is created to reflect the total inventory. The sample database is smaller than the inventory database. A request is received for an available portion of the total inventory, the request specifying at least one of the demographic characteristics. A proportion of the sample database is determined. The proportion of the sample database has the same demographic characteristic as the request. The available inventory is approximated from the proportion of the sample database having the demographic characteristic.

In a variation, a request is received for an available portion of the total inventory. A first characteristic is identified from the request that corresponds to a genus of the total inventory. A second characteristic is also identified from the request that corresponds to a category of the genus. A proportion of the sample database is determined using a set of the sample database defined by the genus, and a portion of the subset defined by the category. The available inventory is approximated using the proportion of the sample database determined by the portion of the set defined by the category. In another embodiment, a method and system is provided for planning and scheduling advertisement media over a network coupleable to a plurality of terminals. A total inventory is forecasted over the network. The total inventory is for impressions that are available over the network. In an embodiment, total inventory corresponds to a summation of a number of impressions that are deliverable to each terminal coupleable to the network during a designated time period. A sample inventory is created that reflects the total inventory and is smaller than the total inventory. The sample inventory is used to predict a target inventory identified by a category of the total inventory of impressions. In another embodiment, a method and system is provided that supplies demographic information about users of a network system to suppliers of media for the network system. A true database is developed that comprises the demographic information about the users of the network system. The demographic information includes a plurality of categories. A sample database that is representative of the true database is identified. A query is received for an available inventory of impressions that are deliverable to a specified group of the users over a designated time period. The available inventory is approximated over the designated time period using the sample database. Another embodiment provides a method and system for planning advertisement campaigns for a network that is coupleable to a plurality of terminals. The method includes accessing a true inventory comprising a plurality of demographic profiles about users of the terminals. User-profiles are selected from the true database to form a sample database. The sample database is representative of the true database, so that the sample database contains roughly the same proportion of user-profiles in the true database, as well as user-profiles in groups that sort the true database. A total inventory is approximated, where the total inventory reflects all of the demographic profiles in the true inventory. The demographic profiles are sorted according to a genus and/or a category. The sample inventory is used to approximate a portion of the total inventory available for an advertisement campaign directed to the at least one of the genus or the category of the genus. Another embodiment includes a method and system for planning advertisement campaigns for a network coupleable to a plurality of terminals. A total inventory is forecasted for a designated period, where the total inventory includes a plurality of impressions that are deliverable to a plurality of users, and where the total inventory is grouped according to one or more demographic characteristics of the users. A sample inventory is created that reflects the total inventory and is smaller than the total inventory. A first request is received for an available inventory. The first request specifies one or more characteristics. A proportion is of the sample inventory is identified having the characteristic of the first request. The proportion identified in the sample inventory is applied to the total inventory to approximate the available inventory for the first request. The total inventory is reduced for a subsequent request by the available inventory for the first request.

In one embodiment, the total inventory is sorted into a plurality of groups, where each group includes a portion of the inventory defined by one or more characteristics.

In another embodiment, before receiving the first request, an existing inventory of each of the plurality of groups is approximated by identifying a proportion of the sample database having the characteristic of that group, and applying the proportion identified for each group to the total inventory to determine an existing inventory for each of the plurality of groups.

In a variation, subsequent to receiving the first request, a new inventory is approximated for each of the plurality of groups using the proportion identified for that group in the sample inventory, and applying the proportion to the reduced total inventory to approximate a new inventory for each group. In another variation, for each subsequent request; (a) a portion of the sample database having the characteristic of that request is identified; (b) the available inventory is approximated for that request from the portion of the sample database having the characteristics of that request; and (c) the total inventory request is reduced by the available inventory for that request.

In another embodiment, a method and system is included for planning advertisement campaigns for a network coupleable to a plurality of terminal. The embodiment includes forecasting a total inventory for a designated period, where the total inventory includes a plurality of impressions that are deliverable to a plurality of users, and where the total inventory being is according to one or more demographic characteristics of the users. The embodiment includes creating a sample inventory to represent the total inventory, and receiving a plurality of requests for available inventory, where the plurality of requests specifying one or more characteristics. The embodiment further includes arranging the plurality of requests into a sequential order. For each request arranged in the sequential order, the embodiment includes (a) identifying a portion of the sample inventory having the characteristics of that request; (b) approximating the available inventory for that request from the portion of the sample database; and (c) reducing the total inventory by the available inventory for that request.

Another embodiment of the invention includes a method or system for planning and scheduling advertisement media over a network, where the network is coupleable to a plurality of terminals, and the plurality of terminals are operable by a plurality of users. In the embodiment, a total inventory is forecasted for a designated time period. The total inventory corresponding to a summation of a number of impressions that are deliverable to each terminal coupled to the network during the designated time period. A sample inventory is determined based on the total inventory. The sample inventory is used to predict a target inventory from the total inventory of impressions for the designated time period. The target inventory corresponds to impressions deliverable to the users of the terminals belonging to a demographic genus or category associated with the target inventory. An advertisement campaign is associated with the target inventory. Users of the terminals coupled to the network during the designated time-period are subsequently identified. A number of impressions from the advertisement campaign are selectively delivered to the identified users of the terminals who belong to the demographic genus or category of the target inventory.

In a variation, users of the plurality of terminals are registered. A request to log-in during the designated time period is received from at least some of the users of the plurality of terminals. These users are then identified. The impressions delivered to the terminals include media, and may output audio.

Another embodiment provides a method or system for planning advertisement campaigns for messaging application used by a plurality of terminals coupleable to a network. A plurality of users for the application are registered. Registration includes recording a user-profile based on one or more types of demographic information about each user registering in a true database. A user-interface is provided for each terminal coupled to use to messaging application on the network. User-profiles are selected from the true database to form a sample database that is representative of the true database. A total inventory of impressions that are deliverable to users identified by the user profiles in the true database are approximated. At least one of a genus or a category of the user profiles. The sample database is used to approximate a portion of the total inventory available for an advertisement campaign directed to the at least one of the genus or the category of the genus. A number of impressions from the advertisement campaign are selectively delivered to the user-interfaces of the terminals operated by users having the identified genus or category.

BRIEF DESCRIPTION OF THE FIGURES

FIG. 1 illustrates a block diagram of an embodiment of the invention.

FIG. 2 is an example of an algorithm for performing sampling under an embodiment of the invention.

FIG. 3 is an illustration of different inventory types that may be requested by an advertiser. FIGS. 4A-4D illustrate implementation of the invention using an architecture under an embodiment of the invention.

DETAILED DESCRIPTION

This application hereby incorporates by reference the contents of the provisional application, identified by Serial No. 60/124,159, filed March 11, 1999 with the United States Patent Office, naming Jeff Weiner as inventor, and provisional application identified by Attorney Docket No. 20452-704, filed June 17, 1999 with the United States Patent Office, entitled "System for Electronic Messaging and Chatting," naming Jeff Weiner, Paul Thurston, Patrick Robinson, Ken Bailey, and Chris Hall as inventors. Embodiments of this invention provide a predictive media planning and scheduling system. The media planning and scheduling system may form a component of a comprehensive advertisement management system (CAMS) for commercial network applications.

For purpose of this application, an impression refers to an event of a single end user viewing an advertisement or other media element. The advertisement may be, for example, in the form of a banner that appears over a web site that is being viewed by the user.

A media refers to some output detectable to an end user that forms the basis of an advertisement. Media includes, for example, banners that appear on web sites, audio feedback, and other electronic messages which can be detected by an end user over a network.

A targeting profile refers to attributes used to specify a specific demographic, sub-population, or class of end users. The targeting profile may be compiled using a Boolean conjunction of attributed that specify a subset of end users.

A targeted inventory refers to inventory associated with one or more targeting profiles.

A flight refers to an atomic advertising scheduling unit. A flight may be specified by one targeting profile, a set of media to employ with the impressions, and a duration for the flight given by start and end times.

A campaign refers to an aggregate advertising collection that includes one or more advertising flights.

A. Media Planning and Scheduling System

Embodiments of this invention provide a media planning and scheduling system (MPS) system that predicts and distributes inventory for delivery of advertisement media. Preferably, the inventory is in the form of total impressions from all the users in a network, as described below. The inventory may be predicted and distributed as unrestricted inventory or targeted inventory. As will be further described, embodiments of the invention predict unrestricted and targeted inventory to a high degree of accuracy, while minimizing memory and computation resources. In this way, advertisers who wish to use media over a network such as the Internet, or alternatively another network such as wide- area network LANS an email network, may be provided with a near real-time prediction as to the available unrestricted or targeted inventory for any particular time period. The ability to predict inventory in this manner significantly increases the commercial value of the inventory as a whole, since advertisers are able to better reach targeted consumers, and be afforded a reasonable prediction as to how many interested users will be delivered their advertisement media.

In addition, the MPS system under an embodiment of the invention enables advertisers to reach a very specific targeted inventory. The value of the targeted inventory increases by orders of magnitude as the target inventory becomes more specific. By being able to predict and deliver media to very specific target groups, the inventory value available to any network is also increased significantly. FIG. 1 is an illustrative diagram of an MPS system under an embodiment of the invention. In step 10, a true database is compiled containing demographic information for users of a network application. For purpose of discussion, reference will be made to users of an Internet messaging service that transmits voice communications as an email to other registered users of the service, or alternatively to email addresses of other individuals who are not registered to user the messaging services. However, other network activities for use with embodiments of the invention include Internet web sites, such as news or shopping sites, in which users may be identified.

An example of a network application for use with an embodiment of the invention is provided by RocketTalk Inc., accessible at www.rockettalk.com. To download software for use with the electronic messaging service, users must register and enter demographic information. In order to become registered, users must typically enter a name, and an email address. Other information may be optionally requested from an individual user. The demographic information is then tabulated for each user and compiled in a table with information from other users. Additional information may be received for each user by accessing other databases that store demographic information on individuals.

A true database may contain the name, location, age, email address, gender, income, computer type, and/or purchasing preferences for individual users. A user identification may be used to locate individuals and their particular demographic information in the tables. Other examples of users under an embodiment include individuals who have access to a particular network site and can be identified, such as by way of a cookie. The identification of the user may be used to access other personal information about the user.

In step 20, an unrestricted inventory is forecasted for delivering advertisement media based on the historical activities of the users in the true database. The inventory is preferably in the form of impressions. For example, users may be flashed banner advertisements while they deliver or receive voice mail messages on an messaging network as described above, or while surfing at a web site on the Internet. In an embodiment, unrestricted inventory is the total number of impressions delivered to all the users at any given time period.

Forecasting predicts unrestricted inventory for future time periods. Additional details regarding forecasting is provided below.

In step 30, sample database is formulated based on the true database. In an embodiment, the true database is sampled by a random selection to form a much smaller and more manageable sample database. The sample database is used in an algorithm to create probabilities for targeted portions of the inventory, in a manner described below with delivery media planning. Forecasting and sampling may be performed in any particular order.

In step 40, an inventory for advertisement delivery is predicted in response to a request of an advertiser. The inventory may, depending on the advertiser's request, be targeted or unrestricted. Unrestricted inventory is preferably determined by forecasting. As previously defined, targeted inventory includes requests for a portion of the unrestricted inventory. For example, the inventory may be targeted to a particular age group, gender, income bracket, educational level, and/or type of computer used by the individual. The likelihood that a particular advertising campaign or flight can be targeted according to demographic characteristics is determined from the sample database, as further explained below. (1) Forecasting

In an embodiment, a forecasting algorithm predicts the total inventory available at any particular time period based on historical activity. The total inventory may then be used in the planning and scheduling algorithms to develop advertisement flights or campaigns, for either unrestricted or restricted inventory.

As previously mentioned, unrestricted inventory includes the total number of impressions that are available to plan advertisement campaigns. According to an embodiment, unrestricted inventory equals to the number of individuals whom are recorded in a database to use a network multiplied by the impressions that may be delivered to each user. Impressions may be expressed in terms of data packets, as the number of impressions correlates directly with the number of data packets on the computer network. In an embodiment, unrestricted inventory is assumed to equal a summation of the average number of impressions that is available for each viewer.

In an embodiment, forecasting the unrestricted inventory for any particular time period may be accomplished using a self-similar stochastic process, also termed fractal geometry. Empirical studies suggest that traffic over networks, including local area network (LAN), wide area network (WAN), and the Internet, is fractal because users tend to have sporadic levels of interests. For example, web surfers activities increase significantly after locating an item of interest, but surfers browse through items of no interest very rapidly due to the relative ease by which Internet sites and activities can be ignored. This is in contrast to telephonic use, which tends to be non-fractal, as users interest is relatively constant over the time period or periods in which individuals use phones. Based on assumptions for fractal modeling, activity on a network may be modeled qualitatively as a summation of a "heavy-tail" portion for each user of the network. The heavy tail portion is the heavier or more extensive portions of each individual's use on the network. Formulas for use in developing fractal models based on heavy tail portions of individual network use may be found, or derived from, in Willinger, W., Taqqu, M.S., Sherman, R., Wilson, D.V., " Self-similarity through high- variability: statistical analysis of Ethernet LAN traffic at the source level" IEEE/ACM Trans. Networking, vol.5 no.l, February, 1997, pg. 71-86; Leland, W.E, Taqqu, M.S., Willinger, W., Wilson, D.V. (hereby incorporated by reference), " On the self-similar nature of Ethernet traffic (extended version)", IEEE/ ACM Trans. Networking, vol.2 no.l, February, 1994, pg. 1-15 (hereby incorporated by reference); and Crovella, M.E., Bestavros, A., " Self-similarity in World Wide Web traffic: evidence and possible causes" IEEE/ ACM Trans. Networking, vol.5 no.6, December, 1997, pg.835-846 (hereby incorporated by reference).

Forecasting using fractal geometry analysis may be implemented based on empirical studies showing the fractal nature of computer network use. The fractal analysis may be implemented with an autoregrissive integrated moving average (ARIMA). In an embodiment, forecasting is implemented by first determining a trend or growth (positive or negative). The trend curve may be determined using curve fitting, analyzed by, for example, regressions analysis. Preferably, the data points may represent impressions. For example, the data points may be data packet activity on the network, which is an expression used to estimate impressions.

Weight values are assigned to the historical data points forming the trend curve. The weighted values are then combined with a shock function. The shock function represents the variation from the weighted values. A combination of the weighted values and the shock function, such as a summation, provides an acceptable model for forecasting. The shock function is generated in the following manner. To determine the shock function, an ARIMA model may be used and/or general linear estimation. Details on using ARIMA models with fractal model assumptions is detailed in Time series Analysis, George Box, Gwilyn Jenkins, Gregory Reinfel, 3^rd edition, Prentice Hall (1994), pages 151-158, hereby incorporated by reference.

The specific fractal model for traffic on the computer network may be determined using critereas as set forth in Valderio Reisin, "Estimation of the Fractal Difference Parameter in the ARIMA (p.d.q) Model Using the Smooth Periodgram." Journal of Time Series Analysis, vol. 15, no. 3 (1995), pages 335- 350, with specific reference to 338. This article in its entirety is hereby incorporated by reference.

The fractal model may be reduced to one or more regular ARIMA models, using analysis shown in "On Prediction with Fractionally Differenced ARIMA models," M.S. Pieris, B.J.C. Perea, vol. 9, no. 3, pages 215-220 (1988). This article in its entirety is also hereby incorporated by reference.

After defractilization, one or more ARIMA functions or models may remain. An equation for forecasting, based on particular assumptions of a specific network, may be derived by applying Box-Jenkin analysis to each ARIMA equation. The result is a forecasting model based on fractal analysis of traffic.

In alternative embodiments, other forecasting algorithms may use models such as polynomial approximations may be used to develop forecasting models. Specifically, certain polynomial expressions may be used to model past historical data such as user activity or network traffic. The polynomial expressions may then be extrapolated to predict future activity or traffic, particular to a given time period. Historical data or traffic may be modeled, for example, by using techniques such as last value, moving average, or ARIMA methods.

For example, an embodiment may determine unrestricted inventory for a particular time period based on actual unrestricted inventory present on a network at a previous time period. The time period being predicted may have some relation to the time period forming the basis of the forecast. For example, the forecast for a 8-9 PM time slot on a Tuesday night may be based on the actual unrestricted inventory measured from the previous week for the same time slot on the same day, or on the measured unrestricted inventory measured from a previous hour of the day. Moving averages may also be used. For example, the unrestricted inventory for a time slot on a Wednesday night may be a moving average of the unrestricted inventory in the same time slot of a certain number of previous weeknights prior to the Wednesday night time slot being forecasted. The moving average may give extra weight to more recent weeknights, and/or Wednesday nights. (2) Sampling

In an embodiment, the MPS system uses a sample group that is reflective of the overall inventory for predictive planning and scheduling of advertising campaigns and flights. Among other uses, the sample group may be used to determine the likelihood that any individual in the true database falls within the target profile specified by a campaign. The target profile may be, for example, a very specific demographic portion of the users that form the true database.

Use of a sample group significantly decreases computational and hardware requirements necessary for making adequate predictions based on the advertisers request. For example, a true database may include ten million users, each of whom have a particular demographic profile. Massive computer resources are required to determine a targeted demographic request from an advertiser. In contrast, embodiments of the invention use a sampling table that may, for example, include only a small percentage of the users that are representative of the true database. Computations for predictive media planning and scheduling are easily performed using the sampling database. As will be further described, embodiments of the invention use sampling in a manner to predict with a high degree of accuracy available inventory for targeted and unrestricted advertising campaigns. In addition, sampling allows advertisers to receive predictions and feedback regarding a request in or near real-time. As a result, advertisers may be supplied a response to advertisement inquiries regarding inventory availability and targeting information immediately upon request, rather than an extended time period in which the advertiser's request is processed with other requests in a large computer system. This allows the advertiser to rely on more accurate and updated information. In addition, advertisers may use embodiments of the invention to launch campaigns to address more unpredictable and shorter lived business needs, such as for example, responding to business trends or news items that may affect advertisement strategy.

FIG. 2 illustrates an algorithm for sampling under an embodiment of the invention. As shown by FIG. 2, sampling involves organizing the true database for random selection, and then determining an optimal number to randomly select from the true database. Steps 110-140 illustrate steps under an embodiment to organize the true database, In step 110, the database is organized as a column of user identifications or pointers. In step 120, a uniform standard deviant is determined that defines a group of buckets ranging from 0 to 1. In an example, each bucket may segment the domain defined between 0 and 1 into intervals of 0.1. Each selection from the true database has an equal chance of falling into in one of the buckets defined by the uniform standard deviant. In step 130, a hashing function divides the user identification column into segments corresponding to the buckets, so that each segment of the user identification column has an equal likelihood of being selected with every selection. In step 140, a random number is generated corresponding to a user in the user identification column. As noted, the random number has an equal chance of falling into any one of the segments of the user identification corresponding to the buckets determined in step 120. The order in which the aforementioned steps are performed is not crucial to this embodiment of the invention. In step 150, an optimal sample size is determined. Derivation of an optimal sample is best shown by example. For illustrative purposes, the following statement of accuracy may be assumed: the proportion in the sample database that are within 2% of the proportion in the entire population space 19 out of 20 times a sample is constructed. A statistical formula for this statement of accuracy is

(a) P ^ -P^_p^ O^≥ O^

The law of large number allows for the assumption that the variance of the sample proportion is approximately equal to

(b) VAR (^p^ nple) /= -j- P_lnι. (l-P_ll

N

Approximation by Gaussian Distribution provides

Dividing equation of (a) by (c) gives

For (d) to be true, the following relation with the Z-score must also be true

0.02 (e) 1.96 <

7VAR (P_sampl Substituting equation (b) provides

0.02

(f) N > P (l - P) 1.96

Solving for a derivative of (f) then gives an optimal N, according to the following equation r ₉₆V (g) N > 0.02_y

Other sampling methods as used in statistical modeling may also be used with other embodiments of the invention.

One benefit provided by the sampling theory approach is that it scales to a viewer population of tens of millions. In addition, likelihood values are given as highly accurate estimates that require significantly less computational resources than other approaches. Among other advantages, sampling allows inventory prediction to be determined in seconds or less, compared to days or weeks when surveying a true database, as previously practiced. (3) Predicting Inventory for Advertisement Delivery An MPS system under an embodiment of the invention includes delivery media planning to predict available inventory for the delivery of advertisement media. Delivery media planning may be used to plan and schedule advertisement flights and campaigns. Preferably, delivery media planning is based on the unrestricted inventory predicted through forecasting. Delivery media planning accesses a database of demographic information associated with the unrestricted inventory. The demographic information is a compilation of personal information for individuals forming the unrestricted inventory. When advertisers request delivery media planning to individuals forming a specific demographic collection of the inventory, the campaign or flight is deemed to be targeted.

According to an embodiment, the delivery media planning improves over the known art by approximating targeted inventories from predicted unrestricted inventory, to an acceptable or high degree of accuracy. In this way, delivery media planning has an advantage of providing near real-time information as to available inventory (targeted and unrestricted) for flights and campaigns, as well as scalability, reliability and low cost deployment.

FIG. 3 illustrates a block diagram in which every request from an advertiser may be categorized between one of four categories. As shown by FIG. 3, the unrestricted category is for campaigns or flights which are indiscriminate as to the recipient. The unrestricted category is a genus, as defined below, since the unrestricted genus contains only a single category, called the unrestricted category. Every viewer in the population is declared to be in the unrestricted category.

A primary category is for campaigns or flights that is targeted to a geneses, or a category of a genus. A genus is a subset of the demographic population which includes categories that are mutually exclusive of one another. Specifically, a genus forms a probabilistic space known as an Intersection Zero/One Space, or a subspace consisting of mutually exclusive events. An example of a genus is gender. The gender genus may be defined as containing three categories, male, female, and unknown. Each viewer in the demographic population will reside in one and only one of these subsets: a viewer is either known to be male, known to be female or has unknown gender. Therefore, gender genus is an example of a zero/one space because every viewer falls into exactly one of the categories male, female, unknown, and no user falls into two or more categories. The intersection between any pair of categories is zero, while the union over all viewers in the categories is one, i.e. the entire demographic population. Another example of a genus is the income bracket genus. The income bracket genus is defined by a collection of mutually exclusive income brackets. These may be defined as low, upper lower, middle, upper middle, high and unknown.

A request from an advertiser may also be geared towards a more specific demographic portion formed by the combination of one or more categories/geneses. Such categories are termed derived categories. Derived categories may include multiple subcategories of the same genus, or a combination of primary categories. Derived categories may be correlated or uncorrelated. While previous discussion has assumed that the categories are uncorrelated, some derived categories may in fact be correlated. Correlated categories may also be termed splittable categories. Mathematically, splittable categories may be expressed as P(x & y) +0 where x and y are separate primary categories. Splittable categories include for example, correlations between occupations and area codes, and between credit cards and stores people tend to shop at. Splittable categories may be determined from demographic information using a data mining engine, or preprogramming the information into the table. a) Algorithms for processing advertising requests

Tables 1-7 illustrate implementation of an algorithm under an embodiment of the invention, in which the inventory is distributed, categorized and accounted for to predict campaigns and flights. Each of the tables illustrated below correspond to a particular time period in which requests for available inventory is received. The available inventory for the particular time period is then predicted, and detracted from the remaining inventory for the purpose of analyzing subsequent requests from advertisers.

Table 1: Initial Planning Table

Table 1 illustrates an initial planning table for planning and scheduling media delivery. For example Table 1 may represent inventory for any specific time period, such as inventory for a day, or an hour of the day. As shown, table may be organized according to demographic information, listed as geneses and categories. The genus column shown includes a gender genus and an income genus. Each genus includes categories, which are displayed in a category column. While Table 1 and other tables listed below show only one category column, other embodiments of the invention may list additional columns of sub categories for each category.

The likelihood column represents a percentage of impressions that are available from the unrestricted inventory for any demographic profile of the individuals who form the inventory. The available impressions for any request is preferably determined by using the sample database which contains a sampling of individuals and corresponding demographic information. The sample database is searched for the likelihood of finding a particular category for each genus. Therefore, the likelihood column is a statistical approximation of the true database.

The residual inventory column reflects the number of impressions or inventory that is available for each category. In an embodiment, the residual inventory for the unrestricted genus/category is determined by forecasting, as described above. The residual inventory for the remaining categories is determined by multiplying the probability, as listed in the likelihood column, with the available residual inventory, as initially determined by forecasting.

It may be the case that an advertiser makes an inventory query for one of the recorded categories shown in Table 1. For example, if the query is "how many impressions are available in the middle income bracket?", the response generated from Table 1 would be "1250 impressions". Such queries are termed primary category queries, which reside in a named genus. Table 2: Derived Category Table

Table 2 illustrates a prediction for available inventory for a derived category, in which two or more categories or combined using a Boolean AND operation. The derived category shown in Table 2 is of the portion of the demographic who are male and in the middle income category. The likelihood is determined from the sample database, shown in Table 2 as being 0.15. The total number of impressions, therefore, is the product of the probability for this derived category and the unrestricted residual inventory, as derived by forecasting.

Other derived categories may be similarly determined. For example, the derived category may be the combination of three or more categories, or a combination of alternative Boolean operators such as OR or NOT. b Accounting for Depletion of Inventory

Tables 3-7 illustrate that once a flight or campaign is scheduled, the remaining inventory is affected for a particular time period in that the planned or scheduled inventory must be accounted for subsequent campaigns or flights. The following tables illustrate with an additional column how the residual inventory is adjusted for subsequent campaigns after an initial campaign has been planned in a given time period. This may correspond to a scenario in which an advertiser reserves a portion of the inventory.

Table 3: Placing an Unrestricted Order

Table 3 shows an example in which an advertiser reserves unrestricted inventory for 1000 impressions. A new residual inventory column is derived as follows. The residual inventory for the unrestricted genus/category is reduced by 1000. The residual inventory for the remaining categories is determined by multiplying the probability for each category with the new residual inventory for the unrestricted inventory. Likewise, the inventory for a derived category is determined in the same manner. Table 4: Placing a Primary Category Order

Table 4 illustrates how an advertiser may reserve inventory for a primary category. For example, an advertiser may request "1,000 impressions of male viewers". The new residual inventory column reflects how the reservation of this inventory is distributed to the other primary and derived categories. Specifically, the unrestricted inventory is reduced by 1,000. Also, the primary category corresponding to the request is reduced by 1,000. Table 5: Placing a Derived Category Order

Table 5 considers the scenario in which an advertiser places a derived category inventory order. For example, the advertisers orders might be "500 impressions of male viewers in the middle income bracket."

In this example, at least 500 impressions are available in the primary and derived category of male, middle income, and male and middle income. Therefore, 500 impressions are deducted for each of these categories. Two geneses are affected in this example, gender and income bracket. All other categories in these geneses remain unchanged. Categories residing in any other genus are reduced by a percentage, as in the other scenarios above. c Placement of Orders with Correlated Categories Tables 6 and 7 illustrate the algorithm implemented with splittable categories. For purpose of demonstration, the effects of a splittable category may be demonstrated as follows. A genus is provided for internet service providers (ISP) which contains two ISP categories: MSN (Microsoft Network) and AOL (America On-Line). A browser genus contains two browser categories: Netscape and Internet Explorer. After the recent purchase of Netscape Communications Corporation by America On-Line, Inc., it can be assumed that almost all of the AOL users browse using the Netscape browser. However, a portion of the AOL users will use IE. In this case, category AOL from the ISP genus and category Netscape from the Browser genus are highly correlated.

Any order for any derived category containing either AOL or Netscape is therefore subjected to a splitting algorithm. This algorithm is depicted in the table below for the example derived category male & Netscape.

Table 6: Determining Splittable Category Inventory

In this case, the derived category Male & Netscape is split into two components: Males & Netscape & AOL, and the complimentary component Males & Netscape & ( not AOL). The total of all split components is returned to the advertiser as available inventory, in this case that quantity is 750 impressions. Should the advertiser desire some amount of that inventory, say 300 impressions, the order itself is split by proportion. In this case 2/3 of the order is allocated for Male & Netscape and AOL, while 1/3 is Male & Netscape & MSN. The ratio 2/3 is computed from the conditional likelihood calculation 0.10 / (0.10 + 0.05).

The effect of placing an order for 300 impressions of Male & Netscape is recorded in the table below.

Table 7: Placing a Splittable Category Order

In this case, although the ISP genus is not explicitly affected by the order, the splitting algorithm adjusts its values using a reduction technique other than the proportional reduction as seen in earlier scenarios. This permits increased accuracy in the presence of highly correlated data elements.

A separate record of splittable categories and their splitting partners can be kept and used as a pre-process filter to flight planning. Splittable categories can be recognized either by utilizing domain knowledge or by performing linear regression examinations against the population database. (4) Determine Priority of Campaigns and Flights

In an embodiment, the MPS system also determines the priority order for campaigns and flights over predetermined time periods. Preferably, a plurality of campaigns and flights may be scheduled for each period according to the commercial value of each campaign or flight. The value of a flight increases as the targeted profile becomes more specific. Therefore, the value of campaigns and flights reaching a small demographic is greater than another campaign or flight that reaches a broader demographic. The sample database may be used to predict the availability of inventory for specific campaigns. Table 8 illustrates one example in which flight priority scheduling is determined in a specific time period (such as an hour of the day) for seven campaigns, ranging from a very specific campaign (Campaign 7) to an unrestricted campaign (Campaign 6). Table 8: Flight Priority Scheduling

The ranking of the campaigns is based on the scarcity of the target profile associated with each campaign in the population of network users. Preferably, the target profile for each campaign is estimated to exist according to a likelihood percentage determined from the sample database. In the example of Table 8, Campaign 7 has the most specific target profile, where only 3% of the estimate population in the true database has the specified demographic. Campaign 6 has the least specific target profile, as it is unrestricted. Therefore, in the time period shown by Table 8, the order for Campaign 7 is filled first for the listed campaigns, while the order for Campaign 6 is filled last.

By ranking campaigns and flights sequentially according to priority, the inventory depletes progressively as lower ranked campaigns are reserved. For example, the residual inventory from Campaign 1 is depleted according to the number of impressions Campaign 7 reserved in that same time period. If, as shown, Campaign 7 requests 300 impressions, and the unrestricted inventory contains 1000 impressions, 30 impressions are reserved for Campaign 7 (according to 3% likelihood), and the residual inventory for the next highest ranked campaign (Campaign 1) is depleted by 30 impressions. Campaigns 2 and 3 are examples of campaign in which the advertisers request may be reserved because the available target inventory for that time slot exceeds the inventory of the request. Therefore, Campaigns 2 and 3 detract from the residual inventory by the amount contained in each respective request. Table 8 illustrates that the residual inventory available for each campaign is depleted by the sum total of all the impressions reserved by previous campaigns. Some campaigns request impressions that cannot be filled in just one time slot. In the example of Table 8, Campaign 7 requests 300 impressions when only 30 can be reserved according to the target profile requested by that campaign. Subsequently, Campaign 1 requests 200 impressions when only 83 can be reserved, Campaign 5 requests 300 impressions when only 275 impressions can be reserved, and Campaign 6 requests 400 impressions when only 313 can be reserved. In an embodiment, the number of impressions that cannot be reserved are then moved into another time slot. For example, if the time slot shown by Table 8 corresponds to an 8-9 PM time slot, a request for 270 impressions may be placed with a similar table for a 9-10 PM time slot. Advertiser may also request specific time slots in which the remaining impressions that are requested to be delivered. For example, as advertiser may request that Campaign 1 be distributed every Tuesday at the 8-9 PM time slot until the order is filled. Distribution of advertiser's request for inventory over a time frame such as a week is discussed in detail below. The ranking of the campaigns is executed to individual users as they log on or access the network in which the campaigns are being orchestrated. When a user logs on, a server on the network determines whether the users profile matches Campaign 1. If the user is not matched to Campaign 1, the server checks to see if the users profile matches the next ranked campaign, shown in the example of Table 8 as Campaign 1. This process is repeated until the user is assigned a campaign, or until users can no longer be placed in campaigns for that time slot. In an algorithm, residual inventory that is actually left after all of the campaigns for a time slot have been executed is used to control implementation of other time slots. That is the inventory reserved for each campaign is compared with the inventory actually executed for the purpose of implementing a feedback control system. For example, if the remaining residual inventory is zero after all of the campaigns have been executed, the unrestricted inventory and/or the predicted residual inventories for other campaigns may be increased to reflect unexpectedly high user activity. In this manner, the remaining residual inventory after all of the campaigns have been executed can be matched with reservations for future time slots. (5) Resource Allocation

An MPS system under an embodiment of the invention may also include a resource allocation algorithm. A resource allocation algorithm efficiently distributes requested inventory so to evenly distribute the inventory over a time frame. For example, a request may specify that an order be distributed over a three day period. Preferably, the order is distributed evenly over each of the three days. Therefore, an optimization algorithm may be implemented to determine the optimal distribution pattern for an request for media. A time frame may be limited to specific time slots that are intermittent over the course of the time period.

In an embodiment, the resource allocation algorithm is implemented using a quadratic optimization model. The time frame requested from the advertiser is discretized into time slots. For each time slot, the following formula may be applied

∑(Xi - C)²

where represents a time slot in a time frame, Xi represents available inventory for a specific campaign in a corresponding time slot in the time frame, and C is a constant that represents the orders requested. The derivative then can be used to provide the optimal distribution to each time slot in the time frame. (6) Implementation An MPS system under an embodiment of the invention may be implemented using a server system such as described with FIG. 4A. The system includes a concrete FlightPlanNode. The FlightPlanNode exists to interface to a particular database implementation and utilizes data access operations specific to the vendor's implementation. A FlightPlan is an aggregate of one or more FlightPlanNodes and an instance of a FlightPlan may span multiple databases implemented by multiple vendors.

FIG. 4B depicts an architecture of a FlightPlanVisitor. The FlightPlanVisitor declares a visitation operation for each concrete FlightPlanNode. Each concrete visitor implements some specific part of the flight planning algorithm.

FIG. 4C depicts the relationships between the MPS Client, the FlightPlan and the FlightPlanVisitor.

An MPSClient, which uses the FlightPlanVisitor, first creates a FlightPlan. The FlightPlanNodes that make up the FlightPlan are traversed using an instance of a concrete FlightPlanVisitor. When each node is visited, it calls the visitation method that corresponds to the node's class. These interactions are depicted in FIG. 4D below.

As shown by FIG. 4D, a consideration for the design of the Flight Planner is that of concurrent access. In one embodiment, multiple end users (i.e. advertisers) will be performing both inventory query (read) operations as well as flight scheduling and modification (write) operations on individual flight plans. As a result, database synchronization schemes in the PlanningNode class and access synchronization schemes in the FlightPlanNode caching layer should allow for concurrent access as well as resolve concurrency conflicts. (7) User-Interface

Under an embodiment of the invention, a user-interface may be implemented with the MPS system. The UI may interface with the MPS system to provide users to inquire about scheduled flights. The UI would also allow users to campaign status reports. B. Overview Comprehensive Advertising Management System Using MPS

In an embodiment, a media planning and scheduling system (MPS) is used as a component of a CAMS, preferably in combination with advertisement systems that include advertisement delivery, campaign reporting, and Internet data licensing.

(1) Advertisement Delivery System

An advertising delivery system transports advertising media associated with campaigns to an end user's desktop. Preferably, the advertising media is displayed on a user interface (UI) associated with the network. For example, a network such an electronic messaging system accessible through the Internet may include panels that display contact lists, in box, out box etc. A portion of the window that includes the panels may be dedicated to displaying advertising media. The advertising delivery system then transports advertising media to the portion of the window. The advertising delivery system uses a priority-based work queue (see e.g. Table 8) provided by the MPS system. In this embodiment, flight priority determines which media element to transport and display to the UI.

In an embodiment, the advertisement delivery system employs a media rotation scheme in order to maximize the number of unique impressions delivered. A rotation of the media may be triggered upon a particular action from the user to the UI. Alternatively, the media rotation may be triggered by timing the duration of a media event, such as the display of a banner.

The advertisement delivery system may engage in one or more pre- delivery system activities in order to facilitate real-time delivery of advertising media. These pre-delivery activities include calculating an association between each registered viewer and the campaign flights which matching that viewer's individual profile.

During delivery, the advertisement delivery system may utilize a flight priority and a user/campaign association to make media delivery decisions. Newly registered users who have no known targeting profile will only be delivered advertising media from campaign flights indicating no targeting criteria. With some modifications, the MPS may cooperate with an advertisement delivery system to allow for dynamically created media. In addition, a real-time media selection process may be implemented in an alternative embodiment to select media associated with a particular registered user.

(2) Campaign Reporting

In an embodiment, the CAMS employ a reporting system to generate summary reports concerning a current delivery status of any campaign or flight. The summary reports are then made accessible to advertisers or their representatives. Preferably, the reporting system gathers all relevant statistics regarding a flight, including current impression count, impressions remaining, current click count and current click ratio. In one example, current reports are generated and made available not less than four times during the standard business day (8 AM to 5 PM PST). The reporting system can support several methods of report retrieval, including HTTP via a network website, SMTP via email subscription and/or via an advertisers graphical user interface.

(3) Data Profile & Licensing

The comprehensive advertising management system will support user data licensing to third party advertising delivers. This facility will allow third party Internet advertising delivers to subscribe to and use demographic data associated with registered RocketTalk viewers in order to deliver advertising via the World Wide Web.

C. Conclusion

The foregoing description of various embodiments of the invention has been presented for purposes of illustration and description. It is not intended to limit the invention to the precise forms disclosed. Many modifications and equivalent arrangements will be apparent.

Claims

CLAIMSWhat is claimed is:

1. A method for planning and scheduling advertisement media over a network, the method comprising: accessing a database that indicates a total inventory of impressions deliverable to the plurality of users on the network, the total inventory being sorted by one or more demographic characteristics; creating a sample database that reflects the total inventory and the inventory database and is smaller than the inventory database; receiving a request for an available portion of the total inventory, the request specifying at least one of the demographic characteristics; and determining a proportion of the sample database having the demographic characteristic; and approximating the available inventory from the proportion of the sample database having the demographic characteristic.

2. The method of claim 1, wherein determining a proportion of the sample database includes identifying all of the sample database if the request includes an unrestricted characteristic.

3. The method of claim 2, wherein determining a proportion of the sample database includes identifying a portion of the sample database if the request includes a restricted characteristic.

4. The method of claim 1 , wherein:

receiving a request for an available portion of the total inventory includes identifying from the request a first characteristic corresponding to a genus of the total inventory, and a second characteristic corresponding to a category of the genus; determining a proportion of the sample database includes determining a set of the sample database defined by the genus, and determining a portion of the subset defined by the category; and approximating the available inventory includes using the proportion of the sample database determined by the portion of the set defined by the category.

5. The method of claim 1 , wherein: receiving a request for an available portion of the total inventory includes identifying from the request a first characteristic corresponding to a genus of the total inventory, a second characteristic corresponding to a category of the genus, and a third characteristic corresponding to a second category of the genus; and determining a proportion of the sample database having the characteristic includes determining a set of the sample database defined by the genus, determining a portion of the set defined by the first category, and determining another portion of the set defined by the second category; and approximating the available inventory includes using a proportion of the sample database having the characteristic of the request.

6. A method for planning and scheduling advertisement media over a network coupleable to a plurality of terminals, the method comprising: forecasting a total inventory of impressions that are available over the network, the total inventory corresponding to a summation of a number of impressions that are deliverable to each terminal coupleable to the network during a designated time period; creating a sample inventory based on the total inventory, the sample inventory being smaller than the total inventory; and using the sample inventory to predict a target inventory identified by a category of the total inventory of impressions.

7. The method of claim 6, wherein forecasting a total inventory includes using an actual total inventory measured during a previous designated time period.

8. The method of claim 7, wherein using an actual total inventory of a previous designated time period includes using the actual total inventory of a same hour, day, week, or month corresponding to designated time period.

9. The method of claim 7, wherein forecasting a total inventory includes using a plurality of actual total inventory values for other designated time periods.

10. The method of claim 9, wherein using a plurality of actual total inventory values for other designated time periods includes using the actual inventories of a same hour, day, week, or month corresponding to the designated time period.

11. A method for supplying demographic information about users of a network system to suppliers of media for the network system, the method comprising: building a true database comprising the demographic information about the users of the network system, the demographic information including a plurality of categories; identifying a sample database from the true database, the sample database being representative of the true database; and receiving a query for an available inventory of impressions deliverable to a specified group of the users of the network over a designated time period; and approximating the available inventory over the designated time period using the sample database.

12. The method of claim 11, further comprising displaying a graphic interface on a terminal operated by a supplier of media information to prompt for the query.

13. The method of claim 11 , wherein identifying a sample database includes determining a size for the sample database, and randomly identifying a number of users in the true database, the number of users matching the size of the sample database.

14. The method of claim 11 , wherein identifying a sample database comprises scaling the sample database according to a size of the true database.

15. The method of claim 11 , wherein building a true database includes storing demographic information from a plurality of users who register to use the network.

16. A method for planning advertisement campaigns for a network coupleable to a plurality of terminals, the method comprising: accessing a true database comprising a plurality of user profiles, the plurality of user-profiles being sorted into one or more groups using demographic characteristics; selecting user profiles from the true database to form a sample database that is representative of the true database; approximating a total inventory of impressions that are deliverable to users identified by the user profiles in the true database; identifying at least one of a genus or a category of the user profiles; and using the sample database to approximate a portion of the total inventory available for an advertisement campaign directed to the at least one of the genus or the category of the genus.

17. The method of claim 16, wherein selecting user profiles from the true database to form a sample database includes randomly selecting the user- profiles for the sample database.

18. The method of claim 17, wherein a size of the sample database is sufficient so that randomly selected user-profiles form a statistic representation of the true database.

19. The method of claim 16, wherein using the sample database to approximate a portion of the total inventory includes summing impressions that are deliverable to users identified by user-profiles in the sample inventory that share the at least one of the genus or the category.

20. The method of claim 16, further comprising predetermining a target inventory for one or more advertisement campaigns from a portion of total inventory corresponding to user-profiles that share at least one of a genus or characteristic, the portion of the total inventory being estimated from a representative sample of user-profiles in the sample inventory.

21. The method of claim 16, including forming a plurality of target inventories for one or more advertisement campaigns by determining a likelihood that each demographic profile in the plurality of demographic profiles belongs in at least one or more of a genus or a category.

22. The method of claim 16, wherein identifying at least one of a genus or a category of the demographic profiles includes identifying a derived category from a combination of the genus and the category, and predicting an available inventory for a first campaign includes summing each demographic profile in the sample inventory belonging in the derived category.

23. The method of claim 22, identifying a derived category from a combination of the genus and the category includes combining a first category and a second category using a Boolean operation.

24. The method of claim 22, including predicting the available inventory for each of a plurality of campaigns, each campaign directed to either the total inventory, the first target inventory, or another target inventory.

25. The method of claim 20, further comprising receiving a first inventory order, and determining a residual inventory for a subsequent inventory orders by subtracting the available inventory for the first inventory order from the total inventory.

26. The method of claim 25, wherein if receiving the first inventory order for the genus representing the total inventory, determining a residual inventory for a subsequent inventory request comprises subtracting the available inventory for the first inventory order from the total inventory to determine a new total inventory.

27. The method of claim 26, and using a proportion of the total inventory identified by the sample inventory to redetermine the first target inventory.

28. The method of claim 27, wherein if receiving the first inventory order for the first target inventory, determining a residual inventory for a subsequent inventory request comprises subtracting the first inventory order from the total inventory to determine a new total inventory, and subtracting the first inventory order from the target inventory to determine a new target inventory.

29. The method of claim 28, further comprising predicting an available inventory for a second campaign directed to the total inventory or a portion of the total inventory.

30. A method for planning advertisement campaigns for a network coupleable to a plurality of terminals, the method comprising: forecasting a total inventory for a designated period, the total inventory comprising a plurality of impressions that are deliverable to a plurality of users, the total inventory being grouped according to one or more demographic characteristics of the users; creating a sample inventory that reflects the total inventory and is smaller than the total inventory; receiving a first request for an available inventory, the request specifying one or more characteristics; identifying a proportion of the sample inventory having the characteristic of the first request; applying the proportion identified in the sample inventory to the total inventory to approximate the available inventory for the first request; and reducing the total inventory for a subsequent request by the available inventory for the first request.

31. The method of claim 27, further comprising: sorting the total inventory into a plurality of groups, each group comprising a portion of the inventory defined by one or more characteristics.

32. The method of claim 28, wherein before receiving the first request, further comprising approximating an existing inventory of each of the plurality of groups by identifying a proportion of the sample database having the characteristic of that group, and applying the proportion identified for each group to the total inventory to determine an existing inventory for each of the plurality of groups.

33. The method of claim 29, wherein subsequent to receiving the first request, further comprising approximating a new inventory for each of the plurality of groups using the proportion identified for that group in the sample inventory, and applying the proportion to the reduced total inventory to approximate a new inventory for each group.

34. The method of claim 28, wherein one or more of the groups are defined by a characteristic belonging to one of a genus or a category of a genus.

35. The method of claim 29, wherein one or more of the groups are defined by a correlated category formed by the combination of the two or more categories.

36. The method of claim 30, further comprising receiving a plurality of subsequent requests for available inventory, each subsequent request specifying one or more characteristics, and sequentially determining an available inventory for each subsequent request.

37. The method of claim 33, wherein for each subsequent request, the method further includes: a) identifying a portion of the sample database having the characteristic of that request; b) approximating the available inventory for that request from the portion of the sample database having the characteristics of that request; and c) reducing the total inventory request by the available inventory for that request.

38. The method of claim 34, further comprising arranging the first request and the plurality of subsequent requests in a designated order, and performing steps a) through c) for each of the first and subsequent requests sequentially in the designated order.

39. A method for planning advertisement campaigns for a network coupleable to a plurality of terminals, the method comprising: forecasting a total inventory for a designated period, the total inventory comprising a plurality of impressions that are deliverable to a plurality of users, the total inventory being grouped according to one or more demographic characteristics of the users; creating a sample inventory to represent the total inventory; receiving a plurality of requests for available inventory, the plurality of requests specifying one or more characteristics; arranging the plurality of requests into a sequential order; and performing for each request arranged in the sequential order: identifying a portion of the sample inventory having the characteristics of that request; approximating the available inventory for that request from the portion of the sample database; and reducing the total inventory by the available inventory for that request.

40. The method of claim 36, wherein arranging the plurality of requests in the designated order includes arranging the plurality of requests according to an order in which requests requiring a least amount on inventory reduce first from the total inventory.