The Memory Wall in Graph Search
Standard graph search algorithms like A* or Breadth-First Search (BFS) are fundamentally constrained by memory. To guarantee optimality and avoid infinite loops, these algorithms must track every state they visit. Traditionally, this is achieved by maintaining an in-memory hash table of "closed" states. When a new state is generated, the algorithm performs a rapid random-access lookup to see if it has been encountered before.
As search spaces scale into billions or trillions of nodes, this table quickly outgrows physical RAM. Moving the hash table to external storage, such as hard drives or solid-state disks, introduces a severe performance bottleneck. External storage devices excel at streaming large blocks of data sequentially but suffer massive latency penalties when subjected to random-access patterns. If a search algorithm attempts to perform a random disk lookup for every generated node, the system spends almost all its time waiting for disk I/O, causing the search to grind to a halt.
Deferring the Check: From Random to Sequential I/O
The core insight behind overcoming this memory wall is to decouple state generation from duplicate checking. Instead of asking "Have we seen this node before?" the exact moment a node is generated, the algorithm defers the question. Newly generated nodes are simply appended to a sequential log file on disk.
By delaying the duplicate check, the algorithm transforms a chaotic sequence of random-access memory lookups into structured, high-bandwidth sequential I/O operations. Disk storage is highly optimized for streaming data sequentially, making this batch-based approach orders of magnitude faster than real-time disk lookups. As pioneered by Korf in Delayed Duplicate Detection: Extended Abstract, this shift allows search algorithms to bypass RAM capacity limits entirely, shifting the boundary of solvable problems to the capacity of secondary storage.
Sorting-Based Duplicate Elimination
To resolve duplicates in a deferred system, the accumulated states must periodically be reconciled. One elegant way to achieve this without random memory access is through sorting.
When a search layer or an expansion buffer fills up, the algorithm performs a bulk sort-merge operation on the disk files. Because identical states sort to adjacent positions, a single sequential scan through the sorted file can identify and remove all redundant nodes.
[Unsorted Log on Disk] --> [External Sort-Merge] --> [Sorted Log] --> [Sequential Scan]
(State B, A, B, C, A) (High-bandwidth I/O) (A, A, B, B, C) (Duplicates removed)
As detailed by Edelkamp et al. in Cost-Optimal External Planning, this sorted scan allows external-memory planners to validate massive state spaces against existing disk-resident layers without incurring random-access penalties. The authors demonstrate that calculating the exact "locality"—the minimum number of search layers needed to prevent redundant work—allows for highly efficient disk-to-disk comparisons. Korf et al. demonstrated the power of this technique in Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem, scaling search to spaces containing over $10^{18}$ nodes by relying purely on sequential file merges.
Hash-Based Partitioning and Reference Locality
While sorting is highly effective, it introduces an $O(N \log N)$ computational overhead. An alternative mechanism uses hash functions or state-space abstractions to partition the state space into discrete, independent files or "buckets" on disk.
The intuition here is simple: if we can guarantee that a state and all its potential duplicates always map to the exact same bucket, we do not need to search the entire disk to find a match. We only need to look inside that specific bucket.
Generated State ──> Hash Function ──> Maps to Bucket #3 ──> Append to Disk File #3
│
[When Bucket #3 is loaded] ──┘
Exact duplicate check happens in RAM
In Best-First Frontier Search with Delayed Duplicate Detection, Korf showed that distributing nodes into hash-indexed files allows final duplicate checks to occur entirely within RAM. When a specific bucket is loaded into memory, all potential duplicates for those states are guaranteed to be present.
This achieves what Zhou et al. term reference locality in Structured Duplicate Detection in External-Memory Graph Search. By using state-space abstractions to constrain duplicate checks to a small, active subset of data currently held in fast memory, the algorithm ensures that the open and closed lists do not need to reside entirely in RAM simultaneously. Korf et al. leveraged this bucketed approach in Large-Scale Parallel Breadth-First Search to completely map the 10-trillion-state Fifteen Puzzle, proving that hash-based partitioning scales efficiently across massive datasets.
Scaling to Real-World Complexity
Modern iterations of delayed duplicate detection have evolved to handle complex, non-uniform search spaces, real-valued edge costs, and parallel architectures.
When dealing with real-valued edge costs rather than uniform unit steps, standard breadth-first layering breaks down because states in the same layer can have wildly different costs. To solve this, Hatem et al. introduced PEDAL in Heuristic Search for Large Problems With Real Costs, which dynamically layers and buckets states on disk, deferring duplicate removal until a specific bucket is processed in RAM. This was further expanded by Hatem et al. in External Memory Best-First Search for Multiple Sequence Alignment to tackle massive bioinformatics problems, showing that hash-based delayed duplicate detection can handle complex biological alignment constraints without constant memory residency.
Furthermore, the bucketed architecture naturally lends itself to parallel processing and bidirectional search. As shown by Siag et al. in On Parallel External-Memory Bidirectional Search (Extended Abstract) and Shperberg et al. in On Parallel External-Memory Bidirectional Search, partitioning search frontiers into disk-resident buckets allows multiple threads to expand and deduplicate independent regions of the state space simultaneously.
Whether learning optimal Bayesian networks (Malone et al. in Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search) or exploring combinatorial puzzles (Hatem in Heuristic Search for Large Problems with Real Costs), delayed duplicate detection shifts the fundamental constraint of graph search. By trading immediate verification for deferred, sequential batch processing, it allows algorithms to scale gracefully far beyond the physical limitations of RAM.
Key Foundational Work
Best-First Frontier Search with Delayed Duplicate Detection (2004) — contributed 4 concept elements to this direction.
Delayed Duplicate Detection: Extended Abstract (2003) — contributed 1 concept elements to this direction.
Structured Duplicate Detection in External-Memory Graph Search (2004) — contributed 1 concept elements to this direction.