Revisiting Immediate Duplicate Detection in External Memory Search

Authors

  • Shunji Lin The University of Tokyo
  • Alex Fukunaga The University of Tokyo

DOI:

https://doi.org/10.1609/aaai.v32i1.11526

Keywords:

Heuristic Search, External Memory Search, Immediate Duplicate Detection, Delayed Duplicate Detection, SSD

Abstract

External memory search algorithms store the open and closed lists in secondary memory (e.g., hard disks) to augment limited internal memory. To minimize expensive random access in hard disks, these algorithms typically employ delayed duplicate detection (DDD), at the expense of processing more nodes than algorithms using immediate duplicate detection (IDD). Given the recent ubiquity of solid state drives (SSDs), we revisit the use of IDD in external memory search. We propose segmented compression, an improved IDD method that significantly reduces the number of false positive access into secondary memory. We show that A*-IDD, an external search variant of A* that uses segmented compression-based IDD, significantly improves upon previous open-addressing based IDD. We also show that A*-IDD can outperform DDD-based A* on some domains in domain-independent planning.

Downloads

Published

2018-04-25

How to Cite

Lin, S., & Fukunaga, A. (2018). Revisiting Immediate Duplicate Detection in External Memory Search. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11526

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization