Minimizing Writes in Parallel External Memory Search

Sturtevant, Nathan R.; Rutherford, Matthew J.

Minimizing Writes in Parallel External Memory Search

Nathan R. Sturtevant, Matthew J. Rutherford

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 666-672.

Abstract

Recent research on external-memory search has shown that disks can be effectively used as secondary storage when performing large breadth-first searches. We introduce the Write-Minimizing Breadth-First Search (WMBFS) algorithm which is designed to minimizethe number of writes performed in an external-memory BFS. WMBFS is also designed to store the results of the BFS for later use.We present the results of a BFS on a single-agent version of Chinese Checkers and the Rubik's Cube edge cubes, state spaces with about 1 trillion states each. In evaluating against a comparable approach, WMBFS reduces the I/O for the Chinese Checkers domain by over an order of magnitude. In Rubik's cube, in addition to reducing I/O, the search is also 3.5 times faster. Analysis of the results suggests the machine and state-space properties necessary for WMBFS to perform well.

Nathan R. Sturtevant, and Matthew J. Rutherford. 2013. Minimizing Writes in Parallel External Memory Search. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 666–672. https://ijcai.org/proceedings/2013/105

@inproceedings{ijcai2013p105,
  title     = {Minimizing Writes in Parallel External Memory Search},
  author    = {Sturtevant, Nathan R. and Rutherford, Matthew J.},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {666--672},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/105},
}

TY  - CPAPER
TI  - Minimizing Writes in Parallel External Memory Search
AU  - Sturtevant, Nathan R.
AU  - Rutherford, Matthew J.
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 666
EP  - 672
UR  - https://ijcai.org/proceedings/2013/105
ER  -