Accurately estimating advertisement performance

[0001] 1. Field of the Invention

[0002] Implementations described herein relate to on-line advertising and, more particularly, to predicting the performance of such advertising.

[0003] 2. Description of Related Art

[0004] An on-line advertising system may provide advertisements to users when they visit certain web pages. When a particular advertisement is of interest to a user, the user may perform various actions, such as selecting (“clicking”) the advertisement, which may take the user to a web page belonging to the advertiser associated with the advertisement. Additional examples of user actions may include signing-up for services at the target web page, placing an order, etc.

[0005] On-line advertising systems may charge the advertisers based on the number of times their advertisements are shown to users (called advertisement “impressions”) and/or based on the number of times an advertisement is selected by the users. For example, an on-line advertising system may calculate a charge based, at least in part, on the clicks that an advertisement receives. Charges may also be calculated based on other characteristics as well, such as time of day, location of the user, age or other demographic information associated with the user, or the like.

[0006] The effectiveness of an online advertisement is often reflected by the number of times that a desirable user action occurs. For example, the number of times that the advertisement is clicked by a user. Accordingly, it is desirable to display advertisements to the user having the highest likelihood of the desirable user action taking place. Conventional advertisement selection processes fail to accurately predict the likelihood that a user action relating to an advertisement will occur.

[0007] One aspect is directed to a method for estimating on-line advertisement performance. The method may include identifying at least one candidate advertisement in response to an advertisement trigger. A set of at least one key may be identified relating to features of at least one of the candidate advertisement, the advertisement trigger, or a combination of the candidate advertisement and the advertisement trigger. Candidate advertisement performance may be estimated based on historical data relating to the at least one key.

[0008] Another aspect is directed to an on-line advertising device. The device may include means for observing an advertisement trigger. The device may further include means for identifying a candidate advertisement in response to the advertisement trigger. The device may also include means for identifying keys associated with statistically relevant features of at least one of the candidate advertisement or the advertisement trigger. The device may further include means for calculating a statistical effect of each identified key on a combination of the advertisement trigger and the candidate advertisement associated with the identified key. Means is also provided for calculating an estimated user action rate for the combination of the advertisement trigger and the candidate advertisement based on the calculated statistical effect of each identified key.

[0009] Yet another aspect of the invention is directed to an on-line advertisement selection system that may include a processing engine configured to generate statistical information for a plurality of keys associated with a plurality of query/advertisement pairs. An advertisement selection server may be configured to receive a user search query and set of candidate advertisements, where the advertisement selection server may be further configured to estimate a performance of each candidate advertisement based on the statistical information.

[0010] Still another aspect of the invention is directed to a method that may include receiving an advertisement trigger from a user; identifying a candidate advertisement for display to the user; identifying a set of keys having characteristics associated with the advertisement trigger and/or the candidate advertisement; retrieving historical statistical information for each key in the set of keys; calculating a model parameter for each key in the set of keys, where the model parameter is representative of a statistical relevance of the characteristics associated with the key and based on the retrieved historical statistical information; and calculating an estimated user action rate for the candidate advertisement based on a prior probability and each of the calculated model parameters.

[0021] The following detailed description of the invention refers to the accompanying drawings. The detailed description does not limit the invention.

[0022] Implementations consistent with the principles of the invention may estimate the performance of an advertisement. In this way, advertisement selection and ranking may be more accurately determined.

[0023] Estimated performance of an advertisement may be calculated by initially identifying a set of features or combination of features associated with the advertisement and/or a received query. These features may include, for example, geographic location of the user from which the query was received, geographic location of the advertisement provider, text of the query, text of the advertisement, text of the linked page associated with the advertisement, etc. Data regarding the historical occurrence of each feature may then be compiled and analyzed to generate an estimated likelihood that a particular user action relating to the advertisement will occur when served along with the received query.

[0024] FIG. 1 is an exemplary diagram of a system 100 in which concepts consistent with the principles of the invention may be implemented. System 100 may include multiple clients 110 connected to a server 120 via a network 140. Network 140 may include a local area network (LAN), a wide area network (WAN), a telephone network, such as the Public Switched Telephone Network (PSTN), an intranet, the Internet, or a combination of networks. Clients 110 and server 120 may connect to network 140 via wired, wireless, or optical connections. Three clients 110 and one server 120 have been illustrated as connected to network 140 for simplicity. In practice, there may be more clients and/or servers. Also, in some instances, a client may perform one or more functions of a server and a server may perform one or more functions of a client.

[0025] A client 110 may include a device such as a personal computer, a wireless telephone, a personal digital assistant (PDA), a lap top, or another type of computation or communication device, a thread or process running on one of these devices, and/or an object executable by one of these devices.

[0026] Server 120 may include a server device, or a combination of devices, that processes, searches, and/or maintains documents and images in a manner consistent with the principles of the invention. A “document,” as the term is used herein, is to be broadly interpreted to include any machine-readable and machine-storable work product. A document may include, for example, an e-mail, a web document, a web site, a file, a combination of files, one or more files with embedded links to other files, a news group posting, a blog, a web advertisement, etc. In the context of the Internet, a common document is a web document. Web documents often include textual information and may include embedded information (such as meta information, images, hyperlinks, etc.) and/or embedded instructions (such as Javascript, etc.). A “link,” as the term is used herein, is to be broadly interpreted to include any reference to/from a document from/to another document or another part of the same document.

[0027] Server 120, in one implementation, may include a search engine that receives search queries from clients 110 and returns links to results relevant to the search queries back to clients 110. In an implementation consistent with the invention, server 120 may also return advertisements with the search query results. For example, third parties may contract with the operator of server 120 to display their advertisements when their advertisements are relevant to a search query. In other words, server 120 may implement an on-line advertising system.

[0028] Server 120 may implement a number of processes that assist in its operation as an advertising system. Consistent with an aspect of the invention, server 120 may include, or be associated with, a tool, referred to herein as advertisement selection system 125, that assists in selecting, ranking, and presenting advertisements to users along with the search query results. Advertisement selection system 125 will be described in more detail below.

[0029] In one implementation consistent with principles of the invention, advertisement selection system 125 may be implemented as hardware and/or software within server 120. In another implementation, advertisement selection system 125 may be implemented as hardware and/or software within one or more devices separate from or including server 120.

[0030] FIG. 2 is an exemplary diagram of a client 110 or server 120. Client/server 110/120 may include a bus 210, a processor 220, a main memory 230, a read only memory (ROM) 240, a storage device 250, an input device 260, an output device 270, and a communication interface 280. Bus 210 may include conductors that permit communication among the components of client/server 110/120.

[0031] Processor 220 may include a conventional processor, microprocessor, or processing logic that interprets and executes instructions. Main memory 230 may include a random access memory (RAM) or another type of dynamic storage device that may store information and instructions for execution by processor 220. ROM 240 may include a conventional ROM device or another type of static storage device that may store static information and instructions for use by processor 220. Storage device 250 may include a magnetic and/or optical recording medium and its corresponding drive.

[0032] Input device 260 may include one or more conventional mechanisms that permit a user to input information to client/server 110/120, such as a keyboard, a mouse, a pen, voice recognition and/or biometric mechanisms, etc. Output device 270 may include one or more conventional mechanisms that output information to the user, including a display, a printer, a speaker, etc. Communication interface 280 may include any transceiver-like mechanism that enables client/server 110/120 to communicate with other devices and/or systems. For example, communication interface 280 may include mechanisms for communicating with another device or system via a network, such as network 140.

[0033] As will be described in detail below, server 120, consistent with the principles of the invention, may perform advertisement selection operations through advertisement selection system 125. In one implementation, advertisement selection system 125 may be stored in a computer-readable medium, such as memory 230. A computer-readable medium may be defined as one or more physical or logical memory devices and/or carrier waves.

[0034] The software instructions defining advertisement selection system 125 may be read into memory 230 from another computer-readable medium, such as data storage device 250, or from another device via communication interface 280. The software instructions contained in memory 230 may cause processor 220 to perform processes that will be described later. Alternatively, hardwired circuitry or other logic may be used in place of, or in combination with, software instructions to implement processes consistent with the invention. Thus, implementations consistent with the principles of the invention are not limited to any specific combination of hardware circuitry and software. Additionally, multiple computing devices may function together to implement the functionality of a single server 120 or of advertisement selection system 125.

[0035] Before describing advertisement selection system 125 in additional detail, it may be helpful to further describe exemplary advertisement systems that may be implemented by server 120. Accordingly, examples of on-line advertisements will now be described with reference to FIGS. 3A, 3B, 4A, and 4B.

[0036] FIG. 3A is a diagram illustrating an exemplary web document 310 that may be provided by server 120, when functioning as an advertisement system and a search engine, to clients 110. In this example, web document 310 is a web page that displays results 312 that relate to a search query 314 submitted by one of clients 110. Web document 310 may additionally display advertisements, such as advertisements 316 and 317, which may include text and/or graphical advertisements that were determined by server 120 to be relevant to results 312 and/or search query 314. Advertisements may also be referred to as “creatives”.

[0037] Advertisements 316 and 317 may be provided to the operator of server 120 (also called the content host) by advertisers that would like their advertisements displayed to clients 110 that access server 120, such as users who are performing searches through server 120. The advertisement system may charge the advertisers when a user clicks one of the displayed advertisements 316 and 317. Alternatively, charges may be incurred upon the occurrence of additional user actions, such as order placement, target web site registration, etc.

[0038] FIG. 3B is a diagram illustrating another exemplary web document 320. In this example, web document 320 contains content 325 and one or more advertisements 326 and 327. Web document 320 may generally be hosted by a party distinct from the advertisement system that operates server 120 to serve the advertisements. For example, web document 320 may include a web page from a web site targeted to auto enthusiasts. Advertisements 326 and 327 may be advertisements selected by and displayed on web document 320 by the content host. When a client 110 visits web document 320, a web browser at the client may obtain content 325 from the operator of web document 320 and advertisements 326 and 327 from server 120. The advertisements may be selected to generally be relevant to the content of web document 320 or to the content of the web site of which web document 320 is a member. The client web browser may assemble content 325 and advertisements 326 and 327 into a single document for display to the user.

[0039] As with advertisements 316 and 317, advertisements 326 and 327 may be provided to server 120 by advertisers. When a user clicks on one of advertisements 326 or 327, the operator of server 120 may charge the advertiser and credit the operator of web document 320. Accordingly, in this example, the operator of web document 320 agrees to display advertisements provided by server 120 in exchange for monetary compensation when visitors to web document 320 click on one of the displayed advertisements. As described above, more complex user actions may also trigger the charging of the advertiser.

[0040] FIG. 4A is a diagram illustrating an exemplary advertisement 400 submitted by an advertiser. The advertiser may include advertisement text 410 and trigger text 420. In this example, the advertiser would like advertisement text 410 displayed when a user of the search engine includes the terms “jewelry” in their search query. The advertiser may also enter a link 430 for the advertisement and anchor text 440 that the advertiser would like displayed with link 430.

[0041] FIG. 4B is a diagram illustrating a rendered version of advertisement 400 provided to client 110. Advertisement 400 may be displayed, for example, as advertisement 316 or 317 (FIG. 3), in response to a user search query 314 that includes the term “jewelry.”

[0042] The operation of advertisement selection system 125 will now be described in detail.

[0043] FIG. 5 is a flow chart illustrating exemplary high-level operations that may be performed by advertisement selection system 125. As described briefly above, advertisement selection system 125 may operate to identify, rank, and display advertisements in response to received user queries. Initially, upon receipt of a query, either in real time or extracted from a historical log of past queries, advertisement selection system 125 identifies a set of either candidate advertisements (in the case of new queries) or served advertisements (in the case of past queries) (act 500). Once a set of candidate advertisements has been identified, a set of keys relating to characteristics of the advertisements, the query or a combination of both may be identified (act 502).

[0044] Although candidate advertisements have been discussed above with respect to a received query, it should be understood that candidate advertisements may also be identified based on non-query information, such as the content of a web document or other document in which the advertisement is displayed, such as in web document 320 of FIG. 3B. In such a non-query implementation, the identified keys may relate to features of the candidate advertisements and/or features of the web document on which they are to be displayed. Collectively, a web document for displaying advertisements and a received query may be referred to as “advertisement triggers”, each initiating the advertisement performance estimate process described herein.

[0045] As defined herein, a “key” may be an arbitrary string of information relating to any identifiable feature or combination of features associated with the received query or the advertisements identified for display with the search results. In should be further understood that the “query” may include additional information beyond the search terms input by the user. For example, each received query may also include information relating to a broader category or topic associated with the query, the geographic location of the user who initiated the query, the search preferences employed by the user, the type of web browser or other application used to initiate the search, the language preference of the user, the user's interne protocol (IP) address, the ad click or user action history associated with the user and/or the user's IP address, the user's search history, the date and time the query was received, etc.

[0046] In addition to query-related features, each key may additionally or alternatively include features related to the identified advertisements. Advertisement-related features may include the advertiser name, the keyword targets of the ad, the text or content of the ad, the destination URL (uniform resource locator) of the ad, the geographic location of the advertiser, the language of the ad, etc.

[0047] Keys may be then represented as a set of tag-value pairs, where the tag identifies a particular feature type, and the value identifies the corresponding feature value. For example, the notation “user_country: Canada” represents a tag-value pair that indicates that the user's country of residence is Canada. A key consisting of several tag-value pairs may be written as a list enclosed in parentheses. For example, (user_country: “Canada”, query_text: “camping gear”) denotes a key consisting of two tag-value pairs, both of which must be satisfied in order for the given key to be selected.

[0048] Examples of keys may include: (query_word: “free”), i.e. the user's search query contains the word “free”; (user_country: “USA”, user_language: “English”), i.e. the user is located in the USA and the user's selected interface language is English; (destination_page_text: “swimming pool”, query_word: “pool”, browser: “Safari”), i.e. the destination page of the advertisement link contains the phrase “swimming pool”, the user's search contains the word “pool”, and the user is using the Safari browser; etc.

[0049] By using this additional information query and advertisement information, advertisement selection system 125 may more accurately estimate user action rates (UARs) for the identified advertisements in response to the received query, in the manner described in additional detail below.

[0050] In one implementation consistent with principles of the invention, key sets may comprise a broad range of advertisement and query features or characteristics. Alternatively, key sets may include predetermined or designated combinations of query and advertisement features or characteristics. In one implementation, keys may be selected based on predetermined rules associated with the advertisement trigger. For example, a rule may specify that if the advertisement trigger is a search query, then a key will be selected for each pair of adjacent words in the user's search query. According to this rule, the search query “anniversary flowers seattle” would generate the two keys (query_phrase: “anniversary flowers”) and (query_phrase: “flowers seattle”). Additional keys may be generated by other rules associated with the advertisement trigger or the advertisement itself. Although this technique may result in a number of keys being identified, the technique may be used to indicate types of information which are considered useful and hence are suitable for inclusion in the key set for the trigger/advertisement pair. As will be described in additional detail below, the selection of applicable or relevant keys may be further refined from an initial set to reduce the likelihood that irrelevant or redundant keys are included within the UAR estimation process.

[0051] Following initial key selection, historical data regarding each key is retrieved from storage associated with advertisement selection system 125, such as storage device 250 described above (act 504). In one implementation consistent with principles of the invention, the historical data may include information or statistics relating to the number of impressions associated with the key, the number of user actions (e.g, clicks, orders, etc.) associated with the key, etc. As described above, the term “impressions” relates to the number of times the advertisement was displayed in conjunction with the selected key. Further, the term “user actions” relates to the number of times a particular user action associated with the advertisement occurred. For example, it may be determined that for a key such as (user_country: “USA”, advertiser_country: “Canada”), a matching advertisement was displayed 1000 times and acted upon 30 times, representing a historical user action rate of 0.03. In one embodiment, such historical information may be retrieved from various logs maintained by server 120, such as query logs and user action logs.

[0052] The historical information for each key identified in act 502 is then compiled in substantially real-time and a prediction model is applied thereto to generate an estimated UAR or user action probability for each query/advertisement pair (act 506). The estimated UAR may then be used to select, rank or otherwise classify advertisements for potential display to the user in response to the received query (act 508).

[0053] A prediction model consistent with principles of the invention has the following general structure. The estimated likelihood that a given user action will occur for a given trigger/advertisement pair is a function of a prior likelihood that the action will occur, and one or more model parameters associated with the selected keys for the given trigger/advertisement pair. The model parameters are calculated using an iterative process that attempts to solve for the parameter values that produce the best fit of the predicted user action probabilities to the actual historical data used for training.

[0054] The prior likelihood of a user action may be set to a predetermined constant, or it may depend on various features associated with the trigger/advertisement pair, such as IR (information retrieval) scores, the position and size of the displayed advertisement, etc. For example, an advertisement that appears at the top of a search result page may be assigned a higher prior likelihood of a user action occurring than a similar advertisement that appears at the bottom of a search result page.

[0055] The model parameters associated with each key may consist of a single parameter, such as a multiplier on the probability or odds of the desired user action occurring. Alternatively, each key may have several model parameters associated with it that may affect the predicted probability of a user action in more complex ways.

[0056] In the following description, various odds and probabilities are used. The odds of an event occurring and the probability of an event occurring are related by the expression: probability=odds/(odds+1). For example, if the odds of an event occurring are ½ (i.e., the odds are “1:2” as it is often written), the corresponding probability of the event occurring is ⅓. According to this convention, odds and probabilities may be considered interchangeable. It is convenient to express calculations in terms of odds rather than probabilities because odds may take on any non-negative value, whereas probabilities must lie between 0 and 1. However, it should be understood that the following implementation may be performed using probabilities exclusively, or using some other similar representation such as log(odds), with only minimal changes to the description below.

[0057] FIG. 6 is a flow diagram illustrating one implementation of the prediction model of act 506 for generating an estimated UAR for each trigger/advertisement pair. Although the final UAR is defined in terms of the probability of a user action occurring, the estimated UAR for a given trigger/advertisement pair may equivalently be represented as the user action odds (q) as described above. In accordance with one implementation of the principles of the invention, the user action odds may be calculated by multiplying the prior user action odds (q₀) by a model parameter (m_i) associated with each selected key (k_i), henceforth referred to as an odds multiplier. Such a solution may be expressed as:
q=q₀m₁·m₂·m₃ . . . m_n

[0058] In essence, the odds multiplier for each key may be a statistical representation of the predictive power of this key in determining whether or not a user action occurs. In one implementation, the odds multiplier for each key may represent the observed change in the user action rate for trigger/advertisement pairs that select this key (aggregated over the historical data) that cannot be modeled or “explained” using any of the other keys.

[0059] In one implementation consistent with principles of the invention, the model parameters described above may be continually modified to reflect the relative influence of each key on the estimated UAR for each given trigger/advertisement pair. Such a modification may be performed by comparing the predicted probability that a user action will occur disregarding the given key to the measured historical user action rate. In this manner, the relative value of the analyzed key may be identified and refined.

[0060] Turning specifically to FIG. 6, for each selected key (k_i), an average self-excluding probability (P_i) may be initially calculated or identified (act 600). In one implementation, the self-excluding probability (P_i) is a value representative of the relevance of the selected key and may measure the resulting user action rate of a trigger/advertisement pair when the selected key's model parameter (m₁) is removed from the estimated UAR calculation. For key 3, for example, this may be expressed as:
P₃n=((q₀·m_i·m₂·m₃ . . . m_n)/m₃)/(((q₀·m_i·m₂·m₃ . . . m_n)/m₃)+1).

[0061] In one embodiment, the self-excluding probability for each key may be maintained as a moving average, to ensure that the identified self-excluding probability converges more quickly following identification of model parameter for each selected key. Such a moving average may be expressed as:
P_in(avg)=αP_i(n-1)(avg)+(1−α)P_in,
where α is a statistically defined variable very close to 1 (e.g., 0.999) used to control the half-life of the moving average. As shown in the above expression, the value of P_i for the current number of impressions (n) is weighted and averaged by the value of P_i as determined at the previous impression (e.g., n−1).

[0062] Next, the average self-excluding probability (P_i(avg)), may be compared to historical information relating to the number of impressions observed and the number of user actions observed for the observed impressions (act 602). The model parameter associated with the selected key may then be generated or modified based on the comparison of act 602 (act 604).

[0063] FIG. 7 is a flow diagram illustrating one exemplary implementation of the processing of acts 602-604 of FIG. 6. Initially, a confidence interval relating to the odds of a user action may be determined (act 700). Using a confidence interval technique enables more accurate and stable estimates when keys having lesser amounts of historical data are used. In one implementation, the confidence interval includes a lower value L_i and an upper value U_i and is based on the number of impressions (n_i) and user actions (j_i) observed for the selected key. For example, the confidence interval may be an 80% confidence interval [L_i,U_i] calculated in a conventional manner based on the number of impressions and user actions observed. Following confidence interval calculation, it may then be determined whether the average self-excluding probability (P_i(avg)) falls within the interval (act 702). If so, it may be determined that the selected key (k_i) has no effect on the clickthrough rate and its model parameter (m_i) may be set to 1, effectively removing it from the estimated UAR calculation (act 704). However, if it is determined that P_i(avg) falls outside of the confidence interval, then the model parameter for the selected key (m_i) may be set to the minimum adjustment necessary to bring the average self-excluding probability (P_i(avg)) into the confidence interval (act 706). This calculation may be expressed mathematically as:
m_i=[L₁(1−P_i(avg))]/[P_i(avg)(1−L_i)]

[0064] Consider the following example: suppose that 200 user actions (j_i) and 10,000 impressions (n_i) have been observed for a key (k_i) representing the fact that the user is in the United States and the query is related to used cars. Furthermore, suppose that the average predicted user action probability (P_i(avg)) for these impressions (not including the effect of this key) is 0.015. The 80% confidence interval for 200 user actions out of 10,000 impressions is [0.0182,0.0219], so we would set m_i to the model parameter required to transform 0.015 into 0.0182. When submitted into the above expression, this value turns out to be 1.217. In other words, we presume that the presence of this key means that the user is about 20% more likely to perform the measured action than would otherwise be expected.

[0065] Returning now to FIG. 6, once the model parameter for the selected key is calculated, it may be determined whether additional keys remain to be processed (i.e., whether k_i<k_m) (act 606). If additional keys remain to be processed, the counter variable i may be incremented (act 608) and the process may return to act 600 to process the next key. Once model parameters for all keys have been calculated or modified, the estimated odds of a user action may be calculated using the equation q=q₀·m₁·m₂·m₃ . . . m_n (act 610). The odds may then be converted to an estimated user action probability or user action rate using the conversion convention described above (act 612).

[0066] In one implementation consistent with principles of the invention, the UAR prediction model may be trained by processing log data as it arrives and accumulating the statistics mentioned above (e.g., impressions, user actions, self-excluding probabilities, etc.). As additional impressions occur, the confidence intervals associated with each key may shrink and the parameter estimates may become more accurate. In an additional implementation, training may be accelerated by reprocessing old log data. When reprocessing log data, the estimated click probability may be recalculated using the latest parameter or odds multiplier values. This allows the prediction model to converge more quickly.

[0067] In an alternative implementation consistent with principles of the invention, a Bayes estimation can be used to calculate the model parameter for each key. In a Bayesian implementation, a prior distribution (g) of model parameters may be initially determined, such that g(log m) represents the prior probability that a given key has an odds multiplier m. The given model parameter m_i may then be set to be the value of m that maximizes the product:
f(log m)=g(log m)h(log m)
where h(log m) is proportional to the probability of observing j, user actions out of n_i impressions using the given value of m:
h(log m)=pow(p,j_i)pow(1−p,n_i−j_i), where
p=(m·p_i)/(1−p_i+m·p_i) and pow(x,y) represents raising x to the power of y. It should be noted that the above expressions uses log(m) rather than m in order to make the distributions more symmetric.

[0068] FIG. 8 is a block diagram illustrating one exemplary configuration of advertisement selection system 125 for selecting and displaying advertisements in response to queries received from users. Advertisement selection system 125 may include data processing engine 802, a data collection engine 804, data storage 806, an advertisement selection server 808, and an advertisement server 810. Although a discrete number of distinct system components has been identified, it should be understood that system 125 may include more, fewer, or a different arrangement of components.

[0069] In operation, data processing engine 802 may receive a stream of data from data collection engine 804, where each update includes at least a key and a value associated with the key. Once received, data processing engine 702 may apply a rule or rules to the data regarding how to combine multiple values for the same key. For example, received values may include the number of impressions, the number of observed user actions, and the self excluding probability. Rules may then be used to combine multiple values for the same key. For example, values for impressions may be added, values for user actions observed may be added, and the self excluding probability may be updated in accordance with a predetermined methodology.

[0070] Data collection engine 804 may operate to collect query and advertisement information from data storage 806 and generate the update stream sent to data processing engine 802. In one implementation consistent with principles of the invention, the query and advertisement information may include log files, such as query logs, click logs, etc. Data collection engine 804 may perform a lookup from data processing engine 802 to retrieve the prior cumulative data associated with the keys. This data is then used to calculate the updated model parameters for the identified keys in the manner described above. Updates for the identified keys are then forwarded to data processing engine 802.

[0071] Advertisement selection server 808 may operate to receive a query and associated set of candidate advertisements from advertisement server 810. Using the prediction model described above, advertisement selection server 808 may initially identify the set of keys to be used in estimating the UAR for each query/advertisement combination. Advertisement selection server 808 then retrieves the data associated with the keys from data processing engine 802. Once the key data has been received, advertisement selection server 808 may calculate estimated UARs for each candidate advertisement in the manner described above. These estimated UARs may then be passed to advertisement server 810 for use in determining which advertisements to display to the user.

[0072] Advertisement server 810 may serve a selected grouping of advertisements in combination with search results relating to the query based on a ranking associated with the estimated UARs. In response to the ad serving, a user action associated with one or more of the advertisements may be observed. Following each of query reception, ad serving, and observed user actions, advertisement server 810 may generate or update the data maintained in data storage 806.

[0073] In one embodiment, key data that has not been accessed within a predetermined period of time is considered to be no longer used and is removed from the servable data. Examples of old data may include identifiers for obsolete advertisements, etc. In another implementation, a total number of key impressions is tracked within a predetermined time period (e.g., one year). If the total number of key impressions observed during the time period is less than a predetermined threshold, the data is considered statistically irrelevant and is removed from the servable map file. By filtering the data used by the UAR prediction model, performance and accuracy of the model may be increased.

[0074] As described herein, the performance of an on-line advertisement may be accurately predicted.

[0075] The foregoing description of exemplary embodiments of the invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention.

[0076] In addition, one or more of the described acts may be performed by server 120 or another device (or combination of devices). In one implementation, one or more of the described acts may be performed by a client 110.

[0077] Moreover, while series of acts have been described with regard to FIGS. 5-7, the order of the acts may be varied in other implementations consistent with the invention. Moreover, non-dependent acts may be implemented in parallel.

[0078] It will also be apparent to one of ordinary skill in the art that aspects of the invention, as described above, may be implemented in many different forms of software, firmware, and hardware in the implementations illustrated in the figures. The actual software code or specialized control hardware used to implement aspects consistent with the principles of the invention is not limiting of the invention. Thus, the operation and behavior of the aspects of the invention were described without reference to the specific software code—it being understood that one of ordinary skill in the art would be able to design software and control hardware to implement the aspects based on the description herein.

[0079] No element, act, or instruction used in the description of the invention should be construed as critical or essential to the invention unless explicitly described as such. Also, as used herein, the article “a” is intended to include one or more items. Where only one item is intended, the term “one” or similar language is used. Further, the phrase “based on” is intended to mean “based, at least in part, on” unless explicitly stated otherwise.