homeresources & publications › edge partitioning in external-memory graph search


Edge partitioning in external-memory graph search


There is currently much interest in using external 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

considered in previous work. The new technique improves the scalability of structured approaches to external-memory graph search, and also guarantees 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.


Zhou, R. ; Hansen, E. A. Edge partitioning in external-memory graph search. Twentieth International Joint Conference on Artificial Intelligence (IJCAI 2007); 2007 January 6-12; Hyderabad; India; 2410-2416.