English China

Big Data Ist Rechenpower alles bei der Big-Data-Analyse?

Autor / Redakteur: Ulrich Meyer* / Dipl.-Chem. Marc Platthaus

Bei der Verarbeitung großer Datenmengen werden typischerweise sehr leistungsfähige Rechner eingesetzt. Aber ohne geeignete Algorithmen stoßen auch diese schnell an ihre Grenzen. Verbesserte Graphalgorithmen sind der Schlüssel, viele praxisrelevante Big-Data-Berechnungsprobleme effizient zu lösen.

Anbieter zum Thema

Abb.1: Auf das Thema Big Data muss man auch im Labor Antworten finden.
Abb.1: Auf das Thema Big Data muss man auch im Labor Antworten finden.
(Bild: © Alex011973_fotolia.com)

Big Data ist inzwischen in aller Munde und eine Vielzahl von Artikeln in diversen Printmedien widmet sich diesem Thema. Dabei werden wahlweise die Vorteile oder die Risiken und Nebenwirkungen von „Big Data Algorithmen“ in den Vordergrund gestellt. Meist geht es darum, verschiedenste Daten miteinander zu verknüpfen, um so bisher unbekannte (statistische) Zusammenhänge zu sehen. Es ist anfangs oft gar nicht klar, auf welche Fragen man eigentlich Antworten sucht. Die dafür benutzten Algorithmen sind dementsprechend sehr allgemein und nicht auf ein konkretes Anwendungsproblem hin programmiert. Etliche Anwendungen sind aber ganz anders gestrickt und obwohl sehr klar ist, wonach man sucht, bedeutet die schiere Größe der Daten eine enorme Herausforderung. Selbst einfache klassische Probleme lassen sich für Big Data ohne bessere Algorithmen nur noch mit sehr hohem Aufwand lösen.

Im neu eingerichteten Schwerpunktprogramm SPP 1736 „Algorithms for Big Data“ (www.big-data-spp.de) der Deutschen Forschungsgemeinschaft (DFG) geht es um solche Fragestellungen der theoretischen Informatik. Gleich mehrere Projekte beschäftigen sich mit so genannten „Graphalgorithmen“.

Wozu werden Graphalgorithmen verwendet?

Ein bekanntes Beispiel: Wer heutzutage eine Adresse in einer fremden Stadt anfahren will, benutzt dazu höchstwahrscheinlich ein Navigationsgerät oder Smartphone mit entsprechender Software. Beide suchen eine gute oder sogar optimale Route mittels Algorithmen zur kombinatorischen Optimierung. Die Straßenkarte wird intern als Graph abgespeichert, das ist eine Datenstruktur aus Knoten und Kanten. Ein Knoten v entspricht einer Abzweigung oder Straßenkreuzung, eine Kante e={v,w} repräsentiert den Straßenabschnitt zwischen den Knoten v und w. Jede Kante besitzt außerdem ein Kantengewicht c(e), welches z.B. die Länge (oder Reisezeit) des zur Kante gehörenden Straßenabschnitts kodiert. Dementsprechend besteht eine Route vom Startknoten s zum Zielknoten t aus einer Abfolge von Kanten{s,v1}, {v1,v2}, …, {vi-1,vi}, {vi,t} und die Gesamtlänge der Route ergibt sich aus der Summe der entsprechenden Kantengewichte.

Wie findet ein Algorithmus in einem Graphen schnell eine kürzeste Route vom Start zum Ziel? Naiv könnte man hoffen, dass heutige Computer leistungsstark genug sind, einfach alle möglichen Pfade durchzuprobieren und den besten auszugeben. Ein Blick auf den Beispielgraph (siehe S. 24) zeigt jedoch, dass die Anzahl möglicher Pfade im Extremfall viel zu schnell aus dem Ruder läuft: Vom Startknoten s = 0 zum Knoten 3 gibt es zwei Möglichkeiten (entweder über Knoten 1 oder über Knoten 2), dann vom Knoten 3 zum Knoten 6 wiederum zwei Möglichkeiten, das heißt insgesamt also schon 2*2 = 4 verschiedene Routen um von s nach 6 zu gelangen. Weiterhin 2*2*2=23 = 8 Varianten für die Reise von s nach 9 und somit 24 = 16 mögliche Pfade von s nach Knoten 12, sowie allgemein 2(i/3) unterschiedliche Routen von s nach Knoten i, falls i durch 3 teilbar ist.

Erweitert man den Beispielgraphen in analoger Form, dann kommen für den Abschnitt von s bis Knoten 99 schon 233 = 8 589 935 592 Möglichkeiten zusammen und bis Knoten 999 eine rund hundertstellige Zahl verschiedener Routen (das ist deutlich mehr als die Anzahl der Atome im gesamten Universum).

Nun sehen Straßengraphen natürlich etwas anders aus als unser kleines Beispiel, aber auch in ihnen gibt es viel zu viele Möglichkeiten um von A nach B zu gelangen, und die Anzahl der Knoten für gebräuchliche Graphen Westeuropas liegen eher in der Größenordnung von 20 Millionen statt nur 1000. Es braucht also deutlich bessere Methoden als das triviale Aufzählen und Austesten aller Alternativen.

Verbesserung durch Dijkstras Algorithmus

Die Basis dazu wurde schon 1959 durch Edsger W. Dijkstra gelegt. Sein Verfahren arbeitet in höchstens so vielen Phasen wie es Knoten gibt. Ausgehend von dem Startknoten s wird in jeder Phase die kürzeste Route zu einem weiteren Graphknoten korrekt bestimmt und dieser Knoten in eine Menge endgültiger Knoten aufgenommen. Von den endgültigen Knoten wissen wir also, dass ein Distanzwert für einen kürzesten Weg zu ihnen gefunden wurde. Für die noch nicht endgültigen Knoten werden vorläufige Distanzen zum Startknoten s verwaltet. Wird nun ein Knoten v endgültig, so testet der Algorithmus für jeden Nachbarknoten w von v, ob sich für die vorläufige Distanz von s nach w eine Verbesserung ergibt, indem man zunächst die nunmehr bekannte optimale Route von s nach v verfolgt und diese um die Kante von v nach w erweitert. Dijkstra hat gezeigt, dass sein Verfahren korrekt funktioniert, wenn in jeder Phase gerade der Knoten mit kleinster vorläufiger Distanz in die Menge endgültiger Knoten aufgenommen wird. Somit wird jeder Knoten und jede Kante im Wesentlichen nur höchstens konstant oft betrachtet. Mit ähnlich geringem Aufwand können dann die tatsächlichen kürzesten Pfade aus den Distanzwerten rekonstruiert werden. Das bedeutet eine dramatische Verbesserung gegenüber der trivialen Überprüfung aller möglichen Pfaden.

Die Laufzeit von Dijkstras Algorithmus hängt damit hauptsächlich davon ab, wie viele Knoten und Kanten durchmustert werden, bis der gewünschte Zielknoten in die Menge der endgültigen Knoten aufgenommen wird. Insbesondere bei weit entfernten Zielknoten arbeitet der Standard-Dijkstra alles andere als zielorientiert, sondern sucht auch in Richtungen, die Menschen bei einem Blick auf eine klassische Straßenkarte nicht verfolgen würden. Ebenso käme man bei einer langen Route kaum auf die Idee, eine Autobahn zwischenzeitlich zugunsten eines Feldweges zu verlassen, um so die unter Umständen ein paar Meter Wegstrecke einzusparen.

Ist ein Straßengraph mit einer Knotenzahl im zweistelligen Millionenbereich nun Big Data? Als die ersten Navigationssysteme gegen Ende des letzten Jahrtausends ihren Siegeszug in PKW begannen und ihre Daten noch bevorzugt auf CD-Rom gespeichert wurden, galten diese Datenmengen zweifelsohne als sehr groß. Heutzutage denken wir bei großen Graphen eher an den Facebook-Graph (der sich aus der Interpretation von über einer Milliarde Nutzern als Knoten und über 100 Milliarden Freundschaftsbeziehungen als Kanten ergibt) oder an den Web-Graph (mit etlichen Milliarden Webseiten als Knoten und Verweisen als Kanten). Distanzberechnungen in diesen Graphen sind aus mehreren Gründen deutlich anspruchsvoller:

  • Die Struktur des Webs oder sozialer Netzwerke ist mit der des Straßengraphs gar nicht zu vergleichen: die kürzesten Wege zwischen Personen in sozialen Netzwerken umfassen zwar typischerweise nur wenige Kanten, aber aufgrund der vielen Freunden von Freunden explodiert die Anzahl der erreichbaren Personen mit steigender Entfernung. Die meisten Kniffe zu Straßengraphen helfen daher hier gar nicht weiter. Das heißt aber in der Konsequenz, dass nun nicht nur die Graphen an sich schon riesengroß sind, sondern dass in ihnen auch die Suchräume nicht besonders gut beschränkt werden können.
  • Weiterhin passen sehr große Graphen nicht mehr in den Hauptspeicher eines heutigen Standardrechners und die Daten müssen daher auf Externspeicher wie Festplatten oder SSD ausgelagert werden. Der Zugriff auf diese Speichermedien ist jedoch um bis zu einige Millionen Mal langsamer als ein Hauptspeicher- oder Cachezugriff. Zum Ausgleich dafür werden nicht nur Einzeldaten sondern ganze Datenblöcke übertragen. Dijkstras Algorithmus greift aber derart unstrukturiert auf die Graphdaten zu, dass der überwiegende Teil eines gerade gelesenen Datenblocks für die nächsten Algorithmenschritte typischerweise gar nicht relevant ist und schnell durch andere Blöcke im Hauptspeicher ersetzt wird.
  • Die Verteilung des Eingabegraphs auf die einzelnen Hauptspeicher eines ganzen Rechnerverbunds (Cluster, Cloud usw.) entschärft zwar die Externspeicherproblematik, aber wenn nur ein Computer die Berechnung übernimmt, müssen letztlich doch alle Graphdaten über ein Netzwerk kommuniziert werden.

Was spricht gegen die Parallelverarbeitung?

Die Abfolge der Knotenbesuche in Dijkstras Algorithmus ist inhärent sequenziell, d.h. welcher Knoten als nächstes endgültig wird, hängt davon ab, welche Knoten davor endgültig wurden und diese Reihenfolge kann nicht einfach vorhergesagt werden. Um Knoten dennoch parallel verarbeiten zu können, müssen also entweder auch Knoten besucht werden, deren vorläufige Distanzen vielleicht noch gar nicht endgültig sind und damit zu überflüssigen Operationen führen, oder ganz neue Ansätze gefunden werden.

Distanzberechnungen auf sozialen Netzwerken oder dem Webgraphen dienen vielen Zwecken, z.B. helfen sie bei dem Vorschlagen weiterer Bekannter oder beim Ranking von Webseiten in Suchmaschinen. Um sehr viele Distanzabfragen in extrem kurzer Zeit zu beantworten, können nicht jedes Mal große Teile des Graphs zeitaufwändig durchsucht werden. Stattdessen werden spezielle Datenstrukturen benutzt, aus denen sich die gesuchten Distanzen schnell aber meist etwas ungenau rekonstruieren lassen. Die Ungenauigkeit ergibt sich dabei aus der Notwendigkeit, diese Datenstrukturen sehr platzsparend gestalten zu müssen: einfach alle möglichen Distanzpaare abzuspeichern, würde z.B. für den Facebook-Graph etwa eine Million Festplatten benötigen. Erschwerend kommt hinzu, dass sich die Graphdaten quasi im Millisekundentakt verändern: Ständig werden neue Benutzer/Webseiten/Verbindungen usw. erzeugt und (etwas seltener) auch wieder gelöscht. Diese Änderungen passieren typischerweise nicht uniform im ganzen Graphen und beeinflussen auch nicht gleich alle Distanzen. Das Löschen eines „wichtigen“ Knotens (bekannte Webseite oder prominente Person) kann jedoch durchaus größere Auswirkungen haben. Aktualisierungen der Datenstrukturen erfolgen daher oft mit adaptiver Häufigkeit, an kritischen Stellen öfter als an unkritischen. Anspruchsvoll sind auch Kantengewichte mit zeitlich variablem Gewicht. Diesen Fall trifft man ganz natürlich in Graphen, die Straßennetzwerke repräsentieren: Die einem Wegabschnitt zugeordnete Reisezeit variiert unter Umständen sehr stark mit der Uhrzeit, zu der der Abschnitt befahren wird (kurz in der Nacht, länger in der Rushhour). Einfache Optimierungen im Suchalgorithmus sind nun nicht mehr ohne weiteres möglich, da der Zeitpunkt der Zielankunft nicht bekannt ist und damit auch nicht die aktuellen Kantengewichte um den Zielknoten.

Distanzberechnungen zählen zu den einfachsten Graphalgorithmen. Kompliziertere Graphprobleme beschäftigen sich z.B. mit dem Finden bestimmter Muster (Teilgraphen) oder dem Lösen so genannter Färbungsprobleme. Ein typisches Färbungsproblem ergibt sich bei Frequenzzuteilungen: Wenn Graphknoten Funksender und Kanten Störpotenziale zwischen Funksendern repräsentieren, müssen den Knoten Farben (Frequenzen) so zugeordnet werden, dass keine Kante zwei Knoten mit gleicher Farbe verbindet. Eine korrekte Färbung mit möglichst wenigen Farben stellt dann eine ressourcensparende Frequenzzuteilung dar.

Weitere Quellen zahlreicher spannender Graphprobleme sind die Logistikbranche oder die Bioindustrie.

* Prof. Ulrich Meyer: Goethe-Universität Frankfurt, Institut für Informatik, Campus Bockenheim, 60325 Frankfurt am Main

(ID:42957628)