Advertising on the Web - Mining of Massive Datasets - page 290

its ends are yet part of an edge previously selected for the match. This algorithm can be proved to have a competitive
ratio of 1 / 2; that is, it never fails to match at least half as many nodes as the best off-line algorithm matches.
✦ Search Ad Management : A search engine receives bids from advertisers on certain search queries. Some ads are dis-
played with each search query, and the search engine is paid the amount of the bid only if the queryer clicks on the
ad. Each advertiser can give a budget, the total amount they are willing to pay for clicks in a month.
✦ The Adwords Problem : The data for the adwords problem is a set of bids by advertisers on certain search queries,
together with a total budget for each advertiser and information about the historical click-through rate for each ad for
each query. Another part of the data is the stream of search queries received by the search engine. The objective is to
select on-line a fixed-size set of ads in response to each query that will maximize the revenue to the search engine.
✦ Simplified Adwords Problem : To see some of the nuances of ad selection, we considered a simplified version in
which all bids are either 0 or 1, only one ad is shown with each query, and all advertisers have the same budget.
Under this model the obvious greedy algorithm of giving the ad placement to anyone who has bid on the query and
has budget remaining can be shown to have a competitive ratio of 1 / 2.
✦ The Balance Algorithm : This algorithm improves on the simple greedy algorithm. A query's ad is given to the ad-
vertiser who has bid on the query and has the largest remaining budget. Ties can be broken arbitrarily.
✦ Competitive Ratio of the Balance Algorithm : For the simplified adwords model, the competitive ratio of the Balance
Algorithm is 3 / 4 for the case of two advertisers and 1 − 1 /e , or about 63% for any number of advertisers.
✦ The Balance Algorithm for the Generalized Adwords Problem : When bidders can make differing bids, have different
budgets, and have different click-through rates for different queries, the Balance Algorithm awards an ad to the ad-
vertiser with the highest value of the function Ψ = x (1 − e −f ). Here, x is the product of the bid and the click-through
rate for that advertiser and query, and f is the fraction of the advertiser's budget that remains unspent.
✦ Implementing an Adwords Algorithm : The simplest version of the implementation serves in situations where the bids
are on exactly the set of words in the search query. We can represent a query by the list of its words, in sorted order.
Bids are stored in a hash table or similar structure, with a hash key equal to the sorted list of words. A search query
can then be matched against bids by a straightforward lookup in the table.
✦ Matching Word Sets Against Documents : A harder version of the adwords-implementation problem allows bids,
which are still small sets of words as in a search query, to be matched against larger documents, such as emails or
tweets. A bid set matches the document if all the words appear in the document, in any order and not necessarily
adjacent.
✦ Hash Storage of Word Sets : A useful data structure stores the words of each bid set in the order rarest-first. Docu-
ments have their words sorted in the same order. Word sets are stored in a hash table with the first word, in the
rarest-first order, as the key.
✦ Processing Documents for Bid Matches : We process the words of the document rarest-first. Word sets whose first
word is the current word are copied to a temporary hash table, with the second word as the key. Sets already in the
temporary hash table are examined to see if the word that is their key matches the current word, and, if so, they are
rehashed using their next word. Sets whose last word is matched are copied to the output.
8.7 References for Chapter 8
[ 1 ] is an investigation of the way ad position influences the click-through rate.
The Balance Algorithm was developed in [ 2 ] and its application to the adwords problem
is from [ 3 ] .
[1] N. Craswell, O. Zoeter, M. Taylor, and W. Ramsey, “An experimental comparison of click-position bias models,”
Proc. Intl. Conf. on Web Search and Web Data Mining pp. 87-94, 2008.