Ziele und Arbeitsprogramm
Ziele
Im beantragten Teilprojekt 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 zumindest teilweise geschlossen werden
soll. Die Ansätze, welche in den letzten Jahren theoretische
Fortschritte gebracht haben (siehe
Stand der Forschung), scheinen nicht praktisch
relevant zu sein: Zum Einen sind die in den asymptotischen Schranken
(für Speicherplatz und/oder Suchzeit) versteckten konstanten (und
logarithmischen) Faktoren extrem groß, meist exponentiell in der
erlaubten Fehlerzahl; zum Anderen sind Implementierungen wegen der
komplizierten Indexstrukturen schwierig, d.h. aufwändig und daher
fehleranfällig. Ad-hoc-Lösungen
, wie sie für die exakte
Indexsuche weit verbreitet sind, verbieten sich für die
fehlertolerante Mustersuche schließlich schon deswegen, weil dadurch
jegliche Flexibilität bezüglich der Fehlerfunktionen verloren geht.
Außerdem gibt es nach unserem Wissen noch keine experimentellen
Studien, die sich mit der Leistung der moderneren Indexstrukturen für
fehlertolerante Suche in der Praxis beschäftigen. Demgegenüber
scheinen Indexstrukturen, die nicht auf approximatives Pattern
Matching spezialisiert sind, wie zum Beispiel Suffixbäume, auch bei
der fehlertoleranten Suche in der Praxis gute Resultate zu liefern.
Nichtsdestotrotz sehen wir hier erhebliches Verbesserungspotential.
Ziel des Projekts ist es, eine Bibliothek zu erstellen, die Indexstrukturen und Algorithmen für die fehlertolerante Mustersuche zur Verfügung stellt. Die Bibliothek soll mehr als eine Sammlung verschiedener Indizes und Suchalgorithmen für approximatives Pattern Matching werden. Die im Laufe des Projekts in die Bibliothek integrierten Indizes und Suchalgorithmen sollen robust, flexibel und effizient sein. Die Anwendbarkeit der erarbeiteten Methoden für die Proteinstruktursuche (PAST) ist dabei von spezieller Bedeutung.
Die Bibliothek soll eine Schnittstelle für die
fortlaufende Weiterentwicklung der Indizes und Algorithmen darstellen.
Einerseits stellen die Implementierungen die Arbeitsgrundlage für den
Algorithm Engineering Prozess dar, auf der anderen Seite soll die
Bibliothek aber auch Daten für aussagekräftige Experimente liefern.
Diese Generierungsfähigkeit
soll fester Bestandteil der Bibliothek
werden: reale und synthetische (unter verschiedenen Modellen) Daten,
denen beim Testen von Algorithmen und Indizes im Algorithm Engineering eine immer größere Bedeutung zukommt,
werden somit in einer Art Black-Box
dem Benutzer zur Verfügung gestellt.
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; insbesondere für die Proteinstruktursuche im Rahmen von PAST.
- Indexstrukturen und Suchalgorithmen im Sekundärspeicher.
- Verteilte Indexstrukturen und Suchalgorithmen.
- Cache-effiziente Suchalgorithmen.
Etwas außerhalb dieses zentralen Projektziels liegt ein weiteres Teilprojekt, die Analyse der Smoothed Complexity [ST04] von Trie-Datenstrukturen. Hierbei liegt der Fokus auf der Erklärung des Verhaltens dieser Datenstrukturen auf realen Datensätzen, die nicht zufällig sind, auf denen Tries aber dennoch Leistungsmerkmale (z.B. logarithmische Höhe) aufweisen, die bisher nur mit Average-Case-Analyse erklärt werden konnten.
Arbeitsprogramm
Wie bereits im vorherigen Abschnitt erwähnt, ist die Erstellung einer robusten, flexiblen und effizienten Bibliothek für Indexstrukturen und Suchalgorithmen zur fehlertoleranten Mustersuche das zentrale Ziel dieses Forschungsvorhabens. Ausgangspunkt hierfür ist die Implementierung und sorgfältige experimentelle Evaluation der bekannten Methoden. Wie bereits im vorherigen Abschnitt erläutert, sind Ad-hoc-Lösungen nicht zu robusten und flexiblen Anwendungen im Bereich des approximativen Pattern Matchings erweiterbar, selbst wenn sie für Einzelfälle zufriedenstellende und effiziente Lösungen darstellen.
Aus diesem Grund sollen die folgenden Themenkomplexe genauer
untersucht werden: Im Bereich der Indexstrukturen sollen zunächst
einmal vor allem Suffixbäume, Suffixarrays und allgemeine
Trie-Datenstrukturen als Standardindizes, aber auch schon
Datenstrukturen, die bezüglich einer Verwendung im Sekundärspeicher
optimiert sind, also String-B-Trees, Suffixbäume mit entsprechendem
Layout und Prefix-Partitioned Look-Up Trees, in die Bibliothek
aufgenommen werden. Erste zu implementierende Suchalgorithmen finden
sich in der Literatur (siehe dazu die Algorithmen, die im Abschnitt
Stand der Forschung
unter lineare Indexstrukturen
beschriebenen Arbeiten). Die experimentelle Evaluation dieser Indizes
und Algorithmen ist Ausgangspunkt für das weitere Algorithm
Engineering. Die verwendeten Eingabeinstanzen dieser Evaluation
sollen nicht nur als Rückkopplung zur weiteren Verbesserung der zu
entwickelnden Indizes und Algorithmen verwendet, sondern auch anderen
Wissenschaftlerinnen und Wissenschaftlern zur Verfügung gestellt
werden: Die zu erstellende Bibliothek soll einen Instanzengenerator
enthalten, der zum einen Real-World Instanzen und zum anderen
synthetische Instanzen (unter verschiedenen Modellen) erzeugt.
Wir wollen an dieser Stelle betonen, dass die Bibliothek das Kernstück des gesamten Forschungsprojektes darstellt. Insbesondere hat die Bibliothek große Bedeutung und ist Voraussetzung für alle im folgenden genannten Teilprojekte. Die Ergebnisse der Teilprojekte wiederum beeinflussen und verändern die Bibliothek, so dass sich diese stets in dynamischem Wandel befindet.
| Bibliothek für fehlertolerante indexbasierte Textsuche | |||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
||||||||||||||||||||||
|
|||||||||||||||||||||||
Experimentelle Analyse fehlertoleranter Indexstrukturen
Die Bedeutung der experimentellen Analyse im Algorithm Engineering Prozess wird in der Beschreibung des Schwerpunktprogramms hinreichend betont. Gerade bei den Indexstrukturen für fehlertolerante Mustersuche gibt es aber nach unserem Wissen keine aktuellen experimentellen Studien. Als wichtiger Punkt unserer geplanten Forschung soll diese Lücke geschlossen werden.
Zunächst sollen die oben beschriebenen Ansätze sorgfältig getestet werden. Da es hier besonders wichtig ist, geeignete Probleminstanzen zum Test der Datenstrukturen zu verwenden, ist an dieser Stelle schon eine hohe Qualität des Instanzengenerators notwendig.
Neben der Bewertung der oben genannten Verfahren sollen in einer ersten experimentellen Analyse auch komplexere, modernere Indexstrukturen getestet werden, insbesondere Strukturen mit superlinearem Platzbedarf. Es spricht viel dafür, dass komplizierte Datenstrukturen zwar einen theoretischen Vorteil bringen, in der Praxis aber nicht einsetzbar sind. Dies gilt insbesondere für Indexstrukturen, die auf dem Sekundärspeicher operieren. Demgegenüber scheinen Varianten klassischer Textspeicherdatenstrukturen geeignet für den fehlertoleranten Fall. Die experimentelle Studie soll diese Hypothese verifizieren.
Im ersten Schritt der Evaluation werden Methoden, die auf dem Sekundärspeicher operieren, eine besondere Stellung einnehmen. Im Falle der String-B-Trees und Suffixbäume mit entsprechendem Layout existieren noch keine spezialisierten fehlertoleranten Suchalgorithmen. Hier müssen zunächst, ausgehend von den bekannten Suchstrategien auf Hauptspeicherindizes, Algorithmen entwickelt und verfeinert werden. Fehlertolerante Suchalgorithmen für Prefix-Partitioned Look-Up Trees existieren bereits und sind in [AN07] beschrieben.
Wie die Erstellung der Bibliothek soll auch die experimentelle Analyse in dem Forschungsprojekt einen fortlaufenden, dynamischen Prozess darstellen. Indizes und Algorithmen, die aus den in den folgenden Unterpunkten beschriebenen Studien entstehen, sollen sorgfältig experimentell evaluiert und mit den in der Bibliothek vorhandenen Lösungen verglichen werden.
Allgemeine Fehlermodelle
Eine Vielzahl der bekannten Indexstrukturen für fehlertolerante Suche verwendet stark vereinfachte Fehlermodelle, die für reale Probleme unzureichend sind. Gerade die theoretisch gut analysierbaren Methoden beschränken sich auf einfache Hamming- bzw. Edit-Distanz. In vielen Anwendungen, zum Beispiel im Bereich der biologischen Daten, stellt dies aber eine zu starke Vereinfachung dar. Sequenzähnlichkeiten (auf Nukleotid- oder Aminosäureebene) basieren auf evolutionären Mechanismen. Im Zuge eines solchen Vorgangs kann z.B. der Austausch von Aminosäure A gegen Aminosäure B wahrscheinlich, der Austausch von A gegen C dagegen sehr unwahrscheinlich sein. Dem wird in der Regel bei der fehlertoleranten Suche durch Bewertungsmatrizen Rechnung getragen. Unterschiedliche Bewertung von bestimmten Fehlerarten sind in vielen realen Problemen sinnvoll. Daneben gibt es Anwendungen in denen Fehlerarten berücksichtigt werden müssen, die nicht durch die Edit-Operationen abgedeckt sind, z.B. Transpositionen, Translokationen, Swaps, Echo.
In diesem Teilprojekt soll zunächst einmal untersucht werden, wie flexibel vorhandene Indexstrukturen und Suchalgorithmen bezüglich Fehlermodellen sind. An Hand der vom Instanzengenerator zur Verfügung gestellten Daten soll getestet werden, wie die Leistung der modifizierten Ausgangsmethodiken unter allgemeineren Fehlermodellen ist. Hierbei sollen zunächst praktisch relevante Fehlermodelle, Alignment-Distanz bezüglich vorgegebener Bewertungsmatrix für biologische Probleme und Edit-Distanz mit Swaps für Texte, betrachtet werden.
Die Untersuchungen bezüglich allgemeiner Fehlermodelle umfassen: Modifikation bekannter Lösungen, experimentelle Evaluation, theoretische Evaluation, sowie Weiter- und Neuentwicklung von Methoden auf Basis der erhaltenen Resultate. Ziel ist, flexible, effiziente Indexstrukturen und Suchalgorithmen zu erhalten, die für eine Vielzahl von Fehlermodellen einsetzbar sind und bezüglich des jeweiligen Fehlermodells skaliert werden können.
Die Verwendung von möglichst allgemeinen Fehlermodellen ist auch ein wichtiges Kriterium im Zusammenhang mit den unten aufgeführten Punkten des Algorithm-Engineering-Prozesses.
Sekundärspeicheroptimierte Methoden
Viele Probleminstanzen, die sich aus realen Anwendungen ergeben, sind so groß, dass die entsprechenden Indizes nicht im Hauptspeicher gehalten werden können. Das menschliche Genom besteht zum Beispiel aus mehr als 3 Milliarden Basenpaaren, was bei sehr optimistischer Betrachtungsweise einen Platzbedarf von über 30 GByte für einen Suffixbaum-Index erfordert. Methoden, die Sekundärspeicher ohne zu großen Effizienzverlust nutzen, sind erforderlich.
Erster Ausgangspunkt hierfür sind die oben beschriebenen sekundärspeicheroptimierten Datenstrukturen sowie für diese Strukturen bekannte oder noch zu entwickelnde Suchalgorithmen. Insbesondere wollen wir die Ansätze für Prefix-Partitioned Look-Up Trees [AN07] verfeinern und weiterentwickeln. Die Möglichkeit, die Höhe dieser Bäume zu skalieren, sollte zu einer guten Speicherlokalität dieser Datenstruktur führen. Desweiteren soll in diesem Teilprojekt untersucht werden, wie gut andere Indexstrukturen, die für Sekundärspeicherverwendung geeignet sind, zum Beispiel die String-B-Trees [FG99], zur fehlertoleranten Suche verwendet werden können. Dafür müssen vor allem Algorithmen für andere Sekundärspeicherindizes entwickelt werden.
Dieser Arbeitspunkt umfasst auch eine theoretische Analyse der entsprechenden Indizes und Suchalgorithmen, wobei insbesondere die I/O-Effizienz untersucht werden soll.
Die Algorithmen sollen auch auf allgemeinere Fehlermodelle mit praktischer Relevanz erweitert werden, z.B. Alignment-Distanz bzgl. einer gegebenen Bewertungsmatrix oder affinen Lückenkostenfunktionen.
Die in diesem Teilprojekt beschriebenen Arbeitsschritte werden begleitet von kontinuierlichen experimentellen Studien und Integration vielversprechender Ansätze in die Bibliothek.
Cache-effiziente fehlertolerante Mustersuche
Ein wichtiger Faktor für die praktische Leistung eines Algorithmus ist die zugrunde liegende Speicherhierarchie. Wir wollen im Rahmen des Arbeitsprogramms Algorithmen und Datenstrukturen zur fehlertoleranten Mustersuche untersuchen, die diese Strukturen effizient nutzen (cache-effiziente Algorithmen). Die Autoren von [AZS99] untersuchen cache-effizientes (exaktes) Suchen in Tries. Dabei machen sie sich unter anderem zu Nutze, dass bei der exakten Suche von einem bestimmten Knoten immer höchstens zu einem Nachfolgeknoten gesprungen wird. Im fehlertoleranten Fall trifft das nicht zu.
Für cache-effiziente Datenstrukturen und Algorithmen ist zunächst einmal ein genaues Verständnis des Verhaltens der bekannten Methoden bezüglich ihres Cache-Verhaltens notwendig. Die Standardverfahren (diese sollen sowieso im Zuge des Arbeitsprogramms implementiert werden) sollen zunächst bezüglich realer und simulierter Speicherhierarchien getestet werden. Die Ergebnisse der Simulationen sollen dann Ausgangspunkt für das Design von spezialisierten Datenstrukturen bzw. Implementation von Datenstrukturen und den zugehörigen Algorithmen sein. Wir sind davon überzeugt, dass cache-effiziente Methoden in der Praxis deutliche Performance-Vorteile im Vergleich zu nichtspezialisierten Lösungen aufweisen.
Massiv parallele, verteilte Algorithmen für Suffixbäume
Die oben erwähnte Suffixbaumdatenstruktur ist aufgrund ihrer Platzeffizienz sowie der geringen Komplexität ihrer Erzeugung bzw. Anwendung zur Lösung vieler, insbesondere für Anwendungen in der Bioinformatik relevanter Probleme ideal geeignet. Praktische Einschränkungen resultieren jedoch hauptsächlich aus der mangelnden Lokalität der Speicherzugriffe, sowohl bei der Konstruktion der Datenstruktur als auch beim Durchlaufen des Baums im Query Processing. In der Konsequenz wird die Laufzeit dieser Algorithmen in der konkreten Implementierung häufig von Speicherzugriffslatenzen beherrscht, die sich in der Weiterentwicklung der Speichertechnologie jedoch weit weniger schnell verbessern als die reine Zugriffsbandbreite. Insbesondere ist die Verwendung von Sekundärspeichern in diesem Zusammenhang prohibitiv. Somit ist die Größe der in Suffixbäumen verwaltbaren Textdaten durch die Kapazität des Hauptspeichers der betreffenden Maschine beschränkt.
Wir streben aus diesem Grund die Entwicklung spezialisierter Verfahren zur Verteilung von Suffixbäumen auf eine große Zahl eng gekoppelter Rechner an, wie dies in aktuellen Hochleistungsrechnerarchitekturen realisiert ist. Vorarbeiten zu diesem Themenkomplex existieren beispielsweise in [Cli05,CM96,FG96] in Form von Parallelisierungsansätzen und Optimierungen für die Konstruktion von Suffixbäumen im Sekundärspeicher. Der Fokus unseres Ansatzes wird demgegenüber auf der massiven Verteilung in einem System wie dem SGI HLRB-II des Leibniz Rechenzentrums München liegen. Für das von uns vorgeschlagene Projekt kann dieser Großrechner mit zur Zeit 4096~Cores (CPUs) und 17.5 TByte Hauptspeicher als Experimentierplattform genutzt werden. Zur möglichst effizienten Nutzung einer solchen Architektur sollen auch die in den einzelnen Knoten implementierte Speicherhierarchie sowie die spezifische Rechnerorganisation (Zusammenfassung von Cores zu Mehrprozessorknoten und die damit einhergehende Inhomogenität von Kommunikationslatenzen) in die Optimierung einbezogen werden. Die von uns angestrebten Methoden sollen somit besser an hierarchisch organisierte Rechnerarchitekturen angepaßt sein als beispielsweise bei [Cli05]. In einer zweiten Phase der Algorithmenentwicklung sollen auch die oben angesprochenen Methoden zur approximativen Textsuche in die Parallelisierung mit einbezogen werden. Für die unseren Entwicklungsprozess begleitenden Experimente sollen hauptsächlich biologische Datensätze herangezogen werden. So streben wir an, gemeinsame Suffixbäume für eine große Zahl von eukaryotischen Genomsequenzen zu berechnen und auf praxisrelevante Queries anzuwenden. Ferner soll auch der in [TBG06] beschriebene Ansatz zur Anwendung von Suffixbäumen für die Suche nach Proteinstrukturen für entsprechend größere Datenbanken auf einer Architektur mit verteiltem Speicher getestet werden.
Smoothed Analysis
In diesem Teilprojekt soll eine Analyse der Smoothed Complexity [ST04] von Datenstrukturen über Texten, deren Effizienz von der Länge gemeinsamer Präfixe in der Eingabemenge abhängt (Tries, PATRICIA-Bäume, Suffixbäume usw.), durchgeführt werden. Dabei kommt der Entwicklung und Validierung von geeigneten Perturbationsmodellen besondere Bedeutung zu.
Die Komplexität der Operationen von Stringspeicher- und Stringsuchdatenstrukturen wie Prefix-Tries oder auch PATRICIA-Tries ist linear in der Höhe der verwendeten Bäume. Im Worst Case ist diese und somit auch die Komplexität der Operationen linear in der Menge der Strings, die in der Datenstruktur abgespeichert sind. Im Average Case ergibt sich für n zufällige Strings (z.b. über dem binären Alphabet) sowohl bei PATRICIA-Tries als auch bei Prefix-Tries eine erwartete Höhe von Θ(log n).
Im beantragten Projekt sollen ausgehend von der Average-Case-Analyse und den Edit-Operationen (Substitution, Insertion und Deletion) geeignete Perturbationsmodelle entwickelt werden und die Smoothed Complexity der genannten Datenstrukturen unter den Modellen sowohl experimentell, als auch theoretisch analysiert werden. Im Einzelnen sind die folgenden Arbeitsschritte vorgesehen und teilweise wurde bereits Vorarbeit [EKN07] geleistet, die in das Projekt einfließen soll: Ausgehend von der Average-Case-Analyse wurde untersucht, inwieweit sich die Höhe eines Prefix-Tries auf n Eingabestrings, die jeweils unabhängig voneinander und zufällig mit lokalen Edit-Operationen perturbiert werden, verändert. Es hat sich folgendes ergeben: Die Analyse mit Substitutionen entspricht im Wesentlichen dem Vorgehen bei der Average-Case-Analyse und somit ergibt sich eine logarithmische Höhe. Für Insertionen und Deletionen kann unter bestimmten Bedingungen ebenfalls eine logarithmische Smoothed Complexity gezeigt werden, wobei die Bedingungen im Fall der Insertionen nur bezüglich der Perturbationsfunktion und im Fall der Deletionen zusätzlich dazu auch bezüglich des Eingabeuniversums zu verstehen sind: Hat man beispielsweise n identische 1er Strings unendlicher Länge, so bleiben diese unter zufälligen lokalen Deletionen einzelner 1er identische Strings.
In weiteren Arbeitsschritten soll das aufgezeigte Modell auch andere lokale Perturbationen, z.b. Echo-Operationen, zulassen. Dabei soll der Fokus sowohl auf Perturbationen gelegt werden, die eine theoretische Analyse möglich machen, als auch auf Perturbationen, die in natürlichen Eingaben auftreten können: Probabilistische Automaten mit bestimmten Beschränkungen scheinen hierbei ein nützliches Werkzeug zu sein, das verwendet werden soll.
Die Perturbationsmodelle sollen im Instanzen-Generatoren
anderen Wissenschaftlern zur Verfügung gestellt und in die geplante
Bibliothek integriert werden.