External memory graph traversal

<h2 id="background">Background</h2>
Graph traversal is a subroutine in most graph algorithms. The goal of a graph traversal algorithm is to visit (and / or process) every node of a graph. Graph traversal algorithms, like <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a> and <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a>, are analyzed using the <a href="/facts/Von_Neumann_architecture/te0yulFa">von Neumann</a> model, which assumes uniform memory access cost. This view neglects the fact, that for huge instances part of the graph resides on disk rather than internal memory. Since accessing the disk is magnitudes slower than accessing internal memory, the need for efficient traversal of <a href="/facts/External_memory_algorithm/sCcj8M8o">external memory</a> exists.

<h2 id="external-memory-model">External memory model</h2>
For <a href="/facts/External_memory_algorithms/sCcj8M8o">external memory algorithms</a> the external memory model by Aggarwal and Vitter<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> is used for analysis. A machine is specified by three parameters: M, B and D.
M is the size of the internal memory, B is the block size of a disk and D is the number of parallel disks.
The measure of performance for an external memory algorithm is the number of I/Os it performs.

<h2 id="external-memory-breadth-first-search">External memory breadth-first search</h2>
The breadth-first search algorithm starts at a root node and traverses every node with depth one. If there are no more unvisited nodes at the current depth, nodes at a higher depth are traversed. Eventually, every node of the graph has been visited.

<h3>Munagala and Ranade</h3>

For an undirected graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
, Munagala and Ranade<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> proposed the following external memory algorithm:
Let 
 
 
 
 L
 (
 t
 )
 
 
 {\displaystyle L(t)}
 
 denote the nodes in breadth-first search level t and let 
 
 
 
 A
 (
 t
 )
 :=
 N
 (
 L
 (
 t
 −
 1
 )
 )
 
 
 {\displaystyle A(t):=N(L(t-1))}
 
 be the multi-set of neighbors of level t-1. For every t, 
 
 
 
 L
 (
 t
 )
 
 
 {\displaystyle L(t)}
 
 can be constructed from 
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
 by transforming it into a set and excluding previously visited nodes from it.

<ol><li>Create 
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
 by accessing the adjacency list of every vertex in 
 
 
 
 L
 (
 t
 −
 1
 )
 
 
 {\displaystyle L(t-1)}
 
. This step requires 
 
 
 
 O
 (
 
 |
 
 L
 (
 t
 −
 1
 )
 
 |
 
 +
 
 |
 
 A
 (
 t
 )
 
 |
 
 
 /
 
 (
 D
 ⋅
 B
 )
 )
 
 
 {\displaystyle O(|L(t-1)|+|A(t)|/(D\cdot B))}
 
 I/Os.</li>
<li>Next 
 
 
 
 
 A
 ′
 
 (
 t
 )
 
 
 {\displaystyle A'(t)}
 
 is created from 
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
 by removing duplicates. This can be achieved via sorting of 
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
, followed by a scan and compaction phase needing 
 
 
 
 O
 (
 sort
 ⁡
 (
 
 |
 
 A
 
 |
 
 )
 )
 
 
 {\displaystyle O(\operatorname {sort} (|A|))}
 
 I/Os.</li>
<li>
 
 
 
 L
 (
 t
 )
 :=
 
 A
 ′
 
 (
 t
 )
 ∖
 {
 L
 (
 t
 −
 1
 )
 ∪
 L
 (
 t
 −
 2
 )
 }
 
 
 {\displaystyle L(t):=A'(t)\backslash \{L(t-1)\cup L(t-2)\}}
 
 is calculated by a parallel scan over 
 
 
 
 L
 (
 t
 −
 1
 )
 
 
 {\displaystyle L(t-1)}
 
 and 
 
 
 
 L
 (
 t
 −
 2
 )
 
 
 {\displaystyle L(t-2)}
 
 and requires 
 
 
 
 O
 (
 (
 
 |
 
 A
 (
 t
 )
 
 |
 
 +
 
 |
 
 L
 (
 t
 −
 1
 )
 
 |
 
 +
 
 |
 
 L
 (
 t
 −
 2
 )
 
 |
 
 )
 
 /
 
 (
 D
 ⋅
 B
 )
 )
 
 
 {\displaystyle O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B))}
 
 I/Os.</li></ol>
The overall number of I/Os of this algorithm follows with consideration that 
 
 
 
 
 ∑
 
 t
 
 
 
 |
 
 A
 (
 t
 )
 
 |
 
 =
 O
 (
 m
 )
 
 
 {\displaystyle \sum _{t}|A(t)|=O(m)}
 
 and 
 
 
 
 
 ∑
 
 t
 
 
 
 |
 
 L
 (
 t
 )
 
 |
 
 =
 O
 (
 n
 )
 
 
 {\displaystyle \sum _{t}|L(t)|=O(n)}
 
 and is 
 
 
 
 O
 (
 n
 +
 sort
 ⁡
 (
 n
 +
 m
 )
 )
 
 
 {\displaystyle O(n+\operatorname {sort} (n+m))}
 
.
A visualization of the three described steps necessary to compute L(t) is depicted in the figure on the right.

<h3>Mehlhorn and Meyer</h3>
Mehlhorn and Meyer<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> proposed an algorithm that is based on the algorithm of Munagala and Ranade (MR) and improves their result.
It consists of two phases. In the first phase the graph is preprocessed, the second phase performs a breadth-first search using the information gathered in phase one.
During the preprocessing phase the graph is partitioned into disjointed subgraphs 
 
 
 
 
 S
 
 i
 
 
 ,
 
 0
 ≤
 i
 ≤
 K
 
 
 {\displaystyle S_{i},\,0\leq i\leq K}
 
 with small diameter. It further partitions the adjacency lists accordingly, by constructing an external file 
 
 
 
 F
 =
 
 F
 
 0
 
 
 
 F
 
 1
 
 
 …
 
 F
 
 K
 −
 1
 
 
 
 
 {\displaystyle F=F_{0}F_{1}\dots F_{K-1}}
 
, where 
 
 
 
 
 F
 
 i
 
 
 
 
 {\displaystyle F_{i}}
 
 contains the adjacency list for all nodes in 
 
 
 
 
 S
 
 i
 
 
 
 
 {\displaystyle S_{i}}
 
.
The breadth-first search phase is similar to the MR algorithm. In addition the algorithm maintains a sorted external file H. This file is initialized with 
 
 
 
 
 F
 
 0
 
 
 
 
 {\displaystyle F_{0}}
 
. Further, the nodes of any created breadth-first search level carry identifiers for the files 
 
 
 
 
 F
 
 i
 
 
 
 
 {\displaystyle F_{i}}
 
 of their respective subgraphs 
 
 
 
 
 S
 
 i
 
 
 
 
 {\displaystyle S_{i}}
 
. Instead of using random accesses to construct 
 
 
 
 L
 (
 t
 )
 
 
 {\displaystyle L(t)}
 
 the file H is used.

<ol><li>Perform a parallel scan of sorted list 
 
 
 
 L
 (
 t
 −
 1
 )
 
 
 {\displaystyle L(t-1)}
 
 and H. Extract the adjacency lists for nodes 
 
 
 
 v
 ∈
 L
 (
 t
 −
 1
 )
 
 
 {\displaystyle v\in L(t-1)}
 
, that can be found in H.</li>
<li>The adjacency lists for the remaining nodes that could not be found in H need to be fetched. A scan over 
 
 
 
 L
 (
 t
 −
 1
 )
 
 
 {\displaystyle L(t-1)}
 
 yields the partition identifiers. After sorting and deletion of duplicates, the respective files 
 
 
 
 
 F
 
 i
 
 
 
 
 {\displaystyle F_{i}}
 
 can be concatenated into a temporary file F'.</li>
<li>The missing adjacency lists can be extracted from F' with a scan. Next, the remaining adjacency lists are merged into H with a single pass.</li>
<li>
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
 is created by a simple scan. The partition information is attached to each node in 
 
 
 
 A
 (
 t
 )
 
 
 {\displaystyle A(t)}
 
.</li>
<li>The algorithm proceeds like the MR algorithm.</li></ol>
Edges might be scanned more often in H, but unstructured I/Os in order to fetch adjacency lists are reduced.
The overall number of I/Os for this algorithm is 
 
 
 
 O
 
 (
 
 
 
 
 
 n
 ⋅
 (
 n
 +
 m
 )
 
 
 D
 ⋅
 B
 
 
 
 
 +
 sort
 ⁡
 (
 n
 +
 m
 )
 
 )
 
 
 
 {\displaystyle O\left({\sqrt {\frac {n\cdot (n+m)}{D\cdot B}}}+\operatorname {sort} (n+m)\right)}

<h2 id="external-memory-depth-first-search">External memory depth-first search</h2>
The depth-first search algorithm explores a graph along each branch as deep as possible, before backtracing.
For directed graphs Buchsbaum, Goldwasser, Venkatasubramanian and Westbrook<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> proposed an algorithm with 
 
 
 
 O
 (
 (
 V
 +
 E
 
 /
 
 B
 )
 
 log
 
 2
 
 
 ⁡
 (
 V
 
 /
 
 B
 )
 +
 sort
 ⁡
 (
 E
 )
 )
 
 
 {\displaystyle O((V+E/B)\log _{2}(V/B)+\operatorname {sort} (E))}
 
 I/Os.
This algorithm is based on a data structure called buffered repository tree (BRT). It stores a multi-set of items from an ordered universe. Items are identified by key. A BTR offers two operations:

<ul><li>insert(T, x), which adds item x to T and needs 
 
 
 
 O
 (
 1
 
 /
 
 B
 
 log
 
 2
 
 
 ⁡
 (
 N
 
 /
 
 B
 )
 )
 
 
 {\displaystyle O(1/B\log _{2}(N/B))}
 
 amortized I/Os. N is the number of items added to the BTR.</li>
<li>extract(T, k), which reports and deletes from T all items with key k. It requires 
 
 
 
 O
 (
 
 log
 
 2
 
 
 ⁡
 (
 N
 
 /
 
 B
 )
 +
 S
 
 /
 
 B
 )
 
 
 {\displaystyle O(\log _{2}(N/B)+S/B)}
 
 I/Os, where S is the size of the set returned by extract.</li></ul>
The algorithm simulates an internal depth-first search algorithm. A stack S of nodes is hold. During an iteration for the node v on top of S push an unvisited neighbor onto S and iterate. If there are no unvisited neighbors pop v.
The difficulty is to determine whether a node is unvisited without doing 
 
 
 
 Ω
 (
 1
 )
 
 
 {\displaystyle \Omega (1)}
 
 I/Os per edge. To do this for a node v incoming edges ⁠
 
 
 
 (
 x
 ,
 v
 )
 
 
 {\displaystyle (x,v)}
 
⁠ are put into a BRT D, when v is first discovered. Further, outgoing edges (v,x) are put into a priority queue P(v), keyed by the rank in the adjacency list.
For vertex u on top of S all edges (u,x) are extracted from D. Such edges only exist if x has been discovered since the last time u was on top of S (or since the start of the algorithm if u is the first time on top of S). For every edge (u,x) a delete(x) operation is performed on P(u). Finally a delete-min operation on ⁠
 
 
 
 P
 (
 u
 )
 
 
 {\displaystyle P(u)}
 
⁠ yields the next unvisited node. If P(u) is empty, u is popped from S.
Pseudocode for this algorithm is given below.

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 <a href="/facts/Assignment_(computer_science)/kLevAoyJ">:=</a> S.top()
6 if v is not marked:
7 mark(v)
8 extract all edges (v, x) from D, ∀x: P[v].delete(x)
9 if (u <a href="/facts/Assignment_(computer_science)/kLevAoyJ">:=</a> P[v].delete-min()) is not null:
10 S.push(u)
11 else:
12 S.pop()

13 procedure mark(v)
14 put all edges (x, v) into D
15 ∀ (v, x): put x into P[v]

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535. <a href="/wiki/Jeffrey_Vitter" target="_blank">/wiki/Jeffrey_Vitter</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Munagala, Kameshwar; Ranade, Abhiram (1999). "I/O-complexity of Graph Algorithms". Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '99. Baltimore, Maryland, USA: Society for Industrial and Applied Mathematics. pp. 687–694. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Mehlhorn, Kurt; Meyer, Ulrich (2002). "External-Memory Breadth-First Search with Sublinear I/O". Algorithms -- ESA 2002. ESA 2002. Rome, Italy: Springer Berlin Heidelberg. pp. 723–735. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Buchsbaum, Adam L.; Goldwasser, Michael; Venkatasubramanian, Michael; Westbrook, Suresh (2000). "On External Memory Graph Traversal". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '00. San Francisco, California, USA: Society for Industrial and Applied Mathematics. pp. 859–860. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

External memory graph traversal open-in-new

External memory graph traversal