Note to other teachers and users of these slides: We would be delighted if you found this ourmaterial useful in giving your own lectures. Feel free to use these slides verbatim, or to modify
them to fit your own needs. If you make use of a significant portion of these slides in your own
lecture, please include this message, or a link to our web site: http://www.mmds.org

Mining of Massive Datasets
Jure Leskovec, Anand Rajaraman, Jeff Ullman
Stanford University

http://www.mmds.org

 Classic model of algorithms You get to see the entire input, then compute
some function of it In this context, “offline algorithm”
 Online Algorithms

 You get to see the input one piece at a time, andneed to make irrevocable decisions along the way
 Similar to the data stream model

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

2Boys

1a2b3c4dGirls

Nodes: Boys and Girls; Edges: Preferences
Goal: Match boys to girls so that maximum
number of preferences is satisfied
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

4Boys

1a2b3c4dGirlsM = {(1,a),(2,b),(3,d)} is a matching
Cardinality of matching = |M| = 3
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

5Boys

1a2b3c4dGirlsM = {(1,c),(2,b),(3,d),(4,a)} is aperfect matching
Perfect matching … all vertices of the graph are matched
Maximum matching … a matching that contains the largest possible number of matches
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

6 Problem: Find a maximum matching for agiven bipartite graph A perfect one if it exists
 There is a polynomial-time offline algorithm

based on augmenting paths (Hopcroft & Karp 1973,
see http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm)
 But what if we do not know the entire

graph upfront?
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

7 Initially, we are given the set boys
 In each round, one girl’s choices are revealed That is, girl’s edges are revealed At that time, we have to decide to either: Pair the girl with a boy
 Do not pair the girl with any boy
 Example of application:

Assigning tasks to servers

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

8

1a

2b

3c

4

d

(1,a)
(2,b)
(3,d)

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

9 Greedy algorithm for the online graphmatching problem:
 Pair the new girl with any eligible boy
 If there is none, do not pair girl

 How good is the algorithm?

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

10 For input I, suppose greedy produces

matching Mgreedy while an optimal
matching is Mopt
Competitive ratio =minall possible inputs I (|Mgreedy|/|Mopt|)(what is greedy’s worst performance over all possible inputs I)

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

11

Mopt

 Consider a case: Mgreedy≠ Mopt1

 Consider the set G of girls

2b3c4dmatched in Mopt but not in Mgreedy
 Then every boy B adjacent to girls
in G is already matched in Mgreedy:B={}

aG={ If there would exist such non-matched(by Mgreedy) boy adjacent to a non-matched
girl then greedy would have matched them
 Since boys B are already matched in Mgreedy then(1) |Mgreedy|≥ |B|
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

12} Summary so far:

Mopt1a Girls G matched in Mopt but not in Mgreedy23 (1) |Mgreedy|≥ |B|
 There are at least |G| such boysbcd4
B={}

G={(|G| ≤ |B|) otherwise the optimalalgorithm couldn’t have matched all girls in G
 So: |G| ≤ |B| ≤ |Mgreedy|
 By definition of G also: |Mopt| ≤ |Mgreedy| + |G| Worst case is when |G| = |B| = |Mgreedy|
 |Mopt| ≤ 2|Mgreedy| then |Mgreedy|/|Mopt| ≥ 1/2
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org13}

1a2b3c4d(1,a)(2,b)

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

14 Banner ads (1995-2001)

 Initial form of web advertising Popular websites charged
X$ for every 1,000“impressions” of the ad Called “CPM” rate
(Cost per thousand impressions) Modeled similar to TV, magazine ads

CPM…cost per mille
Mille…thousand in Latin

 From untargeted to demographically targeted Low click-through rates
 Low ROI for advertisers
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

16 Introduced by Overture around 2000

 Advertisers bid on search keywords When someone searches for that keyword, thehighest bidder’s ad is shown Advertiser is charged only if the ad is clicked on
 Similar model adopted by Google with somechanges around 2002
 Called Adwords

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

17

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

18 Performance-based advertising works!

 Multi-billion-dollar industry
 Interesting problem:

What ads to show for a given query?
 (Today’s lecture) If I am an advertiser, which search terms

should I bid on and how much should I bid?
 (Not focus of today’s lecture)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

19 Given: 1. A set of bids by advertisers for search queries
 2. A click-through rate for each advertiser-query pair 3. A budget for each advertiser (say for 1 month) 4. A limit on the number of ads to be displayed witheach search query Respond to each search query with a set ofadvertisers such that: 1. The size of the set is no larger than the limit on thenumber of ads per query 2. Each advertiser has bid on the search query 3. Each advertiser has enough budget left to pay forthe ad if it is clicked upon
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

20 A stream of queries arrives at the searchengine: q1, q2, …
 Several advertisers bid on each query When query qi arrives, search engine must
pick a subset of advertisers whose ads areshown Goal: Maximize search engine’s revenues

 Simple solution: Instead of raw bids, use the“expected revenue per click” (i.e., Bid*CTR)
 Clearly we need an online algorithm!
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

21

Advertiser

BidCTR

Bid * CTR

A

$1.00

1%

1 cent

B

$0.75

2%

1.5 cents

C

$0.50

2.5%

1.125 cents

Click throughrate

Expectedrevenue

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

22Advertiser

BidCTR

Bid * CTR

B

$0.75

2%

1.5 cents

C

$0.50

2.5%

1.125 cents

A

$1.00

1%

1 centJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

23 Two complications: Budget CTR of an ad is unknown
 Each advertiser has a limited budget

 Search engine guarantees that the advertiser
will not be charged more than their daily budget

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

24 CTR: Each ad has a different likelihood ofbeing clicked Advertiser 1 bids $2, click probability = 0.1
 Advertiser 2 bids $1, click probability = 0.5
 Clickthrough rate (CTR) is measured historically Very hard problem: Exploration vs. exploitation
Exploit: Should we keep showing an ad for which we havegood estimates of click-through rate
orExplore: Shall we show a brand new ad to get a better
sense of its click-through rate
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

25 Our setting: Simplified environment

 There is 1 ad shown for each query All advertisers have the same budget B
 All ads are equally likely to be clicked Value of each ad is the same (=1)
 Simplest algorithm is greedy: For a query pick any advertiser who has
bid 1 for that query Competitive ratio of greedy is 1/2
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

26 Two advertisers A and B

 A bids on query x, B bids on x and y Both have budgets of $4
 Query stream: x x x x y y y y Worst case greedy choice: B B B B _ _ _ _ Optimal: A A A A B B B B
 Competitive ratio = ½
 This is the worst case!
 Note: Greedy algorithm is deterministic – it always
resolves draws in the same way
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

27 BALANCE Algorithm by Mehta, Saberi,Vazirani, and Vazirani
 For each query, pick the advertiser with thelargest unspent budget
 Break ties arbitrarily (but in a deterministic way)

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

28 Two advertisers A and B

 A bids on query x, B bids on x and y Both have budgets of $4
 Query stream: x x x x y y y y BALANCE choice: A B A B B B _ _ Optimal: A A A A B B B B
 In general: For BALANCE on 2 advertisers

Competitive ratio = ¾
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

29 Consider simple case (w.l.o.g.):

 2 advertisers, A1 and A2, each with budget B (≥1)
 Optimal solution exhausts both advertisers’ budgets
 BALANCE must exhaust at least one

advertiser’s budget: If not, we can allocate more queries Whenever BALANCE makes a mistake (both advertisers bid
on the query), advertiser’s unspent budget only decreases
 Since optimal exhausts both budgets, one will for sure getexhausted Assume BALANCE exhausts A2’s budget,
but allocates x queries fewer than the optimal
 Revenue: BAL = 2B - x
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

30Queries allocated to A1 in the optimal solution

BQueries allocated to A2 in the optimal solution
A1

A2

Optimal revenue = 2B
Assume Balance gives revenue = 2B-x = B+yx
By

(if we could assign to A1 we would since we still have the budget)x
A1

A2 Not
usedx
B
yx
A1

A2 Notused

Unassigned queries should be assigned to A2
Goal: Show we have y ≥ xCase 1) ≤ ½ of A1’s queries got assigned to A2
then   /
Case 2) > ½ of A1’s queries got assigned to A2
then   / and   Balance revenue is minimum for   /
Minimum Balance revenue = /Competitive Ratio = 3/4
BALANCE exhausts A2’s budget

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

31 In the general case, worst competitive ratioof BALANCE is 1–1/e = approx. 0.63
 Interestingly, no online algorithm has a better
competitive ratio!
 Let’s see the worst case example that gives

this ratio

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org32

 N advertisers: A1, A2, … AN Each with budget B > N
 Queries:

 N∙B queries appear in N rounds of B queries each
 Bidding: Round 1 queries: bidders A1, A2,…, AN Round 2 queries: bidders
A2, A3, …, AN Round i queries: bidders
Ai, …, AN Optimum allocation:

Allocate round i queries to Ai
 Optimum revenue N∙B
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

33

…

B/(N-2)
B/(N-1)
B/N

A1A2

A3

AN-1

AN

BALANCE assigns each of the queries in round 1 to N advertisers.
After k rounds, sum of allocations to each of advertisers Ak,…,AN is∑⋯


If we find the smallest k such that Sk ≥ B, then after k rounds
we cannot allocate any queries to any advertiser
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

34

B/1

B/2

B/3 … B/(N-(k-1)) … B/(N-1)

B/N
S1

S2
Sk = B

1/1

1/2

1/3 … 1/(N-(k-1)) … 1/(N-1)

1/N
S1S2
Sk = 1

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

35 Fact: ∑ /    for large n Result due to Euler
1/1

1/2

1/3 … 1/(N-(k-1)) … 1/(N-1)

1/Nln(N)Sk = 1ln(N)-1

 implies:  We also know:  So:   Then:       N terms sum to ln(N).
Last k terms sum to 1.
First N-k terms sumto ln(N-k) but also to ln(N)-1

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

36 So after the first k=N(1-1/e) rounds, wecannot allocate a query to any advertiser
 Revenue = B∙N (1-1/e)
 Competitive ratio = 1-1/e

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

37 Arbitrary bids and arbitrary budgets!
 Consider we have 1 query q, advertiser i Bid = xi
 Budget = bi In a general setting BALANCE can be terrible

 Consider two advertisers A1 and A2
 A1: x1 = 1, b1 = 110
 A2: x2 = 10, b2 = 100
 Consider we see 10 instances of q
 BALANCE always selects A1 and earns 10
 Optimal earns 100
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

38 Arbitrary bids: consider query q, bidder i Bid = xi
 Budget = bi Amount spent so far = mi Fraction of budget left over fi = 1-mi/bi
 Define ψi(q) = xi(1-e-fi)
 Allocate query q to bidder i with largest

value of ψi(q) Same competitive ratio (1-1/e)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

39