Edge Partitioning in External-Memory Graph Search
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.
@inproceedings{ijcai2007p388,
title = {Edge Partitioning in External-Memory Graph Search},
author = {Zhou, Rong and Hansen, Eric A.},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2410--2416},
year = {2007},
url = {https://ijcai.org/proceedings/2007/388},
}
TY - CPAPER TI - Edge Partitioning in External-Memory Graph Search AU - Zhou, Rong AU - Hansen, Eric A. T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2410 EP - 2416 UR - https://ijcai.org/proceedings/2007/388 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
