Edge partitioning in external-memory graph search
Rong Zhou, Eric A. Hansen · 2007
There is currently much interest in using exter-nal memory, such as disk storage, to scale up graph-search algorithms. Recent work shows that the local structure of a graph can be leveraged to substantially improve the efficiency of external-memory graph search. This paper introduces a technique, called edge partitioning, which exploits a form of local structure that has not been con-sidered in previous work. The new technique im-proves the scalability of structured approaches to external-memory graph search, and also guaran-tees the applicability of these approaches to any graph-search problem. We show its effectiveness in an external-memory graph-search algorithm for domain-independent STRIPS planning. 1