MapReduce auf Graphen

Da sich die Menge der weltweiten Daten rund alle eineinhalb Jahre verdoppelt, ist eine effizientere Speicherung und Berechnung auf den Daten notwendig. In diesem Buch werden für semantische Daten zwei Ansätze vorgestellt, wie ein Muster, bestehend aus Breiten- und Tiefensuchen, mit Hilfe des MapReduce-Prinzips verteilt werden kann. Der erste Ansatz verteilt die Eingabe der Mustersuche auf mehrere Rechner und erreicht dadurch einen gleichmäßigen Speedup. Im zweiten Ansatz wird der Graph, in dem die semantischen Daten gespeichert sind, auf mehrere Rechner verteilt. Dabei wird, so lange nicht alle Teilgraphen im Arbeitsspeicher gecacht werden können, ein superlinearer Speedup erreicht. Andernfalls existiert keine weitere nennenswerte Beschleunigung. Abschließend wird eine theoretische Kombination der beiden Ansätze diskutiert.