External memory graph traversal

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

External memory graph traversal is a type of graph traversal optimized for accessing externally stored memory.

External memory graph traversal is a type of graph traversal optimized for accessing externally stored memory.

Background

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 breadth-first search and depth-first search, are analyzed using the von Neumann 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 external memory exists. Let L(t) denote the nodes in breadth-first search level t and let A(t):=N(L(t-1)) be the multi-set of neighbors of level t-1.

For every t, L(t) can be constructed from A(t) by transforming it into a set and excluding previously visited nodes from it. Create A(t) by accessing the adjacency list of every vertex in L(t-1) . This step requires O(|L(t-1)|+|A(t)|/(D\cdot B)) I/Os.

Next A'(t) is created from A(t) by removing duplicates. This can be achieved via sorting of A(t) , followed by a scan and compaction phase needing O(\operatorname{sort}(|A|)) I/Os. L(t):=A'(t)\backslash\{L(t-1)\cup L(t-2)\} is calculated by a parallel scan over L(t-1) and L(t-2) and requires O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B)) I/Os.

The overall number of I/Os of this algorithm follows with consideration that \sum_t |A(t)|=O(m) and \sum_t |L(t)|=O(n) and is 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. During the preprocessing phase the graph is partitioned into disjointed subgraphs S_i,\,0\leq i\leq K with small diameter.

It further partitions the adjacency lists accordingly, by constructing an external file F=F_0F_1\dots F_{K-1} , where F_i contains the adjacency list for all nodes in S_i . The breadth-first search phase is similar to the MR algorithm. In addition the algorithm maintains a sorted external file . This file is initialized with F_0 .

Further, the nodes of any created breadth-first search level carry identifiers for the files F_i of their respective subgraphs S_i . Instead of using random accesses to construct L(t) the file is used. Perform a parallel scan of sorted list L(t-1) and . Extract the adjacency lists for nodes v\in L(t-1) , that can be found in .

The adjacency lists for the remaining nodes that could not be found in need to be fetched. A scan over L(t-1) yields the partition identifiers. After sorting and deletion of duplicates, the respective files F_i can be concatenated into a temporary file .

The missing adjacency lists can be extracted from with a scan. Next, the remaining adjacency lists are merged into with a single pass. A(t) is created by a simple scan.

The partition information is attached to each node in A(t) . The algorithm proceeds like the MR algorithm. Edges might be scanned more often in , but unstructured I/Os in order to fetch adjacency lists are reduced.

The overall number of I/Os for this algorithm is O\left(\sqrt\frac{n\cdot(n+m)}{D\cdot B}+\operatorname{sort}(n+m)\right) 5 v := 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 := 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]

Text derived from https://en.wikipedia.org/w/index.php?oldid=1315185311 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001315185311 · captured 1759645585.0 · version history

Cite this page as: encyclopegia.org, “External memory graph traversal”, snapshot enwiki-001315185311. https://encyclopegia.org/a/external-memory-graph-traversal

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.