Databases Reference
In-Depth Information
F
The Balance Algorithm: This algorithm improves on the simple greedy
algorithm. A query's ad is given to the advertiser who has bid on the query
and has the largest remaining budget. Ties can be broken arbitrarily.
F
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.
F
The Balance Algorithm for the Generalized Adwords Problem: When bid-
ders can make differing bids, have different budgets, and have different
click-through rates for different queries, the Balance Algorithm awards an
ad to the advertiser 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 ad-
vertiser and query, and f is the fraction of the advertiser's budget that
remains unspent.
F
Implementing an Adwords Algorithm: The simplest version of the imple-
mentation 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 struc-
ture, 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.
F
Matching Word Sets Against Documents: A harder version of the ad-
words-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.
F
Hash Storage of Word Sets: A useful data structure stores the words of
each bid set in the order rarest-first. Documents 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.
F
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 ad-
words problem is from [3].
