Evaluation of Baseline Methods for IDD-based SSD External Memory Search
For researchers and practitioners in heuristic search, this work provides a practical baseline for external memory search, showing that simple methods can be effective, though the contribution is incremental.
The paper evaluates simple baseline methods for immediate duplicate detection in external memory A* search, finding that a straightforward approach using a hash table with OS page caching can achieve competitive performance, reducing search time by up to 30% compared to more complex methods.
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*.