Heuristic search in large problem spaces inherently
calls for algorithms capable of running under restricted
memory. This question has been investigated in a num-
ber of articles. However, in general the efficient usage
of two-layered storage systems is not further discussed.
Even if hard-disk capacity is sufficient for the problem
instance at hand, the limitation of main memory may
still represent the bottleneck for their practical appli-
cations. Since breadth-first and best-first strategies do
not exhibit any locality of expansion, standard virtual
memory management can soon result in thrashing due
to excessive page faults.
In this paper we propose a new search algorithm and
suitable data structures in order to minimize page
faults by a local reordering of the sequence of expan-
sions. We prove its correctness and completeness and
evaluate it in a real-world scenario of searching a large
road map in a commercial route planning system.