Frontier Traversal When the Graph Exceeds Cache: Top-Down Against Bottom-Up

The cost model that gives breadth-first search its O(n + m) bound counts edge examinations. On a graph of a few hundred million edges that model is misleading, because the traversal is limited not by how many operations it performs but by how many cache lines it must fetch from memory to perform them. A graph stored as compressed sparse rows occupies gigabytes, every neighbour lookup is an indirection into a target array, and the vertex identifier being looked up was chosen by the graph’s structure rather than by locality. The result is a traversal whose running time tracks memory latency rather than instruction count, and a set of techniques that restructure the loop to reduce the number of random accesses.

Where the time actually goes

A top-down breadth-first step processes a frontier of vertices, and for each vertex scans its adjacency block. The block itself is contiguous and is read sequentially — a prefetcher handles it well. But the vertices in the frontier were discovered in the previous layer, and their identifiers are scattered across the whole vertex range. Reading the block for each one is a random access into an array of size proportional to the graph.

Then, for each neighbour identifier read from the block, the algorithm tests and updates the visited array at that index. That is a second random access, this time into an array of n entries — small enough to be cache-resident only when n is small. On a graph with 10⁸ vertices a byte-per-vertex visited array is 100 MB, larger than a last-level cache, so each neighbour test is a cache miss costing hundreds of cycles.

Both costs scale with the number of edges examined, not with the number of vertices. A top-down step over a layer whose vertices have total degree D performs D neighbour tests, and on a scale-free graph — the shape that the Graph500 generator produces, with an edge factor of 16 per vertex and a heavy-tailed degree distribution — a single layer can contain a large fraction of all the edges. The step that touches the most edges is the one where the frontier is widest, which is exactly the layer where the top-down loop has the most parallelism and the worst locality.

The bottom-up inversion

The alternative step reverses the quantification. Instead of asking, for each frontier vertex, which of its neighbours are unvisited, it asks, for each unvisited vertex, whether any of its in-neighbours is in the frontier. If one is, the vertex joins the next frontier.

// bottom-up step: bitmap of frontier, bitmap of visited
for (int64_t v = 0; v < n; ++v) {
    if (visited[v]) continue;
    for (int64_t i = start[v]; i < start[v + 1]; ++i) {
        int64_t u = target[i];
        if (frontier_bit[u]) {       // neighbour already reached
            next_frontier[v] = 1;
            visited[v] = 1;
            break;                   // no need to see the rest
        }
    }
}

Three properties change. The outer loop walks vertices in identifier order, so the accesses to start and target are sequential and prefetchable. The test against frontier_bit is a lookup in a bitmap of n bits — 12.5 MB at 10⁸ vertices, small enough that a large fraction stays cached and each test is one bit within a line that is likely already loaded. And the inner loop breaks at the first hit, so a vertex discovered early in its adjacency block costs a fraction of its degree.

The work is now bounded by the sum of degrees of the unvisited vertices rather than of the frontier. Early in the search almost everything is unvisited and the frontier is tiny, so bottom-up examines a huge number of edges to find a handful of discoveries. Late in the search, when most vertices are visited, the outer loop skips them with one bitmap test each and the inner loops run on the remaining few. The two directions are efficient in opposite regimes, and neither is efficient throughout.

The switch

Direction-optimizing BFS runs top-down while the frontier is small and switches to bottom-up when it grows. The decision rule compares the work the two directions would do. Top-down examines the sum of degrees of the frontier; bottom-up examines the sum of degrees of the unvisited set. Both are computable incrementally: the first by summing degrees as the frontier is built, the second by maintaining a running total of degrees of unvisited vertices and subtracting as vertices are discovered.

A common formulation switches when the frontier’s edge count exceeds the unvisited set’s edge count divided by a tuning constant, so that bottom-up is chosen only when it is expected to do meaningfully less work. The constant accounts for the fact that a bottom-up edge examination is cheaper than a top-down one — sequential access, cached bitmap, early break — so bottom-up wins even when it examines somewhat more edges. The published algorithm uses two thresholds, one to enter the bottom-up phase and one to leave it, to prevent oscillation when the two estimates are close.

Leaving bottom-up is necessary because the direction must eventually produce a frontier to continue from. The bottom-up step computes the next frontier implicitly, as the set of vertices it marked; converting that set into an explicit queue costs a scan of the unvisited vertices, which is O(n) and is why the switch back happens only when the frontier has shrunk enough to make the O(n) scan worthwhile.

The correctness argument is unaffected by direction. Both steps compute exactly the set of vertices at distance k+1 from the set at distance k, so the layer invariant that justifies ordinary BFS holds throughout. What changes is the number of memory accesses, and the direction can be switched at any layer boundary without changing the distances or the layer count.

What the parent pointers cost

The bottom-up step as written does not record which neighbour caused a discovery, so it cannot build a search tree or reconstruct a shortest path. That is a real restriction: the direction-optimizing formulation is used for distance-only queries, and applications needing parents either run top-down throughout, or run a second pass after the distances are known to recover one parent per vertex — for each vertex at distance k+1, find any neighbour at distance k. The second pass costs another full sweep over the edges but is trivially parallel and can be restricted to the layers that matter.

This is a general pattern in large-scale traversal: computing the distance labelling and computing the tree are separated because the tree needs a serialization of discovery order that the parallel, direction-switched loop does not naturally provide. Implementations that try to record parents inside the bottom-up loop reintroduce the random write that the inversion was designed to avoid, and lose most of the gain.

Parallelism and the partitioning question

Both steps parallelize, but with different granularities. The top-down step distributes frontier vertices across threads; each thread owns a slice of the frontier and performs independent neighbour tests, with the visited array written concurrently. Races are benign in the sense that two threads marking the same vertex produce the same result, but they still cost coherence traffic, and implementations use atomic bit operations or per-thread frontier buffers that are merged after the step. The merge is a set union over up to n vertices, which is itself a memory-bound pass.

The bottom-up step distributes the unvisited vertex range, which is static and balanced by construction — each thread gets a contiguous range of identifiers regardless of degree. Load imbalance appears only from the degree distribution within a range, and the early break limits the damage. This is a much easier parallel decomposition than the frontier-driven one, and it is one reason the bottom-up step scales well on shared-memory machines.

The partitioning question dominates distributed implementations. If the graph is partitioned by vertex identifier, an edge almost always crosses a partition boundary, and a top-down step must fetch remote adjacency blocks. Partitioning by edge structure — so that most neighbours of a vertex live in the same partition — reduces remote traffic but costs a preprocessing pass and complicates the visited-array lookup, since a vertex’s state now lives wherever its owner partition is. The 2D and hybrid partitioning schemes used in distributed BFS exist to trade replication of the visited bitmap against communication of the frontier.

The regime where none of it helps

Direction optimization pays on graphs with a heavy-tailed degree distribution and a small diameter, where a few layers cover most vertices and the frontier briefly becomes enormous. On a graph that is a long path or a large grid, every layer holds only a small fraction of the vertices, the bottom-up step never becomes profitable, and the switch rule keeps the traversal top-down throughout. On a graph with uniform low degree and high diameter the frontier never exceeds a small fraction of n, and the whole technique reduces to ordinary BFS with extra bookkeeping.

The same limitation applies to memory. Bottom-up requires the unvisited set to be enumerated by identifier, which requires n to be known and dense. Graphs whose vertices are arbitrary identifiers, or whose unvisited set is naturally represented as a hash set, cannot scan it sequentially. Relabelling into 0..n−1 — the same remapping that compressed sparse row construction requires — is a precondition, not an optimization.

Finally, the direction switch is a heuristic without a worst-case guarantee. An adversary can construct a graph where the switch happens at the wrong layer and the traversal does more work than plain top-down would have. The published results are on benchmark graphs from the Graph500 generator and on social-network-shaped inputs; the technique’s justification is empirical, and its complexity bound is unchanged either way, since both directions are linear in the edge count.

For graphs that genuinely do not fit in memory, the frontier must be spilled and the adjacency blocks re-read per layer. The number of passes equals the diameter, which for a small-world graph is a handful and for a road network is in the thousands — which is why component labelling and other algorithms on such graphs prefer repeated scanning of the whole edge list over a layer-by-layer traversal.