External Memory Search for Massive State Spaces

This direction is merged into another direction: memory-constrained search. Its last version stays readable and citable here.

Version 1 of 115 papers20 conceptsfrozen 2026-10-04

In graph search, memory is almost always a more restrictive bottleneck than time. Algorithms like A* are designed to find the shortest path by maintaining two lists: an "Open" list of nodes to visit and a "Closed" list of nodes already visited. While this prevents the algorithm from spinning in circles, the Closed list grows linearly with the number of states explored. For massive problems like the 4-peg Towers of Hanoi or large-scale genomic sequence alignment, the Closed list quickly hits the "memory wall," exhausting available RAM and crashing the search.

To solve problems with billions or trillions of states, researchers have developed techniques to move the search process from volatile RAM to high-capacity external storage (hard disks and SSDs) while minimizing the performance penalties of slow disk access.

The Problem with Random Access

The primary challenge of using a hard drive as "extra RAM" is the massive disparity between sequential and random access speeds. A standard search algorithm performs "duplicate detection" by checking if a newly generated state already exists in the Closed list. In RAM, this is a near-instantaneous hash table lookup. On a disk, however, performing millions of random lookups would be orders of magnitude slower than the search itself, as the disk head must physically move to different sectors.

To overcome this, researchers like Richard E. Korf and Matthew Hatem propose treating external storage as a high-bandwidth sequential resource. Instead of checking for duplicates one by one, the algorithm batches them.

Delayed Duplicate Detection

Richard E. Korf introduced Delayed Duplicate Detection (DDD) to bridge the gap between search speed and disk latency. In Delayed Duplicate Detection: Extended Abstract, the process is reimagined as a large-scale sorting task:

  1. Expansion: The algorithm expands all nodes at a specific depth and writes the resulting children to a large file on disk without checking for duplicates.
  2. Sorting: Once the expansion is complete, the file is sorted sequentially.
  3. Purging: A single sequential pass through the sorted file identifies and removes duplicate states (which are now adjacent to each other).

By turning random lookups into sequential I/O, DDD allows search algorithms to utilize the full capacity of external drives. This technique enabled the exhaustive search of the 2x7 sliding-tile puzzle and complex Towers of Hanoi configurations that were previously impossible to fit in memory.

Frontier Search and Boundary Storage

Even with disk-based storage, storing every visited node is expensive. Frontier Search reduces the memory footprint by storing only the "frontier"—the boundary between the explored and unexplored parts of the graph.

As Richard E. Korf and Ariel Felner demonstrate in Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem, you can safely delete the "interior" nodes of the search tree if you have a way to prevent the search from immediately backtracking. They achieve this by storing "used-operator bits" with each node—metadata that tracks which actions have already been taken, effectively blocking the path back to the parent without needing to store the parent in a Closed list.

For games with specific structures, like solitaire, Bernard Helmstetter showed in Searching with Analysis of Dependencies in a Solitaire Card Game that one can store only the states at the edges of multi-dimensional blocks, further compressing the representation of the search space.

Structured Duplicate Detection

While DDD relies on sorting, Structured Duplicate Detection (SDD) uses the inherent geometry of the problem to partition the state space. Rong Zhou 0001 and Eric A. Hansen developed a method to automatically discover "local structure" in a search problem.

In Domain-Independent Structured Duplicate Detection, they explain how to divide the state space into "buckets." When the algorithm is expanding nodes in Bucket A, it knows (based on the problem's rules) that the children can only possibly land in Buckets A, B, or C. Therefore, only those specific buckets need to be in RAM. The rest of the search space can remain on disk, significantly reducing the memory overhead for duplicate detection without requiring a full sort of the data.

Scaling to Real-World Complexity

These techniques have moved beyond toy puzzles into high-stakes computational problems. George T. Heineman and colleagues applied sequential memory-access schemes to dynamic programming in Improved Lower Bounds on the Expected Length of Longest Common Subsequences, pushing the mathematical bounds of string comparison by bypassing RAM limits.

Similarly, Nathan R. Sturtevant and Jingwei Chen extended these ideas to External Memory Bidirectional Search, introducing "Delayed Solution Detection" to find where two search frontiers meet across terabytes of disk storage. By combining parallel processing with I/O-efficient batching, these researchers have transformed the hard drive from a slow storage medium into a primary engine for large-scale artificial intelligence.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_external_memory_search_for_massive_state_93b29806,
  title = {External Memory Search for Massive State Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/external-memory-search-for-massive-state-spaces/rdr_93b298064696490cb32a16741368516b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_external_memory_search_for_massive_state_93b29806_v1,
  title = {External Memory Search for Massive State Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/external-memory-search-for-massive-state-spaces/rdr_93b298064696490cb32a16741368516b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}