Map Reduce

• Map Reduce erklaeren (auswendig lernen)
  • Map Reduce ist ein Programmiermodell und die Implementierung davon, mit dem die riesigen Datenmengen parallel verarbeitet werden koennen
  • Skaliert sich horizontal auf vielen Nodes
  • Daten müssen unabhängig werden
  • Mappers transform input into intermediate records to process - apply some function to data
  • Reducers aggregate a list of intermediate values for each key - reduce the list of values to one value
  • Main idea: enable scalable computations and hide the system complexity from programmer
• Wann ist MapReduce anwendbar, wann ist nicht?
  • Verarbeitung der Daten kann dann mit Map Reduce geschehen, wenn die Verarbeitung sich in unabhängige Teilprobleme aufteilen lässt.
• Warum muessen die Daten unabhaengig sein?
  • Mapper arbeitet mit den Daten auf einem Node
  • Wenn es eine Abhangigkeit gibt, soll der Mapper erweiterte Logik haben und auf die Ergebnisse von anderen Mappers warten
  • In worst case werden die Daten sequenziell abgearbeitet → kein Sinn
• Alle Schritte von MapReduce nennen und erklaeren (auswendig lernen)
  • Split - die Daten auf Map-Nodes aufteilen (in Hadoop is done by distribured file system)
  • Map - berechne Key-Value Paaren aus Daten (in jedem Node) (e.g for each word w create pair (w, 1))
  • Shuffle and Sort - Key-Values Paare von Mappers nach Key in Reducers zusammenfassen, in jedem Reducer sortieren nach Key (nicht Sorting von Values mit einem Key)
  • Reduce - die Daten auf Reduce-Nodes mit gleichem Key aggregieren (e.g sum)
  • Combine - Ergebnisse von Reduce-Nodes zusammenfassen
• Why do we need sort after shuffle in Map Reduce?
  • Sorting guarantees that the Reducer can efficiently iterate over its input, processing all values associated with a single key before moving on to the next key.
• Alle Schritte von MapReduce and Wordcount Beispiel zeigen
  • Input: Text
  • Split: Teile von Text werden zwischen Mappers geteilt
  • Map: Für jedes Wort w with ein Key-Value Paar (w, 1) erstellt
  • Shuffle and Sort: Alle Wörter mit gleichem Key werden auf einem Reducer gesammelt
  • Reduce: Reducer berechnet die Summer von Values fuer jedes Key
  • Combine: Die Ergebnisse von mehreren Reducers werden gesammelt

PageRank

• PageRank erklaeren (auswendig lernen)
  • Iterativer Algorithmus, der die Wichtigkeit von Webseiten anhang von Links bestimmt, die auf die Webseiten zeitgen
• Was sagt PageRank aus?
  • PageRank zeigt, wie wichtig ist Node in einem Graphen, anhand von In-Links und Out-Links.
  • Falls eine Webseite viele Out-Links hat, ist Gewicht von diesen Links klein
  • Falls eine Webseite wird von keiner Webseite mit grossem PR verlinkt, ist PR von dieser Webseite auch klein.
• Warum hatte Google die Interesse an Entwicklung von PageRank?
  • To rank web pages in seqrch engine results. Measure of the importance of website pages

Simple PageRank

• Kurze Formel fuer PageRank schreiben (auswendig lernen)

  • Simplified PageRank for node u is the sum all page ranks of nodes that point to u divided by the number of their outboud links

  • Initial PageRank is evenly (uniformly) distributed

  • Formula describes equilibrium: iterate until convergence

  • After first iteration, if node has no inbound links, PR of this node is 0

    

• MapReduce teile von Pagerank erklaeren

  • Map muss auf unabhaengigen Daten berechnet werden
  • Alle PRs fest
  • Map: for each outgoing link: key-value pair (Target, Current Node Value / Current Node Out Links)
  • Reduce: for each key: concatenate list of all values

  

• Was sind Dead Ends?

  • Node with no outbound edges
  • Page or a set of pages that do not link out to any other page.
  • Impact on PageRank: distrupts flow of page rank, never contributes to a PR sum
  • Example: A blog archive page that doesn’t link back to the blog homepage or other blog posts, effectively stopping the flow of link equity
  • Page Rank von allen verbundenen Nodes wird zum 0 konvergieren (this form of convergence is not meaningful or useful for the purpose of ranking pages)
  • PR wird absorbiert

  

• Was sind Spider Traps?

  • Groups with only interconnected nodes
  • Never contributes to a PR sum outside group
  • PR for non-group nodes converges to zero

  

• Wann kann PageRank nicht konvergieren?

  • Dead ends: PR fliest in Dead End, dann 0 überall
  • Spider Traps: Gruppe absorbiert PR, außer Gruppe 0 überall
  • Oder wenn Graph einen Bottleneck hat (node der Starkes eingehendes PR hat, und dann weiter viele ausgehende Links hat) → mehrere Zyklen die ueber einem gemeinsamen Node laufen

• Graphen gegeben? Spider Traps und Dead Ends identifizieren

  • Keine Dead Ends
  • Keine Spider Traps
  • Hier ist A aber Bottleneck