MASS-TEXT: Textindizes für massive Datenmengen

• Antragsteller: Professor Dr. Johannes Christian Fischer, seit 3/2021
• Fachliche Zuordnung: Theoretische Informatik ; Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung von 2014 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 254939031

Texte sind eines der Aushängeschilder für Big Data. Das WWW, digitale Bibliotheken, biologische Folgen wie DNA oder Proteine: sie repräsentieren große Textdatenmengen, die man effizient speichern, strukturieren, komprimieren und durchsuchen möchte. Die Menge dieser Daten ist um mehrere Größenordnungen schneller gewachsen als die Speicher- und Berechnungskapazitäten gewöhnlicher Arbeitsplatzrechner. Zum Beispiel wurde vor etwas 10 Jahren das menschliche Genom (etwa 3 Gigabyte) als große Datenmenge angesehen. Heute möchten wir die Genome von 100 000 Menschen (oder anderen Lebewesen) gleichzeitig analysieren. Dieser Trend zu immer größeren Folgen setzt sich fort, da Sequenzierungskosten weiter fallen.Datenstrukturen für Texte, die die oben angesprochenen Anforderungen erfüllen (Speicherung, Suche, und ggf. Kompression) werden als Text-Index bezeichnet. Bekannte Dienste wie Internetsuchmaschinen (Google, Yahoo, usw.) benutzen relativ einfache "invertierte Indizes". Allerdings haben diese Datenstrukturen Schwächen bei beliebigen Anfragen oder unstrukturierten Texten wie in der Bioinformatik. Außerdem wachsen die Anfragekosten linear mit der Datenmenge. Unser Projekt konzentriert sich auf Indizes, die mit Suffixtabellen verwandt sind. Diese erlauben die Suche nach beliebigen Mustern in Zeit unabhängig von der Datenmenge. Das übergreifende Ziel des Projekts ist es, diese Datenstrukturen skalierbar zu machen, so dass sie auf großen Datenmengen und moderner Hardware funktionieren.Obwohl wir in der ersten Projektphase signifikante Fortschritte gemacht haben, bleiben wichtige Herausforderungen die wir angehen wollen. Insbesondere wollen wir massiv parallele Algorithmen für Rechner mit verteiltem Speicher für allen Phasen der Indexkonstruktion entwerfen und wir benötigen Lastverteilung für die Anfragealgorithmen. Ein anderes wichtiges Problem ist der Platzverbrauch während Konstruktion und Anfrage. Schließlich möchten wir fortgeschrittene Anfragetypen untersuchen wie Ranking der Antworten oder nichtexakte Vorkommen von Mustern.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen
• Ehemalige Antragsteller: Dr. Simon Gog, bis 12/2018; Professor Dr. Peter Sanders, von 12/2018 bis 3/2021