Pressemeldungen

Uniserv verleiht Forschungspreis am KIT 2014

Dr. rer. nat. Christian Schulz für die Arbeit „High Quality Graph Partitioning“ ausgezeichnet.

Netzwerke sind durch die technischen Entwicklungen der letzten Jahrzehnte aus unserem Alltag nicht mehr wegzudenken. „Soziale Netzwerke“, „Networking“ oder das Internet selbst haben unsere Art zu kommunizieren und unsere Beziehungen verändert. Das Wissen, dass sich aus Netzwerken ziehen lässt, wird insbesondere auch in Unternehmen mehr und mehr als wertvolle Ressource und Mittel zur Wertschöpfung genutzt. Sind Relationship Management und Social Networking mittlerweile doch zu wichtigen Teilbereichen des Customer Data Managements geworden. 

Uniserv verleiht Forschungspreis am KIT 2014
Uniserv verleiht Forschungspreis am KIT 2014

Um Freundschaftsbeziehungen in sozialen Netzwerken darstellen zu können, werden Graphen benötigt. In der Informatik sind Graphen das universelle Werkzeug zur Modellierung von Beziehungen zwischen Objekten – also Netzwerken. Häufig sind die betrachteten Netzwerke in der Praxis so groß, dass  man diese Graphen zerlegen muss. Insbesondere dann, wenn sie so groß werden, dass ein einzelner Computer sie nicht mehr effizient verarbeiten kann. Diese Aufteilung – also die Graphpartitionierung – ist aber umso nützlicher, je weniger Verbindungen zwischen den Teilgraphen dabei zerschnitten werden, da die zeitaufwändige und damit „teure“ Kommunikation zwischen den Knoten so minimiert wird. In Zeiten von Big Data, in denen eine Flut von Informationen am besten in Echtzeit vorliegen müssen, ein echter Mehrwert, der schon bald ganz konkret bei einer speziellen Gruppe der aktuell sehr erfolgreichen NoSQL-Datenbanken wichtige Fortschritte bringen könnte: den Graphdatenbanken, die besonders geeignet sind, Beziehungen von Dingen, aber auch Menschen abzubilden und zu verarbeiten.


So wie es beinahe unbegrenzt viele Anwendungsbereiche für Graphen gibt, gibt es buchstäblich tausende Anwendungen von Graphpartitionierung. 

Neue Lösung schlägt alle existierende Systeme

Entsprechend gibt es seit mehr als einem Jahrzehnt etablierte und kaum mehr veränderte Werkzeuge für dieses Problem, deren Leistungsfähigkeit genauso lange als die bestmögliche galt. Davon hat sich Christian Schulz glücklicherweise nicht schrecken lassen: Sein Open-Source Graphpartitionierer KaHIP (Karlsruhe High Quality Partitioning), das Ergebnis seiner mit Auszeichnung abgeschlossenen Dissertation, schlägt alle existierenden Systeme. KaHIP liefert verbesserte Lösungen für fast alle Eingaben in weltweit anerkannten Benchmark-Sammlungen. Oft genügen Minuten, um die beste bekannte Lösung zu finden, während die vorhergehenden Rekordhalter Tage gerechnet haben.

Innovatives Zusammenspiel verschiedenster Techniken

Möglich wird dieser Erfolg durch ein geschicktes Zusammenspiel einer Vielzahl von Techniken, wie Parallelverarbeitung, evolutionäre Algorithmen, lokale Suche, Mehrschichtverfahren, Fluss- und Pfadberechnungen, u.v.a.m. Wie bei den Zutaten in der Haute Cuisine ist es Christian Schulz in seiner Arbeit gelungen, durch geschickte Zubereitung (Implementierung) und sorgfältiges Abschmecken (ausführliche Experimente) ein Gourmet-Menü (KaHIP) hervorzubringen. Dafür gibt es zwar keinen Stern des Guide Michelin – stattdessen wird Christian Schulz aber für seine außerordentliche Leistung und die herausragenden Ergebnisse seiner Dissertation mit dem Thema „High Quality Graph Partitioning“ mit dem Uniserv Forschungspreis „Algorithmen für effiziente Datenverarbeitung“ ausgezeichnet. Die Uniserv Experten sind der Meinung, dass die Ergebnisse seiner Arbeit wichtige Fortschritte in vielen praktischen Anwendungsbereichen ermöglichen – bis hin zu Big Data und eventuell eines Tages auch im Kundendatenmanagement.