Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,CS 345Data Mining,Online algorithms,Search advertising,Online algorithms,Classic model of algorithms,You get toseethe entireinput,then computesomefunctionof it,In this context,“offlinealgorithm,”,”,Online algorithm,You get toseethe inputone pieceat atime,andneedto make irrevocabledecisionsalongtheway,Similar todatastream models,Example:Bipartite matching,1,2,3,4,a,b,c,d,Girls,Boys,Example:Bipartite matching,1,2,3,4,a,b,c,d,M=(1,a),(2,b),(3,d)is amatching,Cardinality ofmatching=|M|=3,Girls,Boys,Example:Bipartite matching,1,2,3,4,a,b,c,d,Girls,Boys,M=(1,c),(2,b),(3,d),(4,a)is a,perfect matching,Matching Algorithm,Problem:Find amaximum-cardinalitymatchingfor agiven bipartite graph,A perfectone if itexists,Thereis apolynomial-time offlinealgorithm(Hopcroftand Karp 1973),But what if wedonthavetheentire graph upfront?,Online problem,Initially,we are given the set Boys,In each round,one girlschoices are revealed,At that time,we have todecide toeither:,Pairthe girl with aboy,Dontpairthegirlwithany boy,Example ofapplication:assigning tasksto servers,Online problem,1,2,3,4,a,b,c,d,(1,a),(2,b),(3,d),Greedy algorithm,Pairthe new girl with any eligibleboy,If thereisnone,dontpairgirl,Howgoodisthealgorithm?,CompetitiveRatio,Forinput I,supposegreedyproducesmatching M,greedy,while anoptimalmatching isM,opt,Competitiveratio=,min,allpossibleinputsI,(|M,greedy,|/|M,opt,|),Analyzing the greedyalgorithm,ConsiderthesetG of girlsmatchedin M,opt,butnotin M,greedy,Thenitmustbethecasethat everyboyadjacenttogirls inG is already matched inM,greedy,There must be atleast|G|suchboys,Otherwise the optimal algorithmcould not have matched all the Ggirls,Therefore,|M,greedy,|,|G|=|M,opt,-M,greedy,|,|M,greedy,|/|M,opt,|,1/2,Worst-case scenario,1,2,3,4,a,b,c,(1,a),(2,b),d,Historyof web advertising,Banner ads(1995-2001),Initial formof web advertising,Popular websites chargedX$for every 1000,“,“impressions”ofad,Called,“,“CPM”rate,Modeled similar toTV,magazine ads,Untargeted to demographicallytageted,Low clickthrough rates,low ROI foradvertisers,Performance-basedadvertising,Introduced by Overture around2000,Advertisers,“,“bid”on search keywords,When someonesearches for thatkeyword,the highest biddersad isshown,Advertiser is charged only ifthe adis clickedon,Similar model adopted byGoogle withsomechanges around 2002,Called,“,“Adwords”,Ads vs.search results,Web 2.0,Performance-basedadvertisingworks!,Multi-billion-dollar industry,Interestingproblems,What ads toshow for a search?,If Iman advertiser,which search terms shouldI bidon andhow much tobid?,Adwords problem,A stream ofqueries arrives atthe searchengine,q1,q2,Several advertisers bidon each query,When query q,i,arrives,search engine must pick a subsetof advertisers whose adsare shown,Goal:maximize search enginesrevenues,Clearly we need anonline algorithm!,Greedyalgorithm,Simplest algorithmis greedy,Its easy tosee that the greedy algorithmis actuallyoptimal!,Complications(1),Each ad hasa differentlikelihood of being clicked,Advertiser 1bids$2,click probability=0.1,Advertiser 2bids$1,click probability=0.5,Clickthroughratemeasured historically,Simplesolution,Instead of raw bids,usethe“expected revenue per click”,The AdwordsInnovation,Advertiser,Bid,CTR,Bid*CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1 cent,1.5 cents,1.125cents,The AdwordsInnovation,Advertiser,Bid,CTR,Bid*CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1 cent,1.5 cents,1.125cents,Complications(2),Each advertiser has a limitedbudget,Searchengine guaranteesthatthe advertiser will notbe charged more than their daily budget,Simplified model(for now),Assumeall bids are 0 or1,Each advertiser has thesame budgetB,One advertiser perquery,Letstry the greedy algorithm,Arbitrarilypick an eligible advertiser for eachkeyword,Bad scenariofor greedy,Two advertisers Aand B,A bidson query x,B bids on xand y,Both have budgetsof$4,Querystream:xxxxyyyy,Worstcase greedychoice:BBBB_,Optimal:AAAABBBB,Competitiveratio=,Simpleanalysis shows this isthe worst case,BALANCE algorithmMSVV,Mehta,Saberi,Vazirani,andVazirani,For each query,pick theadvertiserwith the largest unspentbudget,Breakties arbitrarily,Example:BALANCE,Two advertisers Aand B,A bidson query x,B bids on xand y,Both have budgetsof$4,Querystream:xxxxyyyy,BALANCE choice:ABABBB_,Optimal:AAAABBBB,Competitiveratio=,Analyzing BALANCE,Consider simple case:two advertisers,A,1,and A,2,eachwithbudgetB(assume B,1),Assumeoptimal solutionexhausts both advertisers budgets,BALANCE mustexhaust atleastone advertisers budget,If not,we can allocatemore queries,AssumeBALANCE exhaustsA,2,s budget,Analyzing Balance,A,1,A,2,B,x,y,B,A,1,A,2,x,Opt revenue=2B,Balance revenue=2B-x=B+y,We have y,x,Balance revenue isminimum forx=y=B/2,Minimum Balance revenue=3B/2,CompetitiveRatio=3/4,Queries allocatedto A,1,in optimal solution,Queries allocatedto A,2,in optimal solution,General Result,In thegeneral case,worst competitive r