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:
- 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.
- Delayed Duplicate Detection (DDD): This technique is used to batch-remove duplicate states from disk-based lists, preventing redundant work.
- Parallel Expansion: PEMM leverages multi-core processors to expand buckets and check for solutions across multiple threads, maximizing system throughput.
- Modified Termination: Because solution detection is delayed, the authors established new termination conditions and proofs of correctness to ensure optimality.
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.
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