Minimizing Writes in Parallel External Memory Search
Full Text: 6938-30696-1-PB.pdf
Recent research on external-memory search has shown that disks can be effectively usedas 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 ofthe 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 spaceswith 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.
Citation
N. Sturtevant, M. Rutherford. "Minimizing Writes in Parallel External Memory Search". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Francesca Rossi), pp 666-673, August 2013.| Keywords: | search, bfs, external memory, parallel |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sturtevant+Rutherford:IJCAI13,
author = {Nathan R. Sturtevant and Matthew J. Rutherford},
title = {Minimizing Writes in Parallel External Memory Search},
Editor = {Francesca Rossi},
Pages = {666-673},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2013,
}Last Updated: July 09, 2020Submitted by Sabina P
