Revisiting Immediate Duplicate Detection in External Memory Search

Shunji Lin, Alex FukunagaAAAI 2018 · DOI

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.

Comparison of (a) standard compression and (b) the proposed segmented compression architecture.

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.

Performance metrics for segmented compression across different partition values (p).

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

BibTeX
@inproceedings{lin2018revisiting,
  author = {Shunji Lin and Alex Fukunaga},
  title = {{Revisiting Immediate Duplicate Detection in External Memory Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11526},
}

Loading related content...

Figure