Evaluation of Baseline Methods for IDD-based SSD External Memory Search
2026-06-01 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors looked at ways to improve the A* search algorithm when it runs out of fast memory (RAM) and has to use slower external storage like SSDs or hard drives. Previous research focused on complicated methods to avoid re-examining the same states, but the authors studied simpler methods for this duplicate checking step. They also explored how computer operating systems help speed up external memory access, which was not studied before. Their work fills gaps by analyzing the performance of these straightforward approaches when doing immediate duplicate detection in A*.
A* search algorithmRAMexternal memorySSDHDDimmediate duplicate detection (IDD)delayed duplicate detectionpage cachesearch algorithms
Authors
Yuki Suzuki, Alex Fukunaga
Abstract
Many difficult search problems cannot be solved by algorithms such as A* using only RAM. Search algorithms which use external memory such as SSDs and HDDs with much higher capacity than RAM have been proposed in previous work, but previous work has focused on delayed duplicate detection approaches, as well as complex immediate duplicate detection (IDD) methods, and relatively simple methods for IDD have not been systematically studied. In addition, the effect of OS-level mechanisms for managing and speeding up accesses to external memory, such as page caches, has not been studied. This paper addresses these gaps in the literature by evaluating and analyzing the performance of simple baseline approaches for IDD-based A*.