A Breadth-First Approach to Memory-Efficient Graph Search

Rong Zhou, Eric A. HansenAAAI 2006

Abstract

The scalability of heuristic graph search is often limited by memory rather than time. While A* is optimal in terms of node expansions, its best-first nature frequently results in a sprawling search frontier that exhausts available RAM. This paper investigates a breadth-first heuristic search framework that combines frontier search, divide-and-conquer path reconstruction, and layered duplicate detection. These techniques allow for solving large-scale graph problems—such as multiple sequence alignment and domain-independent planning—using orders of magnitude less memory than traditional best-first methods.

Introduction

The A algorithm has long been the gold standard for finding shortest paths in graphs. However, its reliance on maintaining two comprehensive lists—Open (the frontier) and Closed (visited nodes)—presents a significant bottleneck. In complex graphs with numerous cycles, linear-space alternatives like Iterative Deepening A (IDA*) often fail because they lack efficient duplicate detection, leading to exponential state regeneration.

The central challenge addressed by Zhou and Hansen (AAAI 2006) is how to perform efficient duplicate detection and path reconstruction without the prohibitive cost of storing every visited node.

The authors propose a framework that shifts the search paradigm from best-first to breadth-first, utilizing several key components:

  1. Frontier Search: By storing only the Open list (the frontier) and discarding the Closed list, the algorithm drastically reduces its memory footprint.
  2. Divide-and-Conquer Solution Recovery: To compensate for the missing Closed list, the algorithm identifies a "midpoint" node during the search. Once the goal is reached, it recursively solves subproblems from Start to Midpoint and Midpoint to Goal to reconstruct the path.
  3. Layered Duplicate Detection: In undirected graphs, duplicate states can be caught by keeping only the current and previous layers in memory. This "sweep" approach prevents the need for a global Closed list.
  4. Breadth-First Iterative-Deepening A (BFIDA): This variant uses an $f$-cost upper bound to prune nodes, iteratively increasing the bound to ensure completeness and optimality.
  5. Beam-Stack Search: For layers that still exceed memory limits, a "beam" mechanism prunes the least promising nodes, while a stacking mechanism allows for backtracking to maintain optimality.

Key Insights: The Frontier Advantage

The most significant contribution of this work is the conceptualization of the search frontier's shape. Traditional A* expands nodes based on $f$-cost ($g + h$), which often causes the search to "stretch" toward the goal along promising but narrow paths. This results in a jagged, wide frontier that consumes vast amounts of memory.

Comparison of search frontiers: Best-first (A*) vs. Breadth-first.

In contrast, breadth-first search expands nodes by $g$-cost (distance from start), maintaining a "flat" and compact frontier. While this may lead to more total node expansions, the maximum memory required at any single point in time is typically much lower. This insight shifts the focus of algorithm design from minimizing node expansions to minimizing the maximum frontier size.

Empirical Results and Applications

The breadth-first approach has shown remarkable success in several domains:

  • Multiple Sequence Alignment: In bioinformatics, "Sweep A" (a layered breadth-first variant) has been shown to use two orders of magnitude less memory than standard frontier A.
  • Symbolic Search: The layer-by-layer expansion is naturally suited for symbolic search using Binary Decision Diagrams (BDDs), where representing sets of states is more efficient than individual node processing.
  • Duplicate Handling: The paper proves that in directed graphs, the number of times a node is regenerated is linearly bounded, avoiding the exponential explosion typical of depth-first methods.

Limitations and Trade-offs

While powerful, the breadth-first approach is not a universal replacement for A*. Its advantages are most pronounced in graphs with unit edge costs where layers are clearly defined. Furthermore, saving memory often comes at the cost of increased computation time due to divide-and-conquer path reconstruction and iterative deepening. However, for many large-scale problems, this time-memory trade-off is the only way to reach a solution without crashing due to memory exhaustion.

Conclusion

By rethinking the geometry of search frontiers, Zhou and Hansen demonstrate that breadth-first strategies can overcome the memory limitations of best-first search. This framework provides a robust alternative for complex graph-search problems where duplicate detection is essential but memory is scarce.

Summary updated

BibTeX
@inproceedings{zhou2006breadth,
  author = {Rong Zhou and Eric A. Hansen},
  title = {{A Breadth-First Approach to Memory-Efficient Graph Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure