Kurzvorstellung der AGAlgorithmen und Komplexität

MPI Informatik

zur SFB-InitiativeIntelligente Organisation und Suche von

Informationen

Holger Bast

Überblick

Themen

– String Matching

– Externer Speicher

– Geometrische Suche

Methoden

Ideen

String Matching

Ergebnisse (J. Kärkkäinen, S. Burkhardt)

– Schnelle Suche durch Indexdatenstruktur und Filterverfahren

Geplant

– generische Bibliothek von String-Matching-Algorithmen (es existiert nichts in der Art bisher!)

SFB-Relevanz

– grundlegendes Problem bei Textsuche

– SFB-interne Anwendung

adeabbcdeefgabegffabedefgceabadcabcegef

3 Teilstrings mit Editierdistanz 1 zu abcde

Externer Speicher

Ergebnisse (U. Meyer, A. Crauser)

– Externspeicher-effiziente Graphensuche

– Bibliothek LEDA-SM, u.a. ES-effiziente Suffixarrays

Geplant (P. Sanders, R. Dementiev)

– ES-effiziente Varianten der STL Datentypen & Algorithmen

SFB-Relevanz

– grundlegendes Problem bei großen Datenmengen

CPUschnell, aber begrenzt

langsamer, blockweiser Zugriff

Geometrische Suche

Ergebnisse (M. Hagedoorn)

– praktisch & asymptotisch effiziente Datenstruktur

Geplant

– Implementierung & Tests in IR-Umgebung

SFB-Relevanz

– Ähnlichkeitssuche in “feature spaces” = geometrische Suche

Methoden

vom Algorithmus zum Programm

– exakte Analyse (konstante Faktoren)

– experimentelle Analyse

– genauere Modelle, z.B. Cache-Effekte

Bibliotheken

– LEDA, LEPs, CGAL, AGD, BALL, …

– wiederverwendbar

– flexibel, trotzdem effizient und leicht zu verwenden (generische Programmierung)

Hierarchische Volltext-Suche

Suche in medizinischer Datenbank

stechender Schmerz in der Nabelgegend?

Typischer Query

Schmerz stechend Nabelgegend

– findet z.B. nicht “es tut weh in der Nähe des Nabels”

– trotzdem 53 Treffer “fallacy of abundance”

Verzeichnis Beschwerden Schmerzen Nabelgegend stechend– Kategorien a priori

– notorisch veraltet

Hierarchische Volltext-Suche

… Weltschmerz … 7.437 docs … Schmerztabletten … 2.217 docs … Halsschmerzen … 310 docs … Schmerzen am Nabel … 117 docs

… Schmerz, am Nabel der Welt … 34 docs … dumpfer Schmerz am Nabel … 17 docs … bohrender Schmerz am Nabel … 14 docs

Welche Formulierungen kommen vor?

– flache Suche skaliert nicht: Schmerz hat 87.432 Treffer

– Idee: Hierarchie der tatsächlich vorkommenden Phrasen

Hierarchische Volltext-Suche Vorarbeiten (Nevill-Manning, Witten, Moffat, …)

– Hierarchie mehrfach vorkommender Phrasen in Linearzeit

Offene Fragen

– Suchtiefe logarithmisch?

– Externspeicher-Effizienz?

– Semantische Zusatzinformation?

– Synthese verschiedenartiger Hierarchien?

SFB-Relevanz

– viele Möglichkeiten, die symbolische Ebene mit der Verständnisebene zu kombinieren

Ende!

Softwarebibliotheken viel Erfahrung

– LEDA (fundamentale Alg. und Dat.)

– LEPs (externer Speicher, …)

– CGAL (geometrische Alg. und Dat.)

– AGD (Graphzeichnen)

– EXACUS (Geometrie mit Kurven)

– …

Methodik

Algorithmus

Analyse

Programm

Experimente

String Matching mit Fehlern

Ergebnisse (J. Kärkkäinen, S. Burkhardt)

– erst exaktes Matching von Teilmustern, z.B. ab?d, bc?e

– approx. Matching nur wo viele Treffer

adeabbcfeefgabegffacedefgceaadcabbdfgef

Vorkommen von abcde mit 2 Fehlern

x x x xx xx x xxxxx x x xx xxx

String Matching mit Fehlern Geplant

– generische Bibliothek von String-Matching-Algorithmen (es existiert nichts in der Art bisher!)

SFB-Relevanz

– grundlegendes Problem

– konkrete Anwendung in anderen Teilprojekten!

Externer Speicher

Ziel: minimale Anzahl I/O-Operationen (Blockzugriffe)

Ergebnisse (U. Meyer, A. Crauser)

– I/O-effiziente Graphensuche

– LEDA-SM, u.a. I/O-effiziente Suffixarrays

CPU

schnell, aberbegrenzte Kapazität

viel langsamer, blockweiser Zugriff

Externer Speicher Geplant (P. Sanders, R. Dementiev)

– I/O-effiziente Varianten der STL Datentypen & Algorithmen

SFB-Relevanz

– grundlegendes Problem bei riesigen Datenmengen

– SFB-interne Anwendung!

Externer Speicher

Ziel: minimale Anzahl I/O-Operationen (= Blockzugriffe)

Ergebnisse (U. Meyer, A. Crauser)

– I/O-effiziente Graphensuche, LEDA-SM Bibliothek

Geplant (P. Sanders, R. Dementiev)

– I/O-effiziente Varianten der STL Datentypen & Algorithmen

SFB-Relevanz

– grundlegendes Problem bei großen Datenmengen

CPU

schnell, aberbegrenzte Kapazität

langsamer, blockweiser Zugriff

Methodik

vom Algorithmus zum Programm

– exakte Analyse

– genauere Modelle, z.B. Cacheeffekte

– Bibliotheken: LEDA, LEPs, CGAL, AGD, BALL, …

generische Programmierung

– flexibel, trotzdem effizient und leicht zu verwenden

– z.B. match(string, pattern, myKernel)

myKernel implementiert Iterator und Vergleich