40
Über Routenplanung und Suchmaschinen Holger Bast Max-Planck-Institut für Informatik Saarbrücken, Germany Vorlesung zur Lehrerweiterbildung in Informatik Schloss Dagstuhl, 14. Dezember 2007

Über Routenplanung und Suchmaschinen

  • Upload
    yosefu

  • View
    36

  • Download
    0

Embed Size (px)

DESCRIPTION

Über Routenplanung und Suchmaschinen. Holger Bast Max-Planck-Institut für Informatik Saarbrücken, Germany. Vorlesung zur Lehrerweiterbildung in Informatik Schloss Dagstuhl, 14. Dezember 2007. Henning Peters. Debapriyo Majumdar. Ingmar Weber. Alexandru Chitea. Marjan Celikik. - PowerPoint PPT Presentation

Citation preview

Page 1: Über Routenplanung  und Suchmaschinen

Über Routenplanung und Suchmaschinen

Holger BastMax-Planck-Institut für Informatik

Saarbrücken, Germany

Vorlesung zur Lehrerweiterbildung in InformatikSchloss Dagstuhl, 14. Dezember 2007

Page 2: Über Routenplanung  und Suchmaschinen

Meine Gruppe am MPI Informatik

AlexandruChitea

DebapriyoMajumdar

MarjanCelikik

IngmarWeber

HenningPeters

DanielFischer

IvanPopov

MarkusTetzlaff

Bis vor kurzem

– 2 Doktoranden, 5 Diplomanden, 2 Hilfskräfte

GabrielManolache

Page 3: Über Routenplanung  und Suchmaschinen

Kooperationspartner aus den letzten 3 Jahren

Kooperationen innerhalb des MPII

Page 4: Über Routenplanung  und Suchmaschinen

Überblick

Teil 1: Routenplanung

– Grundlagen: Dijkstras Algorithmus

– kurze Pause

– Fortgeschrittenere Verfahren

Pause

Teil 2: Suchmaschinen

– wir bauen eine Suchmaschine

– kurze Pause

– CompleteSearch

genug Zeit für Diskussionen und Fragen!

Page 5: Über Routenplanung  und Suchmaschinen

Teil 1: Routenplanung

Grundlegendes

– Dijkstras Algorithmus (10 min)

– Korrektheitsbeweis (10 min)

– Bidirektionaler Dijkstra (5 min)

– Warum nicht ausreichend (5 min)

Techniken zur Beschleunigung

– A* + Landmarks (10 min)

– „Straßenschilder” (10 min)

– Highway Hierarchies (10 min)

– Transitknoten Routing (10 min)

Pause

!

Page 6: Über Routenplanung  und Suchmaschinen

Das Kürzeste Wege Problem

Gegeben ein Netzwerk

– Knoten und (gewichtete) Kanten

Berechne den kürzesten Weg

– zwischen zwei Knoten s und t (point to point, P2P)

– von einem Knoten s aus zu allen anderen (single source shortest path, SSSP)

– zwischen allen Knotenpaaren (all-pairs shortest path, APSP)

2

31

2

3

2

1

1

Page 7: Über Routenplanung  und Suchmaschinen

Dijkstras Algorithmus

Absolut grundlegend

– kein Navigationsgerät und keine „Maps” Applikation, bei der nicht in irgendeiner Phase dieser Algorithmus verwendet wird

– löst das single-source shortest-path (SSSP) Problem

– point-to-point (P2P) Problem nicht einfacher

Erfinder

– Edsger Dijkstra, 1930 – 2002

Demo

– http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm

Page 8: Über Routenplanung  und Suchmaschinen

Dijkstras Algorithmus — Pseudo Code

1 for each node u 2 dist[u]: = infinity 3 dist[s] := 0 4 PQ = all nodes 5 while PQ is not empty 6 u := node from PQ with smallest dist[u] (get and remove it) 7 for each neighbor v of u 8 d := dist[u] + cost(u,v) 9 if d < dist[v]10 dist[v] := d

die einzige nicht-triviale

Operation

Page 9: Über Routenplanung  und Suchmaschinen

Dijkstras Algorithmus — Korrektheit

s

tuv

Definiere

– dist(s,u) = Kosten des kürzesten Weges von s nach u

Angenommen dist[t] ≠ d(s,t)

1. sei u der erste Knoten von s aus mit dieser Eigenschaft

2. sei v der Knoten davor, somit dist[v] = d(s,v) ≤ d(s,u) < dist[u]

3. dann ist v vor u bearbeitet worden (in Zeile 6)

4. dann ist dist[u] ≤ dist[v] + cost(v,u) = d(s,u)

Betrachte ein Ziel t und den kürzesten Weg dorthin

Widerspruch zu 1.

Page 10: Über Routenplanung  und Suchmaschinen

Zeile 6

– die Operation heißt delete-min

– wird genau einmal für jeden der n Knoten ausgeführt

Zeilen 8 – 10

– die Operation in Zeile 10 heißt decrease-key

– wird höchstens einmal für jede der m Kanten ausgeführt

Insgesamt also

– n * cost(delete-min) + m * cost(decrease-key)

– trivial: cost(delete-min) ~ n und cost(decrease-key) ~ 1

– geht auch: cost(delete-min) ~ 1 und cost(decrease-key) ~ log n

– Laufzeit dann ~ n + m * log n

Dijkstras Algorithmus — Laufzeit

Page 11: Über Routenplanung  und Suchmaschinen

Straßengraphen …

… sind auch Netzwerke

– Knoten = Kreuzungen

– Kanten = Straßen

– Kantengewichte = Reisezeiten

Typische Straßengraphen

– USA: 24 Millionen Knoten, 58 Millionen Kanten

– Westeuropa: 18 Millionen Knoten, 42 Millionen Kanten

– Deutschland: 4 Millionen Knoten, 11 Millionen Kanten

Mit Dijkstras Algorithmus

– durchschnittliche Zeit für zufällig gewähltes Start und Ziel:

mehrere Sekunden auf ganz USA oder Europa

Wie kann man das beschleunigen?

Page 12: Über Routenplanung  und Suchmaschinen

Bidirektionaler Dijkstra

Dijkstra kann man sich auch so vorstellen

– bei Entfernung d

– werden d2 Knoten besucht

Bidirektionaler Dijkstra

– bei Entfernung d

– werden 2 * (d/2)2 =

d2/2 Knoten besucht

Gewinn nur grob ein Faktor 2

Page 13: Über Routenplanung  und Suchmaschinen

Der A* (A-Stern) Algorithmus

Für ziel-orientiertere Suche (auf einen Knoten t hin)

– Annahme: für jeden Knoten u ein Wert h[u] der schätzt wie weit es von dort zum Ziel ist

– Bedingung: h[u] unterschätzt die Entfernung zum Ziel

Algorithmus

– wie Dijkstra, aber Reihenfolge der Knoten (Zeile 6)

nicht gemäß dist[u]

sondern gemäß dist[u] + h[u]

– wenn all h[u] = 0 gerade Dijkstra Algorithmus

Page 14: Über Routenplanung  und Suchmaschinen

A* Algorithmus — Korrektheit

Selbe Idee wie bei Dijkstra

s

tuv

Aber aufpassen

– Übungsaufgabe …

Page 15: Über Routenplanung  und Suchmaschinen

A* Algorithmus — wie schätzen?

Einfacher Schätzer:

– Luftlinie zum Ziel mit Autobahngeschwindigkeit

– nicht sehr effektiv

Landmarks

– ca. 20 strategisch wichtige Punkte auf der Karte

– für jeden solchen Punkt L untere Schranke

max(d(s,L) – d(t,L) , d(t,L) – d(s,L)) [Bild malen!]

– von 1 Sekunde 1 Millisekunde

(auf dem Straßengraphen der USA der Westeuropas)

Erfinder

– Andrew Goldberg, Microsoft Research

Page 16: Über Routenplanung  und Suchmaschinen

Highway Hierarchies

Idee: Auf langen Reisen fährt man (meistens) – erst auf die nächste Hauptstraße

– dann auf Bundesstraßen

– dann auf Autobahnen

– und in der Nähe des Ziels dasselbe anders herum

Algorithmus (High-Level)– berechne eine Hierarchie von wichtigeren und

wichtigeren Straßen, mit der Garantie dass die Strategie oben immer zum optimalen Weg führt

– von 10 Millisekunden 1 Millisekunde

Erfinder– Peter Sanders (lange MPI Informatik, jetzt U.

Karlsruhe)

– Dominik Schultes (Doktorand von P. Sanders)http://algo2.iti.uni-karlsruhe.de/schultes/hwy/demo/applet.html

Page 17: Über Routenplanung  und Suchmaschinen

Transitknoten

Sehr einfache Grundidee

– wenn man weit weg fährt, verlässt man seine nähere Umgebung durch einen von relativ wenigen Verkehrsknotenpunkten

– versuche diese Knotenpunkte (= Transitknoten) vorzuberechnen

– und alle paarweisen Distanzen zwischen ihnen

Das mit Abstand schnellste Verfahren

– von 1 Millisekunde 10 Mikrosekunden

(für das Straßennetzwerk der USA oder Westeuropas)

Erfinder

– Holger Bast & Stefan Funke, MPI Informatik

Page 18: Über Routenplanung  und Suchmaschinen

Transitknoten — Vorberechnung

Vorberechnung weniger Transitknoten

– mit der Eigenschaft, dass jeder kürzeste Pfad über eine gewisse Mindestdistanz durch einen Transitknoten geht

Vorberechnung der nächsten Transitknoten für jeden Knoten

– mit der Eigenschaft, dass jeder kürzeste Pfad über eine gewisse Mindestdistanz von diesem Knoten aus durch ein dieser nächsten Transitknoten geht

Vorberechnung aller Distanzen

– zwischen allen Paaren von Transitknoten undvon jedem Knoten zu seinen nächsten Transitknoten

Suchanfrage = wenige table lookups !

Page 19: Über Routenplanung  und Suchmaschinen

Pause

Page 20: Über Routenplanung  und Suchmaschinen

Teil 2: Suchmaschinen

Wir bauen eine Suchmaschine (live)

– Crawling (5 min)

– Parsing (10 min)

– Invertierung (5 min)

– Suchanfragen (10 min)

– Web interface (5 min)

Die CompleteSearch Suchmaschine

– Prinzip am Beispiel erklären (10 min)

– was man damit alles machen kann (20 min)

– Datenstrukturen + Experimente (10 min)

Pause!

Page 21: Über Routenplanung  und Suchmaschinen

Webseiten herunterladen (Crawling)

Eingabe

– eine Liste von URLs

Ausgabe

– HTML Dateien, eine für jede der URLs

Implementierung

– wir benutzen einfach curl (oder wget)

Page 22: Über Routenplanung  und Suchmaschinen

Zerlegung in Worte (Parsing)

Eingabe

– die HTML Dokumente aus dem Crawling

Ausgabe

– eine Textdatei index.words mit Zeilen der Form

Wort Dokumentennummer

dies 15ist 15ein 15satz 15

– eine Textdatei index.docs mit Zeilen der Form

DokumentennummerURL

15 http://www.dagstuhl.de/abc16 http://www.dagstuhl.de/xyz

Page 23: Über Routenplanung  und Suchmaschinen

Invertierung

Eingabe

– die (Wort, Dokumentennummer) Paare

nach Dokumentennummer sortiert

Ausgabe

– dieselben Paare

nach Worten sortiert (und innerhalb desselben Wortes nach Dokumentennummer)

– damit bekommen wir so etwas wie den Index am Ende eines Buches, aber für jedes Wort

– ein sogenannter Volltextindex

Page 24: Über Routenplanung  und Suchmaschinen

Suchanfragen (Queries)

Eingabe

– eine Liste von Worten (durch Leerzeichen getrennt)

Ausgabe

– die Liste aller Dokumente, die alle diese Worte enthalten

Implementierung

– für jedes Wort holen wir uns die vorberechnete Liste aller Nummern von Dokumenten, die es enthalten

– dann berechnen wir die Schnittmenge aller dieser Listen

– Komplexität = linear in der Größe der Liste

viel kleiner als die Dokumentenmenge insgesamt!

Page 25: Über Routenplanung  und Suchmaschinen

Ein einfacher Web-Server

Eingabe– eine URL im Broswer, z.B.

http://search.mpi-inf.mpg:8080/xyz

– veranlasst dass eine Verbindung mit dem Rechner search.mpi-inf.mpg.de aufgebaut wird

und folgende Zeichenkette an den Port 8080 geschickt wird (default ist Port 80)

GET /xyz HTTP/1.1

Ausgabe– das Programm, dass auf search.mpi-inf.mpg.de

läuft und auf Port 8080 lauscht, schickt etwas zurück

– typischerweise eine HTML Datei

– die dann im Browser angezeigt wird

Page 26: Über Routenplanung  und Suchmaschinen

CompleteSearch

Geschichte

– entwickelt am Max-Planck-Institut für Informatik

– über die letzten drei Jahre

– unter meiner Leitung

– mehrere Diplom- und Doktorarbeiten

– zahlreiche Veröffentlichungen & Vorträge

– voll einsatzfähige Suchmaschine

Zahlreiche Demonstratoren

– http://search.mpi-inf.mpg.de

Page 27: Über Routenplanung  und Suchmaschinen

Anwendung 1: Autovervollständigung

Nach jedem Tastendruck …

– … zeige die besten Vervollständigungen des zuletzt eingegebenen Wortes, sowie die besten Treffer dafür

– z.B., für die Suchanfrage user interface joy zeige

joystickjoysticksetc.

und entsprechende Treffer

Page 28: Über Routenplanung  und Suchmaschinen

Anwendung 2: Fehlerkorrektur

Wie vorher, aber zeige zusätzlich …

– … Varianten bez. Schreibweise der Vervollständigungen die zu einem Treffer führen

– z.B. soll für die Suchanfrage probabilistic algorithm auch ein Dokument mit probalistic aigorithm als Treffer gelten

Realisierung

– angenommen, aigorithm kommt als Fehlschreibung von algorithm vor, dann für jedes Vorkommen von aigorithm im Index

aigorithm Doc. 17

füge ebenso hinzu

algorithm::aigorithm Doc. 17

Page 29: Über Routenplanung  und Suchmaschinen

Anwendung 3: Ähnliche Worte

Wie vorher, aber zeige zusätzlich …

– … Worte die sinngemäß dasselbe bedeuten wie ein der Vervollständigungen

– z.B., für die Anfrage russia metal betrachte auch Dokumente mit russia aluminium

Implementation

– für beispielsweise jedes Vorkommen von aluminium im Index

aluminium Doc. 17

füge hinzu (pro Vorkommen)

s:67:aluminium Doc. 17

sowie (einmal für alle Dokumente)

s:aluminium:67 Doc. 00

Page 30: Über Routenplanung  und Suchmaschinen

Anwendung 4: Facettensuche

Wie vorher, aber zeige zusätzlich …– … eine Statistik bezüglich diverser Kategorien (wie oft

welche Kategorie vorkommt)

– z.B. für die Anfrage algorithm zeige (prominente) Autoren von Artikeln die dieses Wort enthalten

Realisierung– z.B. für einen Artikel von Roswitha Bardohl, der in der

Zeitschrift Theoretical Computer Science in 2007 erschienen ist, füge hinzu

author:Roswitha_Bardohl Dok. 17 venue:TCS Dok. 17 year:2007 Dok. 17

– sowie auch (zur Vervollständigung von Kategoriennamen)

roswitha:author:Roswitha_Bardohl Dok. 17 bardohl:author:Roswitha_Bardohl Dok. 17etc.

Page 31: Über Routenplanung  und Suchmaschinen

Anwendung 5: Semantische Suche

Wie vorher, aber zeige zusätzlich …

– … “semantische” Vervollständigungen

– z.B. für die Suchanfrage audience pope politician zeige individuelle Politiker (nicht das Wort politician) die zusammen mit den Worten audience pope vorkommen

Realisierung

– man kann nicht einfach für jedes Vorkommen einer Entität alle Kategorien hinzufügen, zu denen diese Entität gehört, z.B. Angela Merkel ist

politician, german, female, human being, organism, chancellor, adult, member of parliament, …

– Lösung: trickreiche Kombination mit sogenannten “joins” und es gibt noch mehr Anwendungen …

Page 32: Über Routenplanung  und Suchmaschinen

D98

E B A S

D98

E B A S

D78

K L S

D78

K L SD53

J D E A

D53

J D E A

Formulierung des Kernproblems

D2

B F A

D2

B F A

D4

K L K A B

D4

K L K A B

D9

E E R

D9

E E R

D27

K L D F

D27

K L D F

D92

P U D E M

D92

P U D E M

D43

D Q

D43

D Q

D32

I L S D H

D32

I L S D H

D1

A O E W H

D1

A O E W H

D88

P A E G Q

D88

P A E G Q

D3

Q DA

D3

Q DA

D17

B WU K A

D17

B WU K A

D74

J W Q

D74

J W Q

D13

A O E W H

D13

A O E W H

D13 D17 D88 …

C D E F G

Daten gegeben als

– Dokumente mit Worten

– Dokumente haben Ids (D1, D2, …)

– Worte haben Ids (A, B, C, …)

Suchanfrage

– sortierte Liste von Dok. Ids

– Intervall von Wort Ids

Treffer für “traffic”

Worte die mit “inter” beginnen

Page 33: Über Routenplanung  und Suchmaschinen

Daten gegeben als

– Dokumente mit Worten

– Dokumente haben Ids (D1, D2, …)

– Worte haben Ids (A, B, C, …)

Suchanfrage

– sortierte Liste von Dok. Ids

– Intervall von Wort Ids

Antwort

– alle passenden Wort-in-Dok. Paare

– mit Scores

D13E0.5 0.2 0.7

D88E

D98

E B A S

D98

E B A S

D78

K L S

D78

K L SD53

J D E A

D53

J D E A

D2

B F A

D2

B F A

D4

K L K A B

D4

K L K A B

D9

E E R

D9

E E R

D27

K L D F

D27

K L D F

D92

P U D E M

D92

P U D E M

D43

D Q

D43

D Q

D32

I L S D H

D32

I L S D H

D1

A O E W H

D1

A O E W H

D88

P A E G Q

D88

P A E G Q

D3

Q DA

D3

Q DA

D17

B WU K A

D17

B WU K A

D74

J W Q

D74

J W Q

D13

A O E W H

D13

A O E W H

D88

P A E G Q

D88

P A E G Q

D17

B WU K A

D17

B WU K A

D13

A O E W H

D13

A O E W H

D13 D17 D88 …

C D E F G

D88G

Formulierung des Kernproblems

“kontext-sensitive Präfixsuche”

Treffer für “traffic”

Worte die mit “inter” beginnen

Page 34: Über Routenplanung  und Suchmaschinen

Lösung über invertierte Listen

Zum Beispiel, traffic inter*

gegeben die Dokumente: D13, D17, D88, … (Treffer für traffic)

und der Wortbereich: C D E F G (Ids für inter*)

Iteriere über alle Worte aus dem gegebenen Bereich

C (interaction) D8, D23, D291, ...

D (interesting) D24, D36, D165, ...

E (interface) D13, D24, D88, ...

F (interior) D56, D129, D251, ...

G (internet) D3, D15, D88, ...

Schneide jede Liste mit der gegebenen und vereinige alle Schnitte

D13 D88 D88 …E E G …

typischerweisesehr viele

Listen!

Ziel: schneller ohne mehr Platz zu verbrauchen

im worst casequadratische Komplexität

Page 35: Über Routenplanung  und Suchmaschinen

Einschub

Die invertierten Listen sind, trotz quadratischer worst-case Komplexität, in der Praxis schwer zu schlagen

– sehr einfacher Code

– Listen sehr gut komprimierbar

– perfekte Zugriffslokalität

Anzahl der Operationen ist ein trügerisches Maß

– 100 disk seeks benötigen ca. eine halbe Sekunde

– in der Zeit können 200 MB Daten gelesen werden(falls komprimiert gespeichert)

– Hauptspeicher: 100 nichtlokale Zugriffe 10 KB am Stück

Daten

Page 36: Über Routenplanung  und Suchmaschinen

Neu: Halb-Invertierte Listen

Listen von Dokument-Wort Paaren (sortiert nach Dok. Id)

A-D:1 3 3 5 5 6 7 8 8 9 11 11 11 12 13 15

D A C A B A C A D A A B C A C A

flache Partitionierung Alternative: hierarchisch

– z.B. eine Liste für A-D, eine Liste für E-H, etc.

Eigenschaften– einfach + perfekte Lokalität + sehr gut komprimierbar(!)

Suchanfragen– bei geeigneter Partitionierung, immer genau eine Liste

– extrem schnell: Ø 0.1 Sekunde / Anfrage für TREC Terabyte

(426 GB Rohdaten, 25 Millionen Dokumente)

Page 37: Über Routenplanung  und Suchmaschinen

Halb-Invertierte Listen: Komprimierung

Dok. Ids Differenzen und Wort Ids Häufigkeitsränge

1 3 3 5 5 6 7 8 8 9 11 11 11 12 13 15D A C A B A C A D A A B C A C A

+1 +2 +0 +2 +0 +1 +1 +1 +0 +1 +2 +0 +0 +1 +1 +23rd 1st 2nd 1st 4th 1st 2nd 1st 3rd 1st 1st 4th 2nd 1st 2nd 1st

Kodiere alle Zahlen universell: x log2 x Bits+0 0 +1 10 +2 110

1st (A) 0 2nd (C) 10 3rd (D) 111 4th (B) 110

10 110 0 110 0 10 10 10 0 10 110 0 0 10 10 110111 0 10 0 110 0 10 0 111 0 0 110 10 0 10 0

Was schließlich gespeichert wird

Page 38: Über Routenplanung  und Suchmaschinen

Ergebnis Platzverbrauch

HOMEOPATHY44,015 Dok.

263,817 Wortemit Positionen

WIKIPEDIA 2,866,503 Dok.

6,700,119 Worte mit Positionen

TREC .GOV 25,204,013 Dok.

25,263,176 Worte ohne Positionen

Orig.größe 452 MB 7.4 GB 426 GB

VOLL-INV 13 MB 0.48 GB 4.6 GB

HALB-INV 14 MB 0.51 GB 4.9 GB

perfekte Übereinstimmung von Theorie und Praxis

Definition– empirische Entropie einer Datenstruktur = optimale

Anzahl Bits die zur Kodierung benötigt werden Theorem

– empirische Entropie von HALB-INV mit Blockgröße ε∙n ist 1+ε mal die empirische Entropie von VOLL-INV

Experimente (mit konkretem Kodierungsverfahren)

Page 39: Über Routenplanung  und Suchmaschinen
Page 40: Über Routenplanung  und Suchmaschinen

Zusammenfassung: CompleteSearch

Output

– Publikationen in verschiedenen Communities

SIGIR (IR), CIDR (DB), SPIRE (Theory), GWEM (KI), …

– zahlreiche öffentliche Installationen DBLP

– Industriekontakte

Entscheidend waren

– Identifizierung und Formulierung des Präfixsuchproblems

– Wahl der Analyseparameter: Lokalität, Komprimierung, etc.

(und zum Beispiel hier nicht: Anzahl der Operationen)

– generell: Wissen in vielen relevanten Gebieten