Minimizing Writes in Parallel External Memory Search
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.
Cite
Text
Sturtevant and Rutherford. "Minimizing Writes in Parallel External Memory Search." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Sturtevant and Rutherford. "Minimizing Writes in Parallel External Memory Search." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/sturtevant2013ijcai-minimizing/)BibTeX
@inproceedings{sturtevant2013ijcai-minimizing,
title = {{Minimizing Writes in Parallel External Memory Search}},
author = {Sturtevant, Nathan R. and Rutherford, Matthew J.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {666-673},
url = {https://mlanthology.org/ijcai/2013/sturtevant2013ijcai-minimizing/}
}