External Memory Bidirectional Search

Nathan R. Sturtevant, Jingwei Chen

Abstract: Bidirectional heuristic search is theoretically efficient but practically limited by the high memory requirements of maintaining search frontiers. This paper presents Parallel External-Memory MM (PEMM), the first algorithm to successfully adapt bidirectional search for external storage. By introducing Delayed Solution Detection (DSD), PEMM batches disk-based lookups to overcome the latency of hard drives. The authors demonstrate the efficacy of PEMM by solving the 20-move Rubik’s Cube "superflip" position via brute force, requiring 5.0 Terabytes of disk space and over 38 billion node expansions.

Introduction

Search algorithms are central to artificial intelligence, powering applications from pathfinding to complex puzzle solving. Bidirectional search—searching simultaneously from a start state and a goal state—can exponentially reduce the number of explored states compared to unidirectional search. However, it is notoriously memory-intensive. To detect when the "forward" and "backward" frontiers meet, standard algorithms require keeping both frontiers in RAM for rapid random-access lookups. When search spaces exceed RAM capacity, external memory (disks) must be used. Unfortunately, the high latency of random disk I/O makes traditional solution detection a prohibitive bottleneck.

Methods: Parallel External-Memory MM

The authors propose Parallel External-Memory MM (PEMM) to address the "random access tax" of disk-based search. PEMM builds upon the Meet-in-the-Middle (MM) algorithm, adapting it for high-latency environments through several key innovations:

  1. Delayed Solution Detection (DSD): Instead of checking for a solution with every state generation, PEMM groups states into "buckets" based on cost and hash values. Solution detection is performed only when an entire bucket is loaded into RAM for expansion, converting thousands of random probes into a single sequential batch operation.
  2. Delayed Duplicate Detection (DDD): This technique is used to batch-remove duplicate states from disk-based lists, preventing redundant work.
  3. Parallel Expansion: PEMM leverages multi-core processors to expand buckets and check for solutions across multiple threads, maximizing system throughput.
  4. Modified Termination: Because solution detection is delayed, the authors established new termination conditions and proofs of correctness to ensure optimality.
Figure 1: A sample search graph illustrating edge weights and potential search paths between nodes.

PEMM utilizes a specific priority function, $max(f, 2g)$, to ensure that the forward and backward searches meet efficiently near the midpoint of the solution path without overshooting. As illustrated in Figure 1, managing these paths efficiently is critical when the graph structure is complex.

Experimental Evaluation

The researchers evaluated PEMM using the Rubik’s Cube, a benchmark with a state space of approximately $4.3 \times 10^{19}$. The evaluation included 10 standard "Korf’s instances" and the "Superflip" position—a configuration exactly 20 moves from the goal, representing the maximum possible distance (God’s Number).

Results

The experiments demonstrated that PEMM can scale to problems previously unreachable by bidirectional search. Notably, PEMM achieved the first brute-force solution of the Rubik’s Cube superflip position.

Figure 2: Experimental results for PEMM on Rubik's Cube instances, comparing performance without heuristics against a Pattern Database (PDB) heuristic.

As shown in Figure 2, the superflip search (row 'S') required 5.0 Terabytes of disk space and 38.08 billion node expansions. When compared to a parallel version of AIDA, PEMM was 3x more efficient in node expansions and 2x faster in total time when using standard heuristics. PEMM only trailed AIDA when the latter was equipped with a massive 114 GB specialized pattern database heuristic that could fit in RAM.

Discussion and Conclusion

A key insight from this work is that the pattern of data access is often more critical than the volume of data in external memory search. By delaying solution detection, PEMM trades immediate feedback for massive I/O efficiency. Furthermore, the results suggest that brute-force search on disk can outperform heuristic search in RAM for very difficult problems where heuristics are too weak to prune the search space effectively. Future work includes testing PEMM on different graph structures, such as road networks or grids, and further optimizing the overlap between disk I/O and parallel computation.

Summary updated

Abstract

This paper studies external memory bidirectional search. That is, how bidirectional search algorithms can run using external memory such as hard drives or solid state drives. While external memory algorithms have been broadly studied in unidirectional search, they have not been studied in the context of bidirectional search. We show that the primary bottleneck in bidirectional search is the question of solution detection - knowing when the two search frontiers have met. We propose a method of delayed solution detection that makes external bidirectional search more efficient. Experimental results show the effectiveness of the approach.
BibTeX
@inproceedings{sturtevant2016external,
  author = {Nathan R. Sturtevant and Jingwei Chen},
  title = {{External Memory Bidirectional Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure