Intelligente Suchein sehr großen Datenmengen

Holger BastMax-Planck-Institut für Informatik

Saarbrücken

Vortrag an der Universität Mainz5. März 2008

Früher: Klassische theoretische Informatik Komponenten

– feststehende und voll spezifizierte Problemezum Beispiel: gegeben ein Graph,berechne ein maximales Matching

– vollständige Theoremezum Beispiel: für einen zufälligen Graphen,maximales Matching in erwarteter Zeit O (n log n)

– eventuell Experimentezum Beispiel: implementiere den Algorithmus undmesse die Laufzeit auf vielen zufälligen Graphen

Theorie als Selbstzweck – schult präzises Denken / Formulieren / Methodik– selten direkt relevant

HashingSortingSchedulingMatching…

Jetzt: Angewandt auf der Basis guter Theorie Komponenten

– Ausgangspunkt ist eine reale Anwendungentscheidend diese in ihrer Ganzheit zu verstehen

– Abstraktion kritischer Teile (theoretischem Denken zugänglich machen)oft der schwierigste und kreativste Teil

– Algorithmen / Datenstrukturen entwerfen und mathem. analysierenwie in der klassischen Algorithmik, aber …

– Experimente + Algorithm Engineeringzur Ergänzung und Bestätigung der Theorie

– Bau eines (Prototyp-) Systemsultimativer Realitätstest, wichtige Inspirationsquelle

Theorie als Mittel zum Zweck– direkt anwendbare + verlässliche Lösungen– Anwendung geht vor mathematische Tiefe

Überblick Meine Arbeitsweise

– Früher: Klassische theoretische Informatik– Jetzt: Angewandt auf der Basis guter Theorie

Ausgewählte Ergebnisse– Die CompleteSearch Suchmaschine ≈ 20 min– Spektrales Lernen ≈ 10 min– Kürzeste Wege in Straßennetzwerken ≈

10 min Zusammenfassung

– nach jedem Ergebnis

Die CompleteSearch Suchmaschine Hintergrund

– Suchmaschinen sind extrem schnell– auch für sehr großen Datenmengen– aber sie können nur genau eine Sache:

Stichwortsuche Ziel

– komplexere Suchfunktionen– aber genauso schnell

Lösung– kontext-sensitive Präfixsuche– einerseits: sehr mächtig– andererseits: effizient berechenbar

Mögliche Suchanfragen 1/2 Volltextsuche mit Autovervollständigung

– traffic inter* Strukturierte Daten als künstliche Worte

– venue:esa– author:elmar_schömer– year:2007

Datenbankanfragen: select, join, …– venue:esa author:*– venue:esa author:* und venue:sigir author:*

und schneide die Menge der Vervollständigungen (an Stelle der Menge der Dokumente)

Elmar Schömer ESA 2007 paper #23876Michael Hemmer ESA 2007 paper #23876Laurent Dupont ESA 2007 paper #23876… … … …

Mögliche Suchanfragen 2/2 Facettensuche

– automatische Statistik über vordefinierte Kategorien

Verwandte Worte– Suche metal, finde aluminium

Fehlertolerante Suche– Suche probabilistic, finde probalistic

Semantische Suche– Suche politician, finde Angela Merkel

und mehr …

alles mit ein- und demselben Mechanismus

D98E B A

S

D78K L S

D53J D E

A

Formulierung des Kernproblems

D2B F A

D4K L K A B

D9E E R

D27K L D

F

D92P U D E M

D43D Q

D32I L S D H

D1A O E W H D88

P A E G Q

D3Q DA

D17B WU K A

D74J W Q

D13A 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

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

……

D98E B A

S

D78K L S

D53J D E

AD2B F A

D4K L K A B

D9E E R

D27K L D

F

D92P U D E M

D43D Q

D32I L S D H

D1A O E W H D88

P A E G Q

D3Q DA

D17B WU K A

D74J W Q

D13A O E W H

D88P A E G Q

D17B WU K A

D13A 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

Lösung via Invertierter Index (INV) 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 BereichC (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

Grundlegende Idee Berechne invertierte Listen für Bereiche von Worten

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

Beobachtungen– ein Präfix entspricht einem Bereich von Worten– idealerweise Liste für jeden Präfix vorberechnet– aber das kostet viel zu viel Platz– erhebliche Redundanz zwischen den Listen

Liste fürA-D

Lösung 2: AutoTree Baumartige Anordnung Theorem:

– VerarbeitungszeitO(|D| + |output|) (ausgabesensitiv)

– ohne mehr Platz zu verbrauchen als INV

Aber– nicht IO-effizient (wegen Bitvektor Operationen)– suboptimale Kompression

1 1 1 1 1 1 1 1 1 1 …

1 0 0 0 1 0 0 1 1 1 …

1 0 0 1 1 …aa

chen

aach

enad

vanc

ealg

olalg

orith

mad

vanc

eaa

chen

art adva

nce

adva

nce

manne

r

mannin

gmax

imal

maxim

almax

imum

maple

mazza

middle

Lösung 2: AutoTree SPIRE’06 / JIR’07

Trick 1: Relative bit vectors– the i-th bit of the root node corresponds to the i-th doc– the i-th bit of any other node corresponds to the i-th set

bit of its parent node

aachen-zyskowski1111111111111…

maakeb-zyskowski1001000111101…

maakeb-stream1001110…

corresponds to doc 5

corresponds to doc 5

corresponds to doc 10

Lösung 2: AutoTree SPIRE’06 / JIR’07

Tricks 2: Push up the words– For each node, by each set bit, store the leftmost word

of that doc that is not already stored by a parent node

1 1 1 1 1 1 1 1 1 1 …

1 0 0 0 1 0 0 1 1 1 …

1 0 0 1 1 …

aach

enaa

chen

adva

nce

algol

algor

ithm

adva

nce

aach

enart ad

vanc

ead

vanc

e

manne

r

mannin

gmax

imal

maxim

alm

axim

um

maple

mazza

middle

D = 5, 7, 10W = max*

D = 5, 10 (→ 2, 5)report: maximum

D = 5report: Ø → STOP

Lösung 2: AutoTree SPIRE’06 / JIR’07

Tricks 3: divide into blocks– and build a tree over each block as shown before

Lösung 2: AutoTree SPIRE’06 / JIR’07

Tricks 3: divide into blocks– and build a tree over each block as shown before

Solution 2: AutoTree SPIRE’06 / JIR’07

Tricks 3: divide into blocks– and build a tree over each block as shown before

Theorem:– query processing time O(|D| + |output|)– uses no more space than an inverted index

AutoTree Summary:+ output-sensitive– not IO-efficient (heavy use of bit-rank operations)– compression not optimal

Einschub Der invertierte Index ist, 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

schlechte Lokalität

Lokalität + Kompression entscheidendbei sehr großen Datenmengen

Lösung 3: Hybrider Index (HYB) Flache Aufteilung des Vokabulars in Blöcke

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

Liste fürA-D

2 2 3 3 4 4 7 7 8 8 9 9 11E F G J H I I E F G H J I

Liste fürE-J

1 1 2 3 4 5 6 6 6 8 9 9 9 10 10L N M N N K L M N M K L M K L

Liste fürK-N

Gute Lokalität, aber was ist mit Kompression?

Lösung 3: Hybrider Index (HYB) Flache Aufteilung des Vokabulars in Blöcke

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

Definition: Empirische Entropie Empirische Entropie

– … formalisiert die optimale Anzahl Bits die zur Kodierung einer Sequenz benötigt werden

– … für eine Multi-Teilmenge der Größe m aus einem Universum der Größe n m ∙ log (1 + n / m) + n ∙ log (1 + m / n)

– … für eine Folge von n Elementen aus einem Universum der Größe k, mit ni Vorkommen des i-ten Elements n1 ∙ log (n / n1) + ∙∙∙ + nk ∙ log (n / nk)

– usw …

Platzverbrauch: INV gegen HYBTheorem: Die empirische Entropie des INV Index ist

Σ ni ∙ (1/ln 2 + log2(n/ni))Theorem: Die empirische Entropie des HYB Index ist Σ ni ∙ ((1+ε)/ln 2 + log2(n/ni))

ni = number of documents containing i-th word, n = number of documents, ε = 0.1 MEDBOOKS

44,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 GBVOLL-INV 13 MB 0.48 GB 4.6 GBHALB-INV 14 MB 0.51 GB 4.9 GB

perfekte Übereinstimmung von Theorie und Praxis… und HYB etwa 10 mal schneller als INV

Zusammenfassung: CompleteSearch Output

– Publikationen in verschiedenen CommunitiesSIGIR (IR), CIDR (DB), SPIRE (Theorie), GWEM (KI), …

– zahlreiche Industriekontakte, Vortrag bei Google– zahlreiche Installationen, auch kommerzielle DBLP– DFG Projekt im SPP Algorithm Engineering– Dr. Meyer Struckmann Wissenschaftspreis 2007 (15.000

€) Entscheidend waren

– Identifizierung und Formulierung des Präfixsuchproblems– Wahl der Analyseparameter: Lokalität, Komprimierung, etc.

(und zum Beispiel hier nicht: Anzahl der Operationen)– Experimente, Software Engineering, Prototyp– generell: Wissen in vielen relevanten Gebieten (z.B. Ontologien)

Ausblick: Suche Sehr viele theoretisch interessante + praktisch

relevante Probleme im Rahmen von Suche– effiziente(re) Facettensuche, semantische Suche,

etc.– fehlertolerante Suche– Indexkonstruktion– effiziente Erzeugung von „result snippets”– …

Übertragung auf Nicht-Text Retrieval– 3D shape retrieval– Suche in Bildern und Videos– …

Überblick Meine Arbeitsweise

– Früher: Klassische theoretische Informatik– Jetzt: Angewandt auf der Basis guter Theorie

Ausgewählte Ergebnisse– Die CompleteSearch Suchmaschine ≈ 20 min– Spektrales Lernen ≈ 10 min– Kürzeste Wege in Straßennetzwerken ≈

10 min Zusammenfassung

– nach jedem Ergebnis

Spektrales Lernen

1 0 1 0 01 1 0 0 01 1 1 1 00 0 0 1 1

internetwebsurfingbeach

Daten als Objekt-Feature Matrix gegeben– Bilder, Formen, Text, … – z.B. Objekte = Dokumente, Features = Worte

Problem:fehlende Einträge

Spektrales Lernen

1 0 1 0 01 1 0 0 01 1 1 1 00 0 0 1 1

internetwebsurfingbeach

0.8 0.6 0.6 0.1 -0.20.8 0.6 0.6 0.1 -0.21.2 0.9 0.9 0.8 0.3-0.1 0.0 0.0 1.1 0.9

Lösung: Rang-k Approximation

die Approximation erhöht die Präzision

(durch Eigenvektorzerlegung)

Daten als Objekt-Feature Matrix gegeben– Bilder, Formen, Text, … – z.B. Objekte = Dokumente, Features = Worte

Problem:fehlende Einträge

Wann und warum funktioniert das? Vorgängerarbeiten:

Wenn die Objekte durch Kombination von k Basisobjekten generiert und leicht perturbiert werden, dann funktioniert die Rang-k Approximation

– Papadimitriou, Tamaki, Raghavan, Vempala PODS 1998– Ding SIGIR 1999– Thomas Hofmann Machine Learning 2000– Azar, Fiat, Karlin, McSherry, Saia STOC 2001– und viele andere mehr …

Mathematisch interessant (Perturbationstheorie) aber …– in der Regel gibt es keine k natürlichen Basisobjekte– Verbesserung durch Approximation ist extrem intransparent

Alternative Sicht Betrachte die Feature-Feature Korrelations-Matrix

(Objekt-Objekt Korrelations-Matrix ginge genauso gut)

0.8 0.1 0.6 0.10.1 1.1 0.9 0.10.6 0.9 1.1 0.70.1 0.1 0.7 2.0

paarweise Skalarprodukteder norm. Zeilen-Vektoren

beste Rang-2Approximation

intern

et

web surfin

gbe

ach

internetwebsurfingbeach

0.3 0.4 0.3 -0.10.4 0.4 0.3 -0.20.3 0.3 0.4 0.3-0.1 -0.2 0.3 0.8

0.8 0.1 0.6 0.10.1 1.1 0.9 0.10.6 0.9 1.1 0.70.1 0.1 0.7 2.0

die approximierten Korrelationen hängen stark vom Rang ab!

intern

et

web surfin

gbe

ach

internetwebsurfingbeach

0.9 -0.1 0.2 -0.1-0.1 0.8 0.3 -0.20.2 0.3 0.4 0.3-0.1 -0.2 0.3 0.8

Alternative Sicht

paarweise Skalarprodukteder norm. Zeilen-Vektoren

beste Rang-3Approximation

Betrachte die Feature-Feature Korrelations-Matrix(Objekt-Objekt Korrelations-Matrix ginge genauso gut)

Zentrale Beobachtung Abhängigkeit der Korrelation eines festen

Paares vom Rang k der Approximation

node / vertex200 400 6000

Rang der Approximation

logic / logics

200 400 6000Rang der Approximation

logic / vertex

200 400 6000Rang der Approximation

Korre

latio

n

0

kein einzelner Rang ist gut für alle Paare!

Zentrale Beobachtung Abhängigkeit der Korrelation eines festen

Paares vom Rang k der Approximation

node / vertex200 400 6000

Rang der Approximation

logic / logics

200 400 6000Rang der Approximation

logic / vertex

200 400 6000Rang der Approximation

Korre

latio

n

0

kein einzelner Rang ist gut für alle Paare!aber die Form der Kurve scheint ein guter Indikator zu sein

Kurven für verwandte Terme· · · · · 1 1 0 0· · · · · 0 0 1 1· · · · · 1 1 1 10 0 1 1 1 1 0 1 00 0 1 1 1 0 1 0 1

Wir nennen zwei Terme perfekt verwandt wenn sie mit exakt den gleichen Termen vorkommen

200

400

600

0 200

400

600

0 200

400

600

0

Charakteristische Form:

hoch und wieder runter

Die Stelle des Abfalls ist für jedes Term-Paar anders!

Term 1Term 2

0

beweisbare Formim idealisierten Fall

beweisbar kleine Änderung nach kleiner

Perturbation

auf halbem Wegezu einer realen Matrix

Korre

latio

n

Rang der Approximation Rang der ApproximationRang der Approximation

Kurven für nicht-verwandte Terme Ko-Okkurrenz Graph:

– Knoten = Terme– Kanten = zwei Terme kommen

zusammen vor perfekt unverwandt = kein Pfad

200

400

600

0Rang der Approximation

200

400

600

0Rang der Approximation

200

400

600

0Rang der Approximation

Korre

latio

n

0

beweisbare Formim idealisierten Fall

beweisbar kleine Änderung nach kleiner

Perturbation

auf halbem Wegezu einer realen Matrix

Charakteristische Form: Oszillation um Null

Ein einfacher Algorithmus

1. Normalisiere die Term-Dokument Matrix, so dass der theoretische Abfallpunkt für alle Termpaare gleich ist

2. Für jedes Termpaar: falls die Kurve je negativ ist vor diesem Punkt, setze Korrelation auf 1, sonst auf 0

200 400 6000200 400 6000200 400 6000

einfache 0-1 Klassifikation, keine fraktionalen Einträge

setze auf 1 setze auf 1 setze auf 0

0

Korre

latio

n

Rang der Approximation Rang der ApproximationRang der Approximation

Zusammenfassung: Spektrales Lernen Ergebnisse

– Einsicht: Spektrale Lernverfahren funktionieren, indem sie Paare von verwandten Features (Terme) identifizieren

– Integration mit CompleteSearch (inspirierte weitere Forschung)

– dadurch erstmalig transparent– „magisches” Verfahren entzaubert durch Theorie + Empirik

From: Prabhakar Raghavan <pragh@yahoo-inc.com>Date: [after my SIGIR’05 talk]Subject: Very clear talk

Thank you – it’s too easy to make this stuff mystical and you did the opposite

Ausblick: Maschinelles Lernen Spektralzerlegung in diesem Fall nicht

praktikabel– hoher Berechnungsaufwand (Spektralzerlegung)– relativ geringer Nutzen (findet verwandte Paare)

Effizientes Maschinelles Lernen– Entitätenerkennung auf sehr großen Datenmengen– Fehlerkorrektur auf sehr großen Datenmengen– …

Überblick Meine Arbeitsweise

– Früher: Klassische theoretische Informatik– Jetzt: Angewandt auf der Basis guter Theorie

Ausgewählte Ergebnisse– Die CompleteSearch Suchmaschine ≈ 20 min– Spektrales Lernen ≈ 10 min– Kürzeste Wege in Straßennetzwerken ≈

10 min Zusammenfassung

– nach jedem Ergebnis

Kürzeste Wege in Straßennetzwerken Problemstellung

– von einem Start zu einem Ziel (point-to-point)– (un)gerichteter Graph, Kantenkosten = Reisezeiten

Stand der Kunst Dijkstra's Algorithmus

≈ 1 Sekunde pro Anfrage, USA Straßennetzwerk Für wesentlich schnellere Zeiten …

muss das Netzwerk vorverarbeitet werdenspezielle Eigenschaften von Straßennetzwerken

Das bisher beste Verfahren≈ 1 Millisekunde pro Anfrage, USA Netzwerk

Unsere Arbeitzuerst: theoretisch sehr schöner Algorithmusaber: konnten die 1 Millisekunde nicht schlagendann radikal neuer Ansatz: Transitknoten≈ 10 Mikrosekunden pro Anfrage, USA Straßennetzwerk

Sanders et al '04/05/06

Dijkstra '59Luby and Ragde '85

Gutman '04Goldberg et al '05/06

Möhring et al '05Lauther et al '04

Wagner et al '05/06

Thorup and Zwick '01

...

24 Millionen Knoten58 Millionen Kanten

...

Die Transitknoten Idee1. Vorberechnung weniger Transitknoten

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

2. 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 eine dieser nächsten Transitknoten geht

3. Vorberechnung aller Distanzen zwischen allen Paaren von Transitknoten und

von jedem Knoten zu seinen nächsten Transitknoten

Suchanfrage = wenige table lookups !

Vorberechnung der Transitknoten

Von Distanzen zu Pfaden24 min20 min23 min

23

2Start Ziel

Zusammenfassung: Kürzeste Wege Output

– Publikationen: DIMACS’06, ALENEX’07, Science 07– Großes Presseecho: Süddeutsche, Welt, c’t, Chip, …– Patent + zahlreiche Firmenkontakte + …– Heinz Billing Preis für wiss. Rechnen 2007 (mit S. Funke)– Scientific American 50 Award 2007

Charakteristik– Klassisches Problem, aber auf echten Daten– theoretisch schönerer Algorithmus war nicht praktikabel– einfache aber radikal neue Idee, enorme Verbesserung– Verständnis der Besonderheit der Daten entscheidend

Ausblick: Kürzeste Wege Theoretische Untermauerung

– wir haben schon: beweisbar korrekt– aber für genau welche Graphen: beweisbar

effizient? Erweiterungen

– dynamische Änderungen (Staus)– tageszeitabhängige Kantenkosten (rush hour)– Periodische Abfahrts/Ankunftszeiten (Bahn, Bus,

etc.)– …