Durchquerung des externen Speichergraphen - External memory graph traversal

Externer Speicher Graph Traversal ist eine Art von Graph Traversal, die für den Zugriff auf extern gespeicherten Speicher optimiert ist.

Hintergrund

Die Diagrammdurchquerung ist in den meisten Diagrammalgorithmen eine Unterroutine. Das Ziel eines Graph-Traversal-Algorithmus besteht darin, jeden Knoten eines Graphen zu besuchen (und / oder zu verarbeiten). Graph-Traversal-Algorithmen wie die Breitensuche und die Tiefensuche werden mit dem von Neumann- Modell analysiert , das einheitliche Speicherzugriffskosten voraussetzt. Diese Ansicht vernachlässigt die Tatsache, dass sich ein großer Teil des Diagramms für große Instanzen eher auf der Festplatte als im internen Speicher befindet. Da der Zugriff auf die Festplatte um Größenordnungen langsamer ist als der Zugriff auf den internen Speicher, besteht die Notwendigkeit einer effizienten Durchquerung des externen Speichers .

Externes Speichermodell

Für externe Speicheralgorithmen wird das externe Speichermodell von Aggarwal und Vitter zur Analyse verwendet. Eine Maschine wird durch drei Parameter festgelegt: M , B und D . M ist die Größe des internen Speichers, B ist die Blockgröße einer Platte und D ist die Anzahl der parallelen Platten. Das Leistungsmaß für einen externen Speicheralgorithmus ist die Anzahl der durchgeführten E / A.

Suche nach der Breite des externen Speichers

Der Breitensuchalgorithmus beginnt an einem Wurzelknoten und durchläuft jeden Knoten mit der Tiefe eins. Wenn in der aktuellen Tiefe keine nicht besuchten Knoten mehr vorhanden sind, werden Knoten in einer höheren Tiefe durchlaufen. Schließlich wurde jeder Knoten des Diagramms besucht.

Munagala und Ranade

Visualisierung zur Berechnung von L (t) im Munagala-Ranade -Breitensuchalgorithmus .

Für einen ungerichteten Graphen schlugen Munagala und Ranade den folgenden externen Speicheralgorithmus vor: ${\ displaystyle G}$

Lassen Sie bezeichnen die Knoten in Breitensuche Ebene t und lassen Sie die Multi-Satz von Nachbarn des Niveaus t-1 sein. Kann für jedes t konstruiert werden, indem es in eine Menge umgewandelt und zuvor besuchte Knoten davon ausgeschlossen werden. ${\ displaystyle L (t)}$${\ Anzeigestil A (t): = N (L (t-1))}$${\ displaystyle L (t)}$${\ displaystyle A (t)}$

1. Erstellen Sie, indem Sie auf die Adjazenzliste jedes Scheitelpunkts in zugreifen . Dieser Schritt erfordert E / A. ${\ displaystyle A (t)}$${\ displaystyle L (t-1)}$${\ Anzeigestil O (| L (t-1) | + | A (t) | / (D \ cdot B))}$
2. Next wird erstellt, indem Duplikate entfernt werden. Dies kann durch Sortieren von erreicht werden , gefolgt von einer Scan- und Verdichtungsphase, die E / A benötigt. ${\ displaystyle A '(t)}$${\ displaystyle A (t)}$${\ displaystyle A (t)}$${\ displaystyle O (\ operatorname {sort} (| A |))}$
3. ${\ Anzeigestil L (t): = A '(t) \ Backslash \ {L (t-1) \ Tasse L (t-2) \}}$ berechnet wird , durch eine parallele Abtastung über und und erfordern I / O. ${\ displaystyle L (t-1)}$${\ displaystyle L (t-2)}$${\ Anzeigestil O ((| A (t) | + | L (t-1) | + | L (t-2) |) / (D \ cdot B))}$

Die Gesamtzahl der E / A dieses Algorithmus folgt unter Berücksichtigung von und und . ${\ displaystyle \ sum _ {t} | A (t) | = O (m)}$${\ displaystyle \ sum _ {t} | L (t) | = O (n)}$${\ displaystyle O (n + \ operatorname {sort} (n + m))}$

Eine Visualisierung der drei beschriebenen Schritte, die zur Berechnung von L ( t ) erforderlich sind, ist in der Abbildung rechts dargestellt.

Mehlhorn und Meyer

Mehlhorn und Meyer schlugen einen Algorithmus vor, der auf dem Algorithmus von Munagala und Ranade (MR) basiert und deren Ergebnis verbessert.

Es besteht aus zwei Phasen. In der ersten Phase wird der Graph vorverarbeitet, in der zweiten Phase wird eine Breitensuche unter Verwendung der in Phase 1 gesammelten Informationen durchgeführt.

Während der Vorverarbeitungsphase wird der Graph in nicht zusammenhängende Teilgraphen mit kleinem Durchmesser aufgeteilt. Es partitioniert die Adjazenzlisten entsprechend weiter, indem es eine externe Datei erstellt , in der die Adjazenzliste für alle Knoten in enthalten ist . ${\ displaystyle S_ {i}, \, 0 \ leq i \ leq K}$${\ displaystyle F = F_ {0} F_ {1} \ Punkte F_ {K-1}}$${\ displaystyle F_ {i}}$${\ displaystyle S_ {i}}$

Die Breitensuchphase ähnelt dem MR-Algorithmus. Zusätzlich verwaltet der Algorithmus eine sortierte externe Datei . Diese Datei wird mit initialisiert . Ferner tragen die Knoten jeder erstellten Suchebene mit der Breite zuerst Kennungen für die Dateien ihrer jeweiligen Untergraphen . Anstatt zufällige Zugriffe zum Erstellen der Datei zu verwenden, wird diese verwendet. ${\ displaystyle H}$${\ displaystyle F_ {0}}$${\ displaystyle F_ {i}}$${\ displaystyle S_ {i}}$${\ displaystyle L (t)}$${\ displaystyle H}$

1. Führen Sie einen parallelen Scan der sortierten Liste und durch . Extrahieren Sie die Adjazenzlisten für Knoten , die sich in befinden . ${\ displaystyle L (t-1)}$${\ displaystyle H}$${\ displaystyle v \ in L (t-1)}$${\ displaystyle H}$
2. Die Adjazenzlisten für die verbleibenden Knoten, die nicht gefunden werden konnten , müssen abgerufen werden. Ein Scan-Over ergibt die Partitionskennungen. Nach dem Sortieren und Löschen von Duplikaten können die jeweiligen Dateien zu einer temporären Datei verkettet werden . ${\ displaystyle H}$${\ displaystyle L (t-1)}$${\ displaystyle F_ {i}}$${\ displaystyle F '}$
3. Die fehlenden Adjazenzlisten können mit einem Scan extrahiert werden . Als nächstes werden die verbleibenden Adjazenzlisten mit einem einzigen Durchgang zusammengeführt. ${\ displaystyle F '}$${\ displaystyle H}$
4. ${\ displaystyle A (t)}$ wird durch einen einfachen Scan erstellt. Die Partitionsinformationen werden an jeden Knoten in angehängt . ${\ displaystyle A (t)}$
5. Der Algorithmus verhält sich wie der MR-Algorithmus.

Kanten werden möglicherweise häufiger gescannt , unstrukturierte E / A-Vorgänge zum Abrufen von Adjazenzlisten werden jedoch reduziert. ${\ displaystyle H}$

Die Gesamtzahl der E / A für diesen Algorithmus beträgt ${\ displaystyle O ({\ sqrt {n \ cdot (n + m) / (D \ cdot B)}} + \ operatorname {sort} (n + m))}$

Externe Speicher-Tiefensuche

Der Tiefensuchalgorithmus untersucht ein Diagramm entlang jedes Zweigs so tief wie möglich, bevor er zurückverfolgt wird.

Für gerichtete Graphen schlugen Buchsbaum, Goldwasser, Venkatasubramanian und Westbrook einen Algorithmus mit E / A vor. ${\ displaystyle O ((V + E / B) \ log _ {2} (V / B) + \ operatorname {sort} (E))}$

Dieser Algorithmus basiert auf einer Datenstruktur, die als gepufferter Repository-Baum (BRT) bezeichnet wird. Es speichert eine Vielzahl von Gegenständen aus einem geordneten Universum. Artikel werden durch Schlüssel identifiziert. Eine BTR bietet zwei Operationen:

• Einfügen (T, x) , das Element x zu T hinzufügt und amortisierte E / A benötigt. N ist die Anzahl der Elemente, die der BTR hinzugefügt wurden. ${\ displaystyle O (1 / B \ log _ {2} (N / B))}$
• Extrakt (T, k) , der alle Elemente mit dem Schlüssel k meldet und aus T löscht . Es sind E / A erforderlich , wobei S die Größe des vom Extrakt zurückgegebenen Satzes ist . ${\ displaystyle O (\ log _ {2} (N / B) + S / B)}$

Der Algorithmus simuliert einen internen Tiefensuchalgorithmus. Ein Stapel S von Knoten wird gehalten. Während einer Iteration für den Knoten v über S einen nicht besuchten Nachbarn auf S schieben und iterieren. Wenn es keine nicht besuchten Nachbarn gibt pop v .

Die Schwierigkeit besteht darin, festzustellen, ob ein Knoten nicht besucht wird, ohne E / A pro Kante auszuführen . Um dies für einen Knoten v zu tun, werden eingehende Kanten (x, v) in eine BRT D gestellt , wenn v zum ersten Mal entdeckt wird. Ferner werden ausgehende Kanten ( v , x ) in eine Prioritätswarteschlange P ( v ) gestellt, die durch den Rang in der Adjazenzliste gekennzeichnet ist. ${\ displaystyle \ Omega (1)}$

Für den Scheitelpunkt u über S werden alle Kanten ( u , x ) aus D extrahiert . Solche Kanten bestehen nur , wenn x hat sich seit dem letzten Mal entdeckt worden , u auf der Oberseite war S (oder seit dem Beginn des Algorithmus , wenn u ist das erste Mal auf der Spitze S ). Für jede Kante ( u , x ) wird eine Löschoperation ( x ) an P ( u ) ausgeführt. Schließlich ergibt eine Min-Löschoperation auf P (u) den nächsten nicht besuchten Knoten. Wenn P ( u ) leer ist, wird u aus S entfernt .

Der Pseudocode für diesen Algorithmus ist unten angegeben.

1  procedure BGVW-depth-first-search(G, v):
2      let S be a stack, P[] a priority queue for each node and D a BRT
3      S.push(v)
4      while S is not empty
5          v = S.top()
6          if v is not marked:
7              mark(v)
8          extract all edges (v, x) from D, ${\displaystyle \forall }$x: P[v].delete(x)
9          if u = P[v].delete-min() not null
10             S.push(u)
11         else
12             S.pop()

13  procedure mark(v)
14      put all edges (x, v) into D
15      ${\displaystyle \forall }$ (v, x): put x into P[v]

Verweise