External Memory Minimaler Spannbaum

Ein externer minimaler Spannbaum bezeichnet in der Informatik einen minimalen Spannbaum, der für einen in den Sekundärspeicher ausgelagerten Graphen $G=(V,E)$ berechnet wurde. Letzteres ist für Graphen nötig, deren Anzahl Knoten und Kanten zu groß ist, als das sie gleichzeitig vollständig in den Hauptspeicher passen. Als Anwendungsbeispiel kann man einen Crawl des sozialen Netzwerkes Twitter aus dem Jahre 2010 heranziehen. Wenn man das Kantengewicht vernachlässigt und eine Kante als Paar von Knotenindizes speichert, so ergibt sich für den Graphen eine Größe von

${\frac {(2\cdot \lceil \log _{2}(41652230)\rceil )\cdot 1468365182}{8}}\,{\text{Bytes}}\approx 9{,}55\cdot 10^{9}\,{\text{Bytes}}$,

was 9,55 Gigabytes entspricht. Wenn man davon ausgeht, dass ein Desktop-PC für gewöhnlich über 8 GB Hauptspeicher verfügt, so würden diese nicht ausreichen, um auf dem Graphen einen minimalen Spannbaum vollständig intern zu berechnen.

Für externe Algorithmen verwendet man als Berechnungsmodell das External Memory Modell. Es besteht aus Hauptspeicher der Größe $M$ und Sekundärspeicher und man kann Datenblöcke der Größe $B$ zwischen ersterem und letzterem übertragen. Das Lesen (Schreiben) eines Blocks vom (in den) Sekundärspeicher in den (vom) Hauptspeicher, bezeichnet man als I/O (= Input/Output). Letzteres ist die Kerngröße in diesem Modell, die es zu minimieren gilt. Im Gegensatz zu Modellen wie der Random Access Machine steht hier nicht die asymptotische Laufzeit im Vordergrund, sondern die Anzahl I/Os. Aufgrund der deutlich erhöhten Zugriffszeit des Sekundärspeichers, relativ zu der des Hauptspeichers, werden die I/Os oft zum Flaschenhals des Systems.

Semiexterne Berechnung

Eine Einschränkung zur Definition aus der Einleitung bilden semiexterne Algorithmen zur Berechnung minimaler Spannbäume. Jene Algorithmen verarbeiten ungerichtete Graphen, von denen nur die Knoten in den Hauptspeicher passen. Formal ist das durch die Beziehung

$M=c\cdot |V|<|E|$

gegeben, wobei $c$ eine Konstante ist.

Der Algorithmus von Kruskal lässt sich leicht als semiexterne Variante umsetzen. Dazu muss man die Kanten zunächst nach aufsteigendem Gewicht extern sortieren, was sich mithilfe von

$\operatorname {sort} (|E|):=\Theta \left({\frac {|E|}{B}}\cdot \log _{\frac {M}{B}}\left({\frac {|E|}{B}}\right)\right)$ (die Sortierschranke) I/Os

realisieren lässt. Die Union-Find-Struktur lässt sich vollständig im Hauptspeicher verwalten, wodurch sich insgesamt ${\mathcal {O}}(\operatorname {sort} (|E|))$ I/Os ergeben.

Externe Berechnung

Falls die Knotenmenge ebenfalls zu groß für den Hauptspeicher ist, so lässt sich ein minimaler Spannbaum durch externe Algorithmen berechnen.

Algorithmus von Prim

Der Algorithmus von Prim kann mithilfe einer externen Prioritätswarteschlange als externer Algorithmus ausgeführt werden. Sie speichert die Kanten des Graphen, wobei als Priorität deren Gewichte genommen werden. Der Algorithmus wählt iterativ die Kante geringsten Gewichts aus und fügt sie zum bisherigen minimalen Spannbaum hinzu. Die leichteste Kante erhält man durch eine extractMin()-Operation der Warteschlange. Im Folgenden ist der Algorithmus in Pseudocode beschrieben (es ist zu beachten, dass die gerichteten Kanten von $G$ betrachtet werden).

c: Gewichtsfunktion der Kanten
s $\in$ V(G): beliebiger Startknoten
Adj: adjazenten Knoten eines Knoten
Inc: inzidente Kanten eines Knoten

external_prim(G,c,s):
01  T $\leftarrow (\emptyset ,\emptyset )$ // T = (V,E): Knoten und Kanten des zu berechnenden MST
02  Q $\leftarrow$ leere externe Prioritätswarteschlange
03  für alle e $\in$ Adj(s)
04      Q.insert(e, c(e))
05  solange Q nicht leer
06      (u,v) $\leftarrow$ Q.extractMin()
07      wenn v nicht Teil von T
08          V(T) $\leftarrow$ V(T) $\cup$ {v}
09          E(T) $\leftarrow$ E(T) $\cup$ {(u,v)}
10          für alle e $\in$ Inc(v) \ {(v,u)} // denn (u,v) ist schon aufgenommen worden
11              Q.insert(e, c(e))
12  return T

Es wird angenommen, dass die Kantengewichte paarweise verschieden sind. So kann man die Überprüfung in Zeile 7, ob der v Knoten bereits im Spannbaum enthalten ist, leicht realisieren. Man muss dazu lediglich überprüfen, ob die nächste Kante minimalen Gewichts gleich (u,v) (aus Zeile 6) ist, was nur eine zusätzliche extractMin()-Operation der Warteschlange Q erfordert. Denn jeder Knoten fügt seine inzidenten Kanten in Q ein und falls v schon Teil des Spannbaums sind, so befindet sich die Kante (v,u) ebenfalls in Q. Darin muss diese Kante aber der unmittelbare Nachfolger von (u,v) sein, da nach Annahme keine zwei Kanten dasselbe Gewicht haben.

Die gesamte I/O-Komplexität umfasst ${\mathcal {O}}(|V|+\operatorname {sort} (|E|))$ I/Os. Zunächst werden für jeden Knoten dessen adjazente Knoten ausgelesen, was bei Umsetzung per Adjazenzliste

${\mathcal {O}}\left(|V|+{\frac {|E|}{B}}\right)$ I/Os

erfordert. Der Algorithmus verarbeitet weiterhin alle Kanten von $G$ und führt pro Kante höchstens zwei Operationen der Warteschlange aus. Wenn man davon ausgeht, dass die Warteschlange $n$ Operationen mit ${\mathcal {O}}(\operatorname {sort} (n))$ I/Os unterstützt, dann beträgt die Gesamtkomplexität ${\mathcal {O}}(|V|+\operatorname {sort} (|E|))$ I/Os.

Kantenreduktion

Ein anderer Ansatz ist es iterativ Kanten des minimalen Spannbaumes zu identifizieren, sodass man diese entfernen kann. Das führt man solange fort, bis der resultierende Graph ausreichend dicht ist. Ist der Graph ausreichend dicht, so fällt die Komplexität für das Berechnen des minimalen Spannbaumes auf dem verbleibenden Graphen insgesamt nicht mehr ins Gewicht.

Beispiel einer Kantenkontraktion: die Kante $\{1,2\}$ wurde kontrahiert. Die neue Kante $\{1,3\}$ war vorher $\{2,3\}$.

Konkret will man die Anzahl Knoten auf mindestens ${\tfrac {|E|}{B}}$ reduzieren, um dann auf dem resultierenden Graphen den Algorithmus von Prim laufen zu lassen, wodurch sich dessen Komplexität zu ${\mathcal {O}}(\operatorname {sort} (|E|))$ I/Os vereinfacht.

Die Reduktion entstammt dem Algorithmus von Borůvka, weswegen der folgende Ablauf auch Boruvka-Phase genannt wird: für jeden Knoten wählt man die leichteste adjazente Kante aus, welche Teil des minimalen Spannbaums sein muss. Anschließend kontrahiert man jede solche Kante, sodass sich die Anzahl Knoten mindestens halbiert. Bei der Kontraktion können neue Kanten entstehen, sodass man für diese Verweise auf dessen ursprüngliche Kante speichern muss. Letzteres ist nötig, um am Ende einen minimalen Spannbaum für den ursprünglichen Graphen konstruieren zu können.

Insgesamt sind dafür

$\left\lceil \log _{2}\left({\frac {|V|\cdot B}{|E|}}\right)\right\rceil$ Phasen

nötig. Eine einzelne Phase lässt sich mit ${\mathcal {O}}(\operatorname {sort} (|E|))$ I/Os implementieren, sodass sich insgesamt

${\mathcal {O}}\left(\operatorname {sort} (|E|)\cdot \max \left\{1,\left\lceil \log _{2}\left({\frac {|V|\cdot B}{|E|}}\right)\right\rceil \right\}\right)$ I/Os

ergeben. Die Maximumsbildung in der Komplexität rührt daher, dass mindestens eine Boruvka-Phase nötig ist.

Randomisierter Sweep

Anstatt den deterministischen Verfahren kann man die Berechnung auch randomisiert durchführen. Die Idee ist es die Anzahl Knoten solange zu reduzieren, bis man auf dem verbleibenden Graphen einen semiexternen Algorithmus ausführen kann. Die Reduktion wird ebenfalls durch Kantenkontraktion, wie oben beschrieben, umgesetzt. Dabei wird iterativ ein zufälliger Knoten ausgewählt und nur dessen leichteste Kante kontrahiert, nachdem sie in den minimalen Spannbaum aufgenommen wurde.

Ein Problem ergibt sich, wenn die zufällige Auswahl direkt umgesetzt wird: für jeden Knoten fällt ein I/O an, da auf die Knoten in willkürlicher Reihenfolge zugegriffen wird. Man kann dem entgegnen, indem man stattdessen eine zufällige Permutation der Knotenindizes erstellt und die Knoten nach deren neu zugewiesenen Indizes absteigend abarbeitet (= Sweeping).

Auch hier wird wieder eine externe Prioritätswarteschlange benutzt, welche die Kanten des Graphen speichert. Als Priorität wird der größere Knotenindex der Kante gewählt, wobei bei zwei gleichen Indizes die Kante mit kleinerem Gewicht die höhere Priorität bekommt. Dadurch kann man effizient die zu einem Knoten inzidente leichteste Kante bestimmen. Durch die Sortierung nach Knotenindizes und weil in jedem Schritt von einem Knoten $u$ nur die leichteste Kante $\{u,v\}$ betrachtet wird, lässt sich die Kantenkontraktion ohne weiteres umsetzen. Dazu wird in der nächsten Iteration die Kante $\{u,w\}$ als Kante $\{v,w\}$ mit selbem Gewicht in die Warteschlange eingefügt.

Die erwartete Anzahl betrachteter Kanten, bis die Anzahl Knoten auf $M$ reduziert wurde, beträgt

$2\cdot |E|\cdot \ln \left({\frac {|V|}{M}}\right)$.

Damit werden insgesamt

$|E|+4\cdot |E|\cdot \ln \left({\frac {|V|}{M}}\right)$ Operationen

auf der Warteschlange ausgeführt und es ergeben sich insgesamt

${\mathcal {O}}\left(\operatorname {sort} \left(|E|\cdot \ln \left({\frac {|V|}{M}}\right)\right)\right)$ I/Os.

Literatur

• Otakar Borůvka: O jistém problému minimálním. S. 37–58 ([1]).
• Alok Aggarwal, Jeffrey Vitter: The Input/Output Complexity of Sorting and Related Problems. ACM, New York 1988, S. 1116–1127 ([2]).