TU München, Institut für Informatik Lehrstuhl für Effiziente Algorithmen

Schwerpunktprogramm (SPP) 1307
der Deutschen Forschungsgemeinschaft (DFG)

Algorithm Engineering

Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching

Zusammenfassung

Im diesem Forschungsprojekt soll das gesamte Spektrum des Algorithm Engineering Prozesses auf Indexstrukturen für fehlertolerante Mustersuche (Approximate Pattern Matching) angewendet werden. Im Gegensatz zur exakten Mustersuche klafft im Bereich der fehlertoleranten Mustersuche eine große Lücke zwischen Theorie und Praxis, die durch das Projekt geschlossen werden soll. Die Ansätze, welche in den letzten Jahren theoretische Fortschritte gebracht haben, scheinen aufgrund großer Konstanten in der Praxis nicht relevant zu sein. Eine Algorithmen-Bibliothek soll anderen Wissenschaftlern, Informatikern wie fachfremden Forschern, effiziente Verfahren zur fehlertoleranten (indexbasierten) Mustersuche zur Verfügung stellen. Die Bibliothek soll eine Schnittstelle für die fortlaufende Weiterentwicklung der Indizes und Algorithmen darstellen. Die Implementierungen liefern eine Arbeitsgrundlage für den weiteren Algorithm Engineering Prozess, sollen aber auch von Nicht-Informatikern, z.B. von Biologen, zur Lösung realer Probleme, z.B. zur Auswertung biologischer Daten, verwendet werden können. Insbesondere soll die Bibliothek Indexstrukturen und Suchalgorithmen bereitstellen, die unter folgenden Gesichtspunkten entworfen und optimiert wurden:

• Effiziente Anwendbarkeit auf reale, große Probleminstanzen unter Verwendung möglichst allgemeiner Fehlermodelle.
• Indexstrukturen und Suchalgorithmen im Sekundärspeicher.
• Verteilte Indexstrukturen und Suchalgorithmen.
• Cache-effiziente Suchalgorithmen.

Stand der Forschung und eigene Vorarbeiten

Ziele und Arbeitsprogramm

Literatur

Mitarbeiter

• Prof. Dr. Ernst W. Mayr (Projektleiter)
• Stefan Eckhardt
• Johannes Nowak
• Dr. Hanjo Täubig