Introduction
Standard graph search algorithms like Breadth-First Search (BFS) or A* are notoriously memory-intensive. To prevent redundant computation, these algorithms must store every "visited" node to perform duplicate detection. In massive problem spaces, RAM is often exhausted within minutes. While secondary storage like magnetic disks or SSDs offers terabytes of capacity at a low cost, their slow random-access speeds make traditional hash tables impractical.
To address this, researchers utilize Delayed Duplicate Detection (DDD), which processes nodes in bulk using sequential disk access. This paper investigates the long-standing debate between two primary DDD approaches: sorting nodes to find duplicates versus hashing them into separate files.
Methods: Sorting vs. Hashing
The authors evaluate two distinct flavors of DDD:
- Sorting-Based DDD: Nodes are written to disk, sorted by their state representation to bring duplicates together, and then merged in a single linear scan.
- Hashing-Based DDD: A "file hash" function assigns nodes to different files on disk. Each file is subsequently loaded into memory, where a "memory hash" function identifies duplicates within that specific subset.
The Pipelining Innovation
A core technical contribution of this work is the application of pipelining to the hashing-based approach. Traditional methods use separate "expansion" and "merge" phases, which doubles disk I/O. By combining these phases, the authors allow the algorithm to generate and hash children for the next level immediately as the current level's nodes are de-duplicated. This minimizes data movement and significantly boosts performance.
Experimental Setup
The algorithms were tested on three combinatorial "stress tests" with varying graph properties:
- Sliding-tile puzzles (14-puzzle): Features even-length cycles where duplicates appear every two levels.
- Rubik’s Cube (10-cubie subspace): A complex space with arbitrary cycle lengths.
- 4-peg Towers of Hanoi (21-disc): A space with arbitrary cycles requiring complex "look-back" logic.
Key Results
The experimental data reveals a clear trade-off between time and space efficiency across all tested domains.
Speed vs. Space Trade-off
As shown in the table above, hashing consistently wins on time. The pipelined hashing algorithm (Hash-P) was 45% faster on the 14-puzzle, 58% faster on the Rubik’s Cube subspace, and 48% faster on the Towers of Hanoi compared to the sorting-based version (Sort-P).
Conversely, sorting wins on space. Sorting required 25% to 35% less disk storage (S space vs. H space) than hashing. This is because sorting can merge duplicates in an in-memory buffer before writing to disk, significantly reducing the footprint of intermediate files.
Disk Performance vs. RAM
One of the most counter-intuitive findings is that disk-based search can match or even exceed the speed of in-memory search. On the Thirteen Puzzle, the disk-based algorithm generated 13.34 million nodes per second, while the best in-memory version generated 12.48 million. This parity exists because modern operating systems are highly efficient at buffering sequential file I/O. When disk access is linear, the CPU—rather than the hardware—often becomes the bottleneck. Furthermore, the disk version benefits from using many small, cache-friendly hash tables rather than one massive, cache-unfriendly table in RAM.
Conclusion
While hashing-based DDD with pipelining offers superior speed, sorting-based DDD remains a vital tool for space-constrained environments. The study proves that with efficient sequential I/O and pipelining, disk-based search is a highly competitive alternative to traditional in-memory methods for large-scale state-space exploration.
Summary updated