English China

Big Data

Ist Rechenpower alles bei der Big-Data-Analyse?

Seite: 2/3

Anbieter zum Thema

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.

(ID:42957628)