Veröffentlichungen

Turbo für Graphdatenbanken - Graphpartitionierung mit KaHIP

Heiko Papenfuß, Peter Sanders, Christian Schulz
Java Spektrum 1 / 2015

Mit dem von Dr. Christian Schulz, Träger des Uniserv-Forschungspreises 2014, entwickelten Open-Source Graphpartitionierer KaHIP (Karlsruhe High Quality Partitioning) lassen sich Graphen in kürzester Zeit bestmöglich partitionieren. In sozialen Netzwerken, im Big Data oder auch im Kundendatenmanagement ist dies von besonderer Bedeutung.

In einer zunehmend vernetzten, digitalen Welt erfährt ein neuartiger Typ Datenbank großen Zulauf: die Graphdatenbank. Mit ihr lassen sich Datenpunkte und ihre Verbindungen untereinander besser abbilden als mit klassischen relationalen Datenbanken. Damit die ihnen zugrunde liegende Komplexität für Software beherrschbar bleibt und effizient verarbeitet werden kann, braucht es Algorithmen, die Graphen partitionieren. Dieser Beitrag erläutert, wie diese funktionieren und welche Anwendungsmöglichkeiten daraus entstehen. 

Graphen: Knoten und Kanten

Graphen sind Strukturen aus „Knoten“ und sich untereinander verbindenden „Kanten“. Sie eignen sich zur Modellierung von Netzwerken aller Art, in denen Objekte zueinander in gerichteten oder ungerichteten Beziehungen stehen. Ein besonders anschauliches Beispiel ist wohl der Graph sozialer Netzwerke, der einerseits Personen (Knoten) samt ihrer Eigenschaften beschreibt, aber eben auch die Beziehungen dieser Personen zueinander. Die Kanten zwischen den Knoten beschreiben in diesem Fall, welche Personen miteinander als „Freund“ oder „Follower“ verbunden sind. Bei Twitter beispielsweise handelt es sich aufgrund der Möglichkeit, jemandem einseitig zu folgen, um gerichtete Graphen. Die Freundschaftsbeziehungen bei Facebook mit seiner reziproken Struktur sind hingegen ein ungerichteter Graph.

Nun lässt sich eine Fülle von Beziehungen mit Graphen darstellen. So ist ein Straßennetz nichts anderes als ein Graph, der für Navigationssoftware in einer Datenbank abgebildet werden muss. Auch Schaltkreise in Computerchips lassen sich als Graph beschreiben, genauso wie Sensornetzwerke. Ebenfalls augenfällig sind die Einsatzmöglichkeiten bei Kundendaten, die für Marketing und Vertrieb genutzt werden.