Parallel structured duplicate detection

Abstract

We describe a novel approach to parallelizing graph search using structured duplicate detection. Structured duplicate detection was originally developed as an approach to externalmemory graph search that reduces the number of expensive disk I/O operations needed to check stored nodes for duplicates, by using an abstraction of the search graph to localize memory references. In this paper, we show that this approach can also be used to reduce the number of slow synchronization operations needed in parallel graph search. In addition, we describe several techniques for integrating parallel and external-memory graph search in an efficient way. We demonstrate the effectiveness of these techniques in a graphsearch algorithm for domain-independent STRIPS planning.