Baumberechnung am Datenberg

27. August 2013, 17:02
posten

Informatiker Stefan Woltran vereinfacht komplexe Analysen großer Datenmengen

"Schwierige Berechnungsprobleme gibt es viele", sagt Stefan Woltran. Nicht nur die Wissenschaft, auch der Alltag ist mittlerweile vom Umgang mit großen Datenmengen geprägt. Wollte man etwa eine möglichst kleine Menge an Facebook-Nutzern identifizieren, über deren Freundschaftsverbindungen man die hunderten Millionen Menschen in dem sozialen Netzwerk erreicht, wäre das mit herkömmlichen Computer-Algorithmen ein "kombinatorisches Problem, das nicht effizient lösbar ist", sagt der Informatiker an der TU Wien. Komplexe Abfragen aus derart großen Datenmengen überfordern die Rechenleistung der Computer schnell. Sie würden für eine Lösung viel zu viel Zeit benötigen.

Informatiker wenden deshalb einen Trick an, um dieser "exponentiellen Explosion" aus dem Weg zu gehen. Die Netzwerke, die es zu analysieren gilt - egal ob Facebook, das U-Bahn-Netz oder komplexe Moleküle, weisen bestimmte Struktureigenschaften auf, die helfen, die Berechnung zu beschleunigen. "Auch in Facebook ist nicht jeder mit jedem befreundet, sondern es gibt viele kleine Cliquen", erläutert Woltran. Dementsprechend wird auch die Berechnung in viele kleinere Subprobleme zerlegt.

Die sogenannte Baumweite misst dabei die Komplexität der Netzwerke, die in der Fachsprache Graphen genannt werden, indem sie die Nähe zu einer Baumstruktur und damit zu einem viel effizienteren Lösungsweg angeben. "In vielen Netzwerken steigt dieser Parameter nur gering an, auch wenn die Netzwerkgröße stark ansteigt", erklärt Woltran. In einem vollkommen zufälligen System würde die Zerlegung keine Vorteile bringen. Aber, so Woltran: "In der wirklichen Welt ist Struktur vorhanden."

Wollte bisher ein Programmierer die Baumzerlegung anwenden, musste er sie, zugeschnitten auf sein spezifisches Problem, immer wieder aufs Neue "händisch ausprogrammieren". Woltran möchte diese Art der Graphenberechnung nun automatisieren: Das System soll es ermöglichen, die Algorithmen schnell zu spezifizieren, um sie auf individuelle Problemstellungen anwenden zu können. "Die Programmierer sollen nicht für jedes Problem ein neues Programm schreiben müssen."

Für diese "Dekomposition und Dynamische Programmierung für komplexe Berechnungsprobleme" baut Woltran gerade eine Arbeitsgruppe am Institut für Informationssysteme der TU Wien auf. Die finanzielle Basis dazu legt der Start-Preis, vergeben durch Wissenschaftsministerium und Wissenschaftsfonds FWF, der Woltran heuer zugesprochen wurde.

Einst wollte der 1975 in Mödling geborene Forscher selbst Programmierer werden. Computer hätten ihn von jeher interessiert. Nach dem ersten C64-Heimcomputer, einer HTL für Informatik und nach der Computerspielmusik, die er schon als Halbwüchsiger programmierte, war die "Neugier für die mathematischen und theoretischen Modelle" hinter der Funktionsweise von Computern geweckt. Als er dann gegen Ende des Informatikstudiums in die "Forschungslandschaft reinschnupperte, war klar, dass ich gern auf der Uni bleiben würde". Seine erste Projektleitung, die ihm der Wiener Wissenschafts-, Forschungs- und Technologiefonds WWTF ermöglichte, führte ihn in die Welt der Argumentationsnetzwerke. Sie gab ihm den "Boost" für den weiteren Erfolg, sagt Woltran. (Alois Pumhösel, DER STANDARD, 28.8.2013)

  • Stefan Woltran: Netzwerke haben ähnliche Struktur.
    foto: privat

    Stefan Woltran: Netzwerke haben ähnliche Struktur.

Share if you care.