---
title: "Minimizing Writes in Parallel External Memory Search"
authors:
  - "Nathan R. Sturtevant"
  - "Matthew J. Rutherford"
doi: ""
url: "https://ijcai.org/proceedings/2013/105"
pdf: "https://ijcai.org/proceedings/2013/0105.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "666-672"
track: ""
keywords:
---

# Minimizing Writes in Parallel External Memory Search

Nathan R. Sturtevant, Matthew J. Rutherford

*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.