Advanced Search Techniques for Large Scale Data Analytics Pavel Zezula and Jan Sedmidubsky Masaryk University http://disa.fi.muni.cz 2 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 1 2 3 4 a b c d Boys Girls 4 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Nodes: Boys and Girls; Edges: Preferences Goal: Match boys to girls so that maximum number of preferences is satisfied M = {(1,a),(2,b),(3,d)} is a matching Cardinality of matching = |M| = 3 1 2 3 4 a b c d Boys Girls 5 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 1 2 3 4 a b c d Boys Girls M = {(1,c),(2,b),(3,d),(4,a)} is a perfect matching 6 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Perfect matching … all vertices of the graph are matched Maximum matching … a matching that contains the largest possible number of matches 7 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 8 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 9 1 2 3 4 a b c d (1,a) (2,b) (3,d) 10 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡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) 11 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡Consider a case: Mgreedy≠ Mopt ¡Consider the set G of girls matched in Mopt but not in Mgreedy ¡Then every boy B adjacent to girls in G is already matched in Mgreedy: §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| ¡ Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 12 a b c d G={ } B={ } Mopt 1 2 3 4 ¡Summary so far: §Girls G matched in Mopt but not in Mgreedy §(1) |Mgreedy|≥ |B| ¡There are at least |G| such boys (|G| £ |B|) otherwise the optimal algorithm 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 ¡ ¡ Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 13 a b c d G={ } B={ } Mopt 1 2 3 4 This is a general proof. We make no assumptions about the structure of the bipartite graph. 1 2 3 4 a b c (1,a) (2,b) d 14 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡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 §From untargeted to demographically targeted §Low click-through rates §Low ROI for advertisers Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 16 CPM…cost per mille Mille…thousand in Latin 17 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) google-results google-ads 18 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 19 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡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 with each search query ¡Respond to each search query with a set of advertisers such that: §1. The size of the set is no larger than the limit on the number of ads per query §2. Each advertiser has bid on the search query §3. Each advertiser has enough budget left to pay for the ad if it is clicked upon Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 20 21 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 22 Advertiser Bid CTR Bid * CTR A B C $1.00 $0.75 $0.50 1% 2% 2.5% 1 cent 1.5 cents 1.125 cents Click through rate Expected revenue ¡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 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 23 ¡CTR: Each ad has a different likelihood of being 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 have good estimates of click-through rate or Explore: Shall we show a brand new ad to get a better sense of its click-through rate Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 24 25 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡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 26 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Is greedy deterministic or randomized (it is deterministic!!) ¡BALANCE Algorithm by Mehta, Saberi, Vazirani, and Vazirani §For each query, pick the advertiser with the largest unspent budget §Break ties arbitrarily (but in a deterministic way) 27 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 28 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 29 Why exhausts budget: -- remember, optimal exhausts both budgets GENERAL PROOF A1 A2 B x y B A1 A2 x Optimal revenue = 2B Assume Balance gives revenue = 2B-x = B+y Queries allocated to A1 in the optimal solution Queries allocated to A2 in the optimal solution Not used 30 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) BALANCE exhausts A2’s budget x y B A1 A2 x Not used Whatever is not used should be assigned to A2 (since if we could assign to A1 we would since we still have the budget) CASE 1) Less than half of A1’s queries got assigned to A2. So y>B/2 CASE 2) If more than half of A1’s queries got assigned to A2. Consider last of A1s queries assigned to A2. At that time B2 > B1. At that time B2 < ½. Since more than half of A1’s queries got assigned to A2 (this means the remaining budget had to be <1/2). So B1<1/2. ¡In the general case with N advertisers, worst competitive ratio of BALANCE is 1–1/e = approx. 0.63 §Interestingly, no online algorithm has a better competitive ratio! 31 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡Customer X §Buys Metallica CD §Buys Megadeth CD ¡Customer Y §Does search on Metallica §Recommender system suggests Megadeth from data collected about customer X classic alive Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 33 http://blog.hubspot.com/Portals/249/images/amazon_logo.gif http://4.bp.blogspot.com/_zmoEeqomXD4/SjftFPB6UTI/AAAAAAAACZE/gxQm5CcUp_k/s400/del.icio.us-logo.jpg http://upload.moldova.org/IT/logos/youtube_logo.gif Items MCBS01705_0000[1] Search Recommendations Products, web sites, blogs, news items, … 34 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Pandora Logo http://scrapetv.com/News/News%20Pages/Business/images-5/netflix-logo.jpg http://www.growyourwritingbusiness.com/images/stumbleupon_logo.bmp http://admintell.napco.com/ee/images/uploads/appletell/618px-Last.fm_logo_.svg_.png Examples: http://upload.wikimedia.org/wikipedia/commons/5/52/Movielens-helping.gif http://blog.ithenticate.com/wp-content/uploads/2010/11/google-news-logo.png http://beefjack.com/files/2010/04/xbox-live-arcade.thumbnail.jpg Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 35 In 1988, a British mountain climber named Joe Simpson wrote a book called Touching the Void, a harrowing account of near death in the Peruvian Andes. It got good reviews but, only a modest success, it was soon forgotten. Then, a decade later, a strange thing happened. Jon Krakauer wroteInto Thin Air, another book about a mountain-climbing tragedy, which became a publishing sensation. SuddenlyTouching the Void started to sell again. Random House rushed out a new edition to keep up with demand. Booksellers began to promote it next to their Into Thin Air displays, and sales rose further. A revised paperback edition, which came out in January, spent 14 weeks on theNew York Times bestseller list. That same month, IFC Films released a docudrama of the story to critical acclaim. NowTouching the Void outsells Into Thin Air more than two to one. What happened? In short, Amazon.com recommendations. The online bookseller's software noted patterns in buying behavior and suggested that readers who liked Into Thin Airwould also like Touching the Void. People took the suggestion, agreed wholeheartedly, wrote rhapsodic reviews. More sales, more algorithm-fueled recommendations, and the positive feedback loop kicked in. Anatomy edit Source: Chris Anderson (2004) Full-size image 36 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 37 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 38 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Avatar LOTR Matrix Pirates Alice Bob Carol David 39 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 40 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 41 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 42 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) ¡Main idea: Recommend items to customer x similar to previous items rated highly by x ¡ ¡Example: ¡Movie recommendations §Recommend movies with same actor(s), director, genre, … ¡Websites, blogs, news §Recommend other sites with “similar” content § Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 44 MCBS01705_0000[1] likes Item profiles Red Circles Triangles User profile match recommend build 45 J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 46 Harnessing quality judgments of other users 48 Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) Figure x N