Die Suche nach dem Super-Algorithmus für Big Data

×

Große Datenmengen, viele Problemstellungen. Weil die bisher bekannten Algorithmen nicht auf das Verarbeiten großer Datenmengen ausgelegt sind, suchen Wissenschaftler nach dem Super-Algorithmus für Big Data, um das Datenmengenproblem in den Griff zu bekommen.

Die Angst des Informatikers vor dem großen Durcheinander ist berechtigt. Weil mit jedem Smartphone, mit jedem intelligenten Auto und mit jeder selbstorganisierten Produktionsanlage die verfügbare Datenmenge wächst, ist das Analysieren der riesigen Datenberge (Big Data) eine der derzeit größten Herausforderungen. Insbesondere vor dem Hintergrund, da für viele Problemstellungen die bisher bekannten Algorithmen nicht auf die Verarbeitung großer Datenmengen ausgelegt sind. In „Data Mining and Knowledge Discovery for Big Data“ geht Springer-Autor Wesley W. Chu, genau auf dieses Problem ein. Er sieht dabei eine der zentralen Aufgaben der Informatik darin, die riesigen Datenberge sinnvoll und sicher zu verarbeiten.

Auch die Wissenschaftler am Institut für Theoretische Informatik am KIT suchen deshalb nach theoretisch fundierten Verfahren und effizienteren Rechenoperationen. Daraus sollen alltagstaugliche Lösungen zur Effizienzsteigerung von Rechenvorgängen entwickelt werden, wie sie etwa bei Suchanfragen im Internet oder bei der strukturellen Analyse von sozialen Netzwerken auftreten. Im Rahmen des von der Deutschen Forschungsgemeinschaft (DFG) geförderten Schwerpunktprogramms „Algorithms for Big Data“ wurden dazu am KIT vier Projekte initiiert.

Forscher suchen Algorithmen für Big Data

Das Projekt „Schnelle inexakte kombinatorische und algebraische Löser für große Netzwerke“ von Juniorprofessor Henning Meyerhenke widmet sich einer Reihe von komplexen Problemstellungen, die sich in großen Netzwerken ergeben. Die zu lösenden Aufgaben sind durch biologische Anwendungen motiviert. Beispielsweise lassen sich Individuen einer Spezies anhand der Ähnlichkeit ihres Erbguts vernetzen und dann klassifizieren. Die neuen Verfahren helfen dabei, die anfallenden Daten mit reduziertem Rechenaufwand in gleichartige Klassen einzuteilen. Diese Einteilung macht es wiederum für Biologen einfacher, neue Erkenntnisse abzuleiten.

Im Projekt „Scalable Cryptography“ von Juniorprofessor Dennis Hofheinz (KIT) und Professor Eike Klitz (Ruhr-Universität Bochum) dreht sich alles um die Sicherheit bei Big Data. Kryptographische Verfahren, wie Verschlüsselung oder digitale Signaturen, können auch bei großen Datenmengen eine sinnvolle Sicherheitsgarantie geben. Bestehende Verfahren lassen sich aber nur bedingt anpassen: So ist etwa der Schutz durch das in gängigen Internetbrowsern verwendete Verschlüsselungsverfahren RSA-OAEP bei riesigen Datenmengen nur unzureichend geklärt. „Wir suchen nach einer Lösung, deren Sicherheitsgarantien auch bei einer steigenden Anzahl an Zugriffen und Benutzern stabil bleiben“, so Juniorprofessor Dennis Hofheinz von der Arbeitsgruppe Kryptographie und Sicherheit am KIT.

Eine immense Ansammlung von Daten bilden die immer weiter wachsenden sozialen Netzwerke wie Facebook oder Twitter. Gleichzeitig zeichnet sich dort ein großer wirtschaftlicher und politischer Wert ab. Das Projekt „Clustering in sozialen Online-Netzwerken“ von Professorin Dorothea Wagner (KIT) und Professor Ulrik Brandes (Universität Konstanz) setzt an diesen Netzwerken an. Neue Algorithmen sollen es möglich machen, die Entwicklung von Onlinegemeinschaften in sozialen Netzwerken nachzuvollziehen.

Um eine große Menge an Daten wie zum Beispiel im Internet zu durchsuchen, ist ein funktionsfähiges Werkzeug, etwa eine gute Suchmaschine, unerlässlich. „Doch die heute verwendeten Suchmaschinen lassen sich mit effizienteren Algorithmen noch weiter verbessern“, sagt Professor Peter Sanders, der ebenfalls am Institut für Theoretische Informatik forscht. Mit seinem Projekt „Textindizierung für große Datenmengen“ sucht Sanders gemeinsam mit Professor Johannes Fischer von der Technischen Universität Dortmund nach Optimierungsmöglichkeiten. Insbesondere sollen viele Prozessoren gleichzeitig eingesetzt werden und die Daten sollen in stark komprimierter Form trotzdem durchsuchbar bleiben.