English China

Big Data

Ist Rechenpower alles bei der Big-Data-Analyse?

Seite: 3/3

Anbieter zum Thema

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)