Abstract
Traditional external memory search algorithms rely on Delayed Duplicate Detection (DDD) to mitigate the slow random access speeds of hard disk drives. However, the advent of Solid State Drives (SSDs) offers significantly better random access performance. This paper explores the feasibility of Immediate Duplicate Detection (IDD) on SSDs. We introduce "Segmented Compression," a novel technique that utilizes a small in-memory mapping table to filter out false positive disk probes. Our results show that A*-IDD with segmented compression can outperform DDD-based methods by 3x to 5x on complex planning tasks, effectively reducing I/O overhead and node expansions.
Introduction
The "gold standard" for external memory search has long been Delayed Duplicate Detection (DDD). By processing duplicates in large, sorted batches, DDD minimizes the random I/O operations that are catastrophic for performance on Hard Disk Drives (HDDs). However, this batching comes at a cost: the algorithm cannot prune duplicates immediately, leading to redundant node expansions and inefficient tie-breaking.
With the transition to Solid State Drives (SSDs), random access latency has decreased by orders of magnitude. This technological shift invites a reconsideration of Immediate Duplicate Detection (IDD), where nodes are checked against the "closed list" as soon as they are generated.
Methodology: Segmented Compression
A naive implementation of IDD on SSDs still faces bottlenecks due to "false positive" disk probes. In standard compression, an in-memory hash table stores pointers to node data on the SSD. Hash collisions can lead the algorithm to fetch a node from the SSD only to find it is not a true duplicate, wasting valuable I/O.
To address this, we introduce Segmented Compression. This technique adds a secondary mapping table in RAM. The SSD storage is partitioned into "write segments," and the mapping table tracks secondary hash values (partition values) for each segment. Before performing a disk read, the algorithm verifies the partition value in the mapping table. If it doesn't match, the disk probe is skipped.
Experimental Evaluation
We evaluated A*-IDD on 34 instances from the International Planning Competition (IPC) and the classic 15-puzzle. The IPC instances represent complex logic puzzles with large state descriptions, while the 15-puzzle provides a benchmark for domains with small, easily generated states.
Results and Discussion
The impact of segmented compression is most evident in the reduction of false positive (FP) probes. As shown in the experimental data, increasing the number of partitions ($p$) significantly lowers the ratio of FP probes to total probes. With $p=100$, false positives are nearly eliminated, allowing the search to proceed with minimal I/O overhead.
In the IPC planning tasks, A-IDD solved 33 out of 34 problems, outperforming standard compression (27/34) and achieving 3x to 5x speedups over DDD-based External A. A key advantage of IDD is its ability to terminate immediately upon finding a goal, avoiding the "final layer penalty" inherent to DDD, which must process all nodes in the final search frontier.
However, DDD remains more efficient for simpler problems like the 15-puzzle. In such cases, the cost of generating a node is so low that even optimized random SSD access becomes a relative bottleneck compared to batch processing.
Conclusion
The shift to SSD hardware necessitates a shift in algorithmic design. Segmented compression makes IDD a highly competitive strategy for external memory search, particularly for complex domains where immediate pruning and efficient tie-breaking are critical. Future work will focus on improving page locality to further optimize SSD performance.
Summary updated