---
title: "Edge Partitioning in External-Memory Graph Search"
authors:
  - "Rong Zhou"
  - "Eric A. Hansen"
doi: ""
url: "https://ijcai.org/proceedings/2007/388"
pdf: "https://ijcai.org/proceedings/2007/0388.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2410-2416"
track: ""
keywords:
---

# Edge Partitioning in External-Memory Graph Search

Rong Zhou, Eric A. Hansen

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2410-2416.

## Abstract

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.