Proceedings

Edge Partitioning in External-Memory Graph Search

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2410-2416.

© 2007 International Joint Conferences on Artificial Intelligence

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.

  1. [Edelkamp et al., 2004] S. Edelkamp, S. Jabbar, and S. Schrödl. External A*. In Proc. of the 27th German Conf. on Artificial Intelligence, pages 226-240, 2004.
  2. [Haslum and Geffner, 2000] P. Haslum and H. Geffner. Ad- missible heuristics for optimal planning. In Proc. of the 5th International Conference on AI Planning and Scheduling, pages 140-149, 2000.
  3. [Korf and Schultze, 2005] R. Korf and P. Schultze. Large- scale parallel breadth-first search. In Proc. of the 20th National Conference on Artificial Intelligence (AAAI-05), pages 1380-1385, 2005.
  4. [Korf, 2004] R. Korf. Best-first frontier search with delayed duplicate detection. In Proc. of the 19th National Conf. on Artificial Intelligence (AAAI-04), pages 650-657, 2004.
  5. [Munagala and Ranade, 1999] K. Munagala and A. Ranade. I/O-complexity of graph algorithms. In Proc. of the 10th Symposium on discrete algorithms, pages 687-694, 1999.
  6. [Stern and Dill, 1998] U. Stern and D. Dill. Using magnetic disk instead of main memory in the mur(phi) verifier. In Proc. of the 10th International Conference on Computer- Aided Verification, pages 172-183, 1998.
  7. [Zhou and Hansen, 2004] R. Zhou and E. Hansen. Struc- tured duplicate detection in external-memory graph search. In Proc. of the 19th National Conference on Ar- tificial Intelligence (AAAI-04), pages 683-688, 2004.
  8. [Zhou and Hansen, 2005] R. Zhou and E. Hansen. External- memory pattern databases using structured duplicate de- tection. In Proc. of the 20th National Conference on Arti- ficial Intelligence (AAAI-05), pages 1398-1405, 2005.
  9. [Zhou and Hansen, 2006a] R. Zhou and E. Hansen. Breadth- first heuristic search. Artificial Intelligence, 170(4-5):385- 408, 2006.
  10. [Zhou and Hansen, 2006b] R. Zhou and E. Hansen. Domain- independent structured duplicate detection. In Proc. of the 21st National Conference on Artificial Intelligence (AAAI- 06), pages 1082-1087, 2006.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards