Fabian M. Suchanek Course material adapted from  Antoine Amarilli , which is based on the slides of the  Web Data Management book . Web Search >introduction
Introduction Crawling Indexing Searching PageRank Business Innovation Overview 2
• Trump is a chump •  Dump Trump! •  Elvis is alive (web) search engine  is a software system that, given a user query, returns a list of Web documents. Def: Search engine 3 User query: Search Engine Result Is Trump a chump? >details
•  In the very beginning:  centralized  list of Web servers     (Example:  DMOZ ) •  Later: only  links  (and URL exchange) to find information  •  Early efforts:  Wanderer W3Catalog  (1993).  •  First search engine with crawling, indexing and searching:     JumpStation  (December 1993).  •   First  search engine:  WebCrawler  (April 1994; brand still active).  •   Lycos  (1994).  •  Search engines proved more successful than hand‐curated  portals •  Nowadays: 93% of Internet traffic from search engines.    (Forrester Research, 2006) Search engines 4 >details
•   Yahoo!  (1994): Initially a  directory •   Excite  (1995).  •   AltaVista  (1995): In 1998, 20 machines, 130~GB RAM,    500 GB HDD, 13M queries/day (150 queries/second). (0) •   Netscape  (1996): Yahoo!, Magellan, Lycos, Infoseek, Excite.  •   Ask Jeeves  (1996): Tentative  natural language  support.  •   Yandex  (1997): Popular in Russia ( 52%  market share as of 2018) •   Google Search  (1997): Invented PageRank.  •   GoTo  (1998): Pay to appear for certain keywords.  •   MSN Search  (1998): Microsoft’s  answer to Google •   Baidu  (2000): Popular in China ( 76%  market share in China)  •   DuckDuckGo  (2008): Privacy‐aware search engine •   Startpage  (2009): Anonymizes Google searches •   Qwant  (2013): French privacy‐aware answer to Google Important search engines 5 >details
As of 2018, according to  NetMarketShare.com Search engine market share 6 Google (72%) Baidu (13%) Bing (7%) Yahoo (4%) Yandex (1%) DuckDuckGo (0.23%), Ask, AOL,... >details
Overview 7 Introduction Crawling Indexing Searching PageRank Business Innovation
Web page 1 Web page 2 Web page 3 Web page 4 Web page 1000 Web page 17 Web page 42 A Search engine 8 Is Trump a chump? User query: Search Engine Result ...
Web Crawler Donald John Trump (born June 14, 1946) is the 45th President of the  United States The United States unites lots of states: Some of the cooler ones are  California  and  New York . Web crawler  is a system that follows hyperlinks, collecting all pages on the way. 9  *click*  *click*  *click* BFS>12 >details
A crawler does BFS on URLs 10 1. Start with queue of important URLs BFS = Breadth First Search http://... http://... http://...
A crawler does BFS on URLs 11 2. Download http://... http://... http://...
A crawler does BFS on URLs 3. If page is “good”, add it to corpus 12 ? http://... http://...
A crawler does BFS on URLs 4. Find URLs in page, enqueue them 13 <a href=XYZ></a> http://... http://... http://...
A crawler does BFS on URLs 5. repeat the process until you covered all pages  • within a certain depth • in a certain domain • with certain topics • . 14 http://... >details http://... http://...
•  In an HTML page   •  Hyperlinks  <a href="...">     •  Media  <img src="..."> <audio src="..."> <video src="..."> <source src="...">     •  Frames  <iframe src="...">     •  JavaScript  window.open("...")  — undecidable in general    •  Page text by  regular expressions . •  In  other kinds  of files (PDFs...).  •  In  sitemaps  provided specifically to crawlers.  •  In  server logs  available online (could include  Referer ).  •  From  existing URLs : parent folder.       =>  Also possible: change GET parameters... Finding new URLs 15 >details
Freshness Problem •  Content on the Web  changes •  Different change rates:       online newspaper main page: every hour or so       published article: virtually no change •   Continuous crawling , and identification of  change rates    for adaptive crawling:        If-Last-Modified  HTTP feature (not reliable)       Identification of duplicates in successive request 16 >details
•  Prevent  multiple indexing  and penalize  content farms •  Prevent duplicate  URLs  by  canonicalization      http://example.com:80/foo       =  http://example.com/bar/../foo       =  http://www.example.com/foo   • Detect  duplicate pages  by using a  hash function . • Detect  near-duplicates  (dates, etc.) by using a  similarity function    (e.g., Broder's  MinHash   from 1997, used in AltaVista).    If you are designing a Web site with multiple legitimate copies      =>  Use  301 redirects  to remove unneeded copies.       =>  Specify the canonical copy using:             <link rel="canonical" href="http://example.com/">   Duplicate pages 17 >details
•  Wait a minimal  delay  between requests to the same server.        =>  Depends on the  server  ( wikipedia.org  vs your laptop).        =>  Depends on the  resource  (large files...).        =>  Generally, waiting at least  one second  is preferable.  •  Requests to different servers can be  parallelized •  Requests should be run  asynchronously •  The HTTP connection should remain  open •  Requests can be  distributed  across multiple machines.  •  Crawlers represent about 20% of Web traffic. Crawl scheduling 18 >details
Crawler traffic Traffic on a3nm.net as of September 2013 (out of 36593 requests). 19 >details
•   Robot Exclusion Standard http://example.com/robots.txt       =>  Only at root level (not available for subfolders).        =>  Filtering by  User-agent       =>   Disallow  directive to forbid certain pages.        =>  Also:  Allow Crawl-delay Host Sitemap •   HTTP header X-Robots-Tag  (less support):        =>   X-Robots-Tag: noindex   •   Meta tag <meta name="robots" content="noindex">        =>  Also  nofollow nosnipped noarchive ...  •   Links <a href="secret/" rel="nofollow">   •   Engine-specific  interfaces (e.g., Google Webmaster Tools).    =>   No guarantees ! Robot control (honor-based) 20 >details
•  Completely Automated Public Turing test to tell Computers    and Humans Apart (trademarked by CMU, but patented by AltaVista).  •  Making a  computer  able to recognize humans.  •   Accessibility  problems for the blind (mitigated by alternatives) •  Can be any AI problem: add two numbers,    listen to a word, recognize an animal in an image, etc. Robot control with CAPTCHAs How can we discriminate against  robots ? 21 >details
CAPTCHAs can be used to • digitize books   Show one word that we know (to validate the user),   and one word that we want to digitize (to digitize the book) • Show ads   Ask the user to type a slogan • Do recognition of street numbers in   Google street view images ReCAPTCHAs 22 >details
•  Employ humans to remotely solve CAPTCHAs    (“sweatshops”, hundreds per hour) •  Sometimes there may be no ground truth •  Optical character recognition has improved and can     solve some CAPTCHAs Breaking CAPTCHAs 23 >details
spider trap  (also: crawler trap, robot trap) is a set of web pages that  cause a web crawler to make an infinite number of requests or cause a poorly constructed crawler to crash.  [Wikipedia/Spider trap] January 1st • no meetings next> <prev Spider traps can be intentional or unintentional. Can be used to trap spiders that do not follow robots.txt :-) “Robot Control” by Spider Traps 24 Example: http://foo.com/bar/foo/bar/foo/bar/foo/bar/..... >details
We can use an existing Web crawl ClueWeb CommonCrawl Internet Archive 25 1b 25 TB 6b 100TB 2b 80TB pages size
Overview 26 Introduction Crawling Indexing Searching PageRank Business Innovation
Web page 1 Web page 2 Web page 3 Web page 4 Web page 1000 Web page 17 Web page 42 A Search engine 27 Will Trump slump? User query: Search Engine Result ... How does this work?
Web page 17 Web page 42 Trump: page 1, page 17, page 42, page 13, ... slump: page 5, page 17, page 42, page 300, ... music: page 2, page 20, page 500, ... ... A Search engine 28 User query: Search Engine Result Will Trump slump?
The  index of a search engine  (also: inverted index) is a map from words to Web documents (and potentially more information). Search Engine Index 29 Search Engine >details >whichWords Trump: page 1, page 17, page 42, page 13, ... slump: page 5, page 17, page 42, page 300, ... music: page 2, page 20, page 500, ... ...
<html>   <head>     <title>Words that rhyme with Trump</title>     <meta charset=UTF-8>     <script>        ...     </script>   </head>   <body>      <h1>Words that rhyme with Trump</h1>      There are lost of words that rhyme with “Trump”, for example      ... Which words go into the index? 30 >details >whichWords
• The  content  of the page.    (importance could be  weighted : headers, emphasized text...) •  The  <title> •  The page  URL •   Meta tags     •   <meta name="description" content="My website">             ( used  by Google snippets).      •   <meta name="keywords" content="great,website">             (not used by Google).      •   Engine-specific <meta name="google" ...>     •  Semantic annotations with  RDFa/JSON-LD   •  Other  file formats . 31 Which words go into the index? >details >whichWords
•  Use  meta-information  (may not be reliable).  •  Look at  characters  (not specific enough).  •  Look at the  frequent k-grams  and classify.        =>  Surprisingly reliable. Language identification Compare: th awarting problecon inge pria notobe inguarguarew for andes so col th anciped the cons ors lessolat reatencle behas nuarocialso by in as the re laturocalis com ad ble of th the in congto res wortionnetesers a with: encer desemps our parcellecon le de grarts is bale diatincyclossibles inats res ne de le catictiont pectionne cofon les des sour dand communes mation parchivell pedique de dontanduismes ce sour les pages ent inse 32 >details
doc1: "This Web page explains why Trump is so grumpy." doc2: "Is Trump a crump or a frump?" doc3: "Words that rhyme are fine" We clean up our Web documents so that they consist of only the parts that we want to index. This yields the  document collection : Document collection 33 >details >Tokenization
token  is a string of one or more characters that is significant as a group. The process of splitting a string into tokens is called  tokenization . [Wikipedia/Token] Tokenization 34 doc1: This, Web, page, explains, why, Trump, is, so, grumpy, . doc2: Is, Trump, a, crump, or, a, frump, ? doc3: Words, that, rhyme, are, fine >details >Tokenization
Challenges:  •  Absence of  whitespace  to separate words in some languages •   Entities  such as acronyms, numbers, URLs, emails, units, etc.  •   Word boundaries  (“host name” or “hostname”?) 35 >Tokenization doc1: This, Web, page, explains, why, Trump, is, so, grumpy, . doc2: Is, Trump, a, crump, or, a, frump, ? doc3: Words, that, rhyme, are, fine >details token  is a string of one or more characters that is significant as a group. The process of splitting a string into tokens is called  tokenization . Tokenization
• We remove  punctuation • We remove  capitalization Normalization 36 doc1: this, web, page, explains, why, trump, is, so, grumpy doc2: is, trump, a, crump, or, a, frump doc3: words, that, rhyme, are, fine >details
production, produced, produce, producer -> produc The  stem  of a word is the part of the word that is common to all its inflected variants. [Paul Kroeger (2005). Analyzing grammar. Cambridge University Press. p. 248.] The  lemma  of a word is its canonical form, as it appears in a dictionary. [Wikipedia/Lemma] go, goes, went -> go Stem, Lemma 37 >details >Stemming
•   Morphological  stemming:     •   Remove : plural, gender, tense, mood...      •   Irregularities : “mouse”/“mice”.      •   Problem: Ambiguities : “stocking”, “rose”, “couvent” (French).  •   Lexical  stemming      •   Derived terms : “policy”, “politics”, “political”...           =>  The most popular algorithm is Porter Stemmer •   Semantic  stemming:     •   Merge  synonyms or near-synonyms. (Not always relevant.) •   Phonetic  stemming:     •   Merge  words that sound similarly to account for        spelling mistakes. Eg., for English,  Soundex  stems         Robert  and  Rupert  to  R163 . Stemming  is the process of replacing a word by a normalized form (the stem or the lemma, depending on the application). Stemming 38 >details >Stemming
Stemming Example 39 doc1: this, web, page, explains, why, trump, is, so, grumpy doc2: is, trump, a, crump, or, a, frump doc3: words, that, rhyme, are, fine >stopwords Stemming  is the process of replacing a word by a normalized form (the stem or the lemma, depending on the application).
Stemming Example 40 doc1: this, web, page, explain, why, trump, is, so, grump doc2: is, trump, a, crump, or, a, frump doc3: words, that, rhyme, are, fine >stopwords Stemming  is the process of replacing a word by a normalized form (the stem or the lemma, depending on the application).
Stopword stopword  is a word that is common in a corpus but has little value for searching. (The definition of stopwords is application‐dependent. This one is from  Postgres .) Is  Trump  a  crump  or a  slump?  This  question makes people jump. 41 Example Usually all words are stopwords, except • nouns, • adjectives • non‐auxiliary verbs >details >stopword details
Stopword Rationale Imagine we search for How many cats do the Simpsons have? List of Simpson cats: ... Here we do explain how many teeth the chicken have. 42 >details
Stopword Rationale Imagine we search for How many cats do the Simpsons have? List of Simpson cats: ... Here we do explain how many teeth the chicken have. 43 Overlap: 5 Overlap: 2
Stopword Rationale Imagine we search for cats Simpsons? List of Simpson cats: ... Here we do explain how many teeth the chicken have. 44 Overlap: 0 Overlap: 2 >details
Stopword removal We  remove stopwords  from our document collection. 45 doc1: this, web, page, explain, why, trump, is, so, grump doc2: is, trump, a, crump, or, a, frump doc3: words, that, rhyme, are, fine >details
Stopword removal =>  Storing the index takes  less space =>  Processing is  faster 46 doc1: web, page, explain, trump, grump doc2: trump, crump, frump doc3: words, rhyme, fine We  remove stopwords  from our document collection.
Overview 47 >motiv TF-IDF Introduction Crawling Indexing Searching PageRank Business Innovation
Ideas for Relevance: TF-IDF 48 doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump Query: Will Trump slump?
Ideas for Relevance: TF-IDF 49 doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump Query: Will Trump slump? The  term frequency    is proportion of terms in   that are  (The more   appears in  , the more   is  relevant  for  .)
The  inverse document frequency    is the logarithm of the inverse proportion of documents of   where   occurs.  (The rarer   is, the more informative it is.) Ideas for Relevance: TF-IDF 50 The  term frequency    is proportion of terms in   that are  (The more   appears in  , the more   is  relevant  for  .) doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump Query: Will Trump slump?
TF-IDF  is the following measure for the importance of a document given a query term: : term : document : document collection : number of occurrences of   in  TF-IDF 51 with >task doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump Query: Will Trump slump?
Compute TF and IDF values for this document collection: Task: TF-IDF 52 trump slump TF TF doc1 doc2 TF-IDF TF-IDF IDF ... doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump
Compute TF and IDF values for this document collection: Task: TF-IDF 53 TF TF doc1 doc2 TF-IDF TF-IDF IDF ... trump slump doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump
trump : doc1/0.02, doc2/0.08, ... slump : doc1/0, doc2/0, ... ... 54 TF-IDF in the index The TF-IDF values are commonly stored in the index. >Fagin & Map Reduce >Fagin doc1:  trump slump , garden, flower, water, sun doc2:  trump, trump slump doc3:  slump slump trump doc4: dog,  slump , cat,  slump , cow,  slump
elvis: doc2/0.15, doc1/0.11,  ... pelvis: doc1/0.05, doc2/0.03, ... ... =>  Finding the top-k documents for a single term query is very easy! 55 Index stores terms by decr. TF-IDF The documents are sorted by decreasing TF-IDF in each list. Query: elvis find top-k documents >Fagin & Map Reduce >Fagin
If a query consists of multiple keywords  we need an  aggregation function , which computes the score of a document from the tf-idf scores of the keywords: The aggregation function should be  monotonic . Common choices are  sum prod min max e.g.:  score(doc1,<elvis,pelvis>) = 0.11 + 0.05 56 Multi‐keyword queries Query: elvis, pelvis elvis: doc2/0.15, doc1/0.11,  ... pelvis: doc1/0.05, doc2/0.03, ... ... >Fagin & Map Reduce >Fagin
Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,... Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists doc1  OK this document has been seen in all lists. 57 Fagin’s Algorithm
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists doc1  OK doc2 doc4 58 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists doc1  OK doc2 doc4 doc3  OK 59 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists doc1  OK doc2  OK doc4 doc3  OK doc7 60 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists doc1  OK doc2  OK doc4 doc3  OK doc7 k documents have been seen in all lists => stop 61 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists •  For all documents that you have seen in any list so far,    write down its tf-ids for each keyword, and its score doc1  OK doc2  OK doc4 doc3  OK doc7 62 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists •  For all documents that you have seen in any list so far,    write down its tf-ids for each keyword, and its score doc1  OK doc2  OK doc4 doc3  OK doc7 We saw these values anyway already during our scan. 63 Fagin’s Algorithm Obama drama score 0.10 0.08 0.08 0.05 0.07 0.05 0.06 0.05 Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,... drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,...
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists •  For all documents that you have seen in any list so far,    write down its tf-ids for each keyword, and its score doc1  OK doc2  OK doc4 doc3  OK doc7 64 Fagin’s Algorithm score 0.10 0.08 0.08 0.05 0.07 0.05 0.06 0.05 0.05 0.02 0.18 0.13 0.12 0.11 0.07 Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,..., doc7/0.05 drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,..., doc4/0.02 Obama drama
Given: inverted index, integer k, keywords •  Scan the lists for the keywords top-down in parallel    until k documents have been seen in all lists •  For all documents that you have seen in any list so far,    write down its tf-ids for each keyword, and its score •  Output the top k documents with highest score doc1  OK doc2  OK doc4 doc3  OK doc7 65 Fagin’s Algorithm score 0.10 0.08 0.08 0.05 0.07 0.05 0.06 0.05 0.02 0.18 0.13 0.11 0.07 0.05 0.12 Obama drama >Fagin & Map Reduce >Fagin
Fagin’s algorithm scans the lists only until we saw k documents in all lists. Why is this sufficient? See also: http://alumni.cs.ucr.edu/~skulhari/Top-k-Query.pdf 66 Fagin’s Algorithm Query: Obama drama, k=3 Obama: doc1/0.10, doc2/0.08, doc3/0.05, doc7/0.05,..., doc9/0.04 drama:  doc1/0.08, doc4/0.07, doc3/0.06, doc2/0.05,..., doc9/0.04 >Fagin & Map Reduce >Task
elvis:    doc4/0.20, doc2/0.15, doc3/0.01, doc6/0.0, doc5/0.0 pelvis:  doc3/0.15, doc4/0.10, doc5/0.05, doc2/0.02 Given: inverted index, integer k, keywords • Scan the lists for the keywords top-down in parallel   until k documents have been seen in all lists • For all documents that you have seen in any list so far,   write down its tf-ids for each keyword, and its score • Output the top k documents with highest score 67 Task: Fagin’s Algorithm Query: elvis pelvis, k=2
score Given: inverted index, integer k, keywords • Scan the lists for the keywords top-down in parallel   until k documents have been seen in all lists • For all documents that you have seen in any list so far,   write down its tf-ids for each keyword, and its score • Output the top k documents with highest score 68 Task: Fagin’s Algorithm => doc4, doc2 doc4 doc3 doc2 doc5 elvis pelvis elvis:    doc4/0.20, doc2/0.15, doc3/0.01, doc6/0.0, doc5/0.0 pelvis:  doc3/0.15, doc4/0.10, doc5/0.05, doc2/0.02 Query: elvis pelvis, k=2 >Map Reduce
doc1 doc2 docn 69 Computing IDF in parallel ... >Map Reduce
doc1 doc2 docn 70 Computing IDF in parallel ...
doc1 doc2 docn (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t9, docn) (t1, docn) ... 71 Computing IDF in parallel ...
doc1 doc2 docn (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t9, docn) (t1, docn) ... (t1,(doc1,doc7,docn)) 72 Computing IDF in parallel ... (t2, (doc1, doc2)) ... (tm, (...)) group by terms
doc1 doc2 docn (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t9, docn) (t1, docn) ... (t1,(doc1,doc7,docn)) (t1, log(n/3)) 73 Computing IDF in parallel ... group by terms (t2, (doc1, doc2)) ... (tm, (...)) >Map Reduce
doc1 doc2 docn (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t9, docn) (t1, docn) ... (t1,(doc1,doc7,docn)) (t1, log(n/3)) (tm, log(n/...)) (t2, log(n/2)) 74 Computing IDF in parallel ... group by terms (t2, (doc1, doc2)) ... (tm, (...))
doc1 doc2 (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t1,(doc1,doc7,docn)) (t1, log(n/3)) (t2, log(n/2)) Map the input to (key, value) pairs Group by key: (key, (value1, ...)) Reduce the value list to an aggregate value (key, aggregate) 75 The Map Reduce Framework group by terms (t2, (doc1, doc2)) >Map Reduce
doc1 doc2 (t1, doc1) (t2, doc1) ... (t7, doc2) (t2, doc2) ... (t1,(doc1,doc7,docn)) (t1, log(n/3)) (t2, log(n/2)) How to distribute the tasks to machines? How to group the data by keys? How to distribute the work? 76 Challenges in MapReduce (t2, (doc1, doc2)) >Map Reduce
•  MapReduce is a framework for  distributed computing •  Published by  Google  in 2004: model and proprietary implementation.  •  Apache  Hadoop : open source implementation.  •  Express your task in terms of:       Map : Operations to run in parallel      Reduce : Operations to aggregate results of Map steps •  The MapReduce implementation takes care of:      •   Scheduling  the various operations.      •   Dispatching  the jobs to the various workers.      •   Monitoring  the jobs and  restarting  failed jobs.      •   Moving  the computation results around. Def: MapReduce 77
Overview 78 Introduction Crawling Indexing Searching PageRank Business Innovation >intro
•  Developed by  Larry Page  and  Sergey Brin , 1996.    (Initially a research project at  Stanford •   Patent  (assigned to Stanford University,     but Google has exclusive license rights).  •  Main idea: Use the  links  on the Web    to estimate the  importance  of pages.     =>  Precompute this  independently  from the query.      =>  (Also: distribute it massively on  cheap  machines.) •  Related idea:  hubs and authorities PageRank  is an algorithm that determines the importance of a Web page based on its links to other Web pages — independently of the query. PageRank 79
The  Web graph  is a graph where the nodes are Web pages and there is an edge from  x  to  y  iff page  x  contains a link to page  y . Web graph 80 <a href="http://b.com"> http://a.com/index.html http://b.com/index.html <a href="http://a.com"> http://c.com/index.html <a href="http://c.com"> <a href="http://c.com"> >graph
directed graph  is a set of “nodes” (also: Vertices)  and a relation of “edges”  . Graph 81 a b c >graph
The  adjacency matrix  of a graph (V,E) is a matrix  with  .     a  b  c a  0  1  1 b  1  0  1 c  0  0  0 Adjacency matrix 82 a b c
Intuitively, a page is more important if it has many incoming links from important pages.