Compressed Suffix Trees: Design, Construction, and Applications

• Antragsteller: Professor Dr. Enno Ohlebusch
• Mitantragsteller: Professor Dr. Mohamed Abouelhoda, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 206825075

Wenn ein Text (z.B. die DNA-Sequenz eines Chromosoms) oder eine Sammlung von Texten (z.B. mehrere Chromosomen oder Genome) nicht oder nur selten verändert wird, dann lohnt es sich in vielen Anwendungen den Text in einem Vorverarbeitungsschritt zu indizieren. Die erstellte Index-Datenstrukutur wird dann benutzt, um Anwendungen (z.B. den Vergleich zweier Genome) zu beschleunigen. Ein wesentliches Problem tritt bei der automatischen Verarbeitung von großen Datenmengen auf: Wenn der Index nicht mehr vollständig in den Hauptspeicher des benutzten Rechners passt, müssen Teile in den Sekundärspeicher ausgelagert werden. Da dies zu erheblichen Effizienzverlusten führt, ist es das Ziel des Projektes, eine Bibliothek von grundlegenden Algorithmen zur Konstruktion von „sehr kleinen“ Index-Datenstrukturen zu erstellen, die auch bei sehr großen Texten noch im Hauptspeicher gehalten werden können. Die Bibliothek soll auch Anwendungsalgorithmen auf diesen Index-Datenstrukturen zur Verfügung stellen. Weiterhin sollen die Algorithmen und Datenstrukturen in einem Kooperationsprojekt integriert werden.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Ägypten, Australien
• Beteiligte Person: Dr. Simon Gog