Parallel Structured Duplicate Detection

Rong Zhou, Eric A. Hansen

We describe a novel approach to parallelizing graph search using structured duplicate detection. Structured duplicate detection was originally developed as an approach to external-memory 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 graph-search algorithm for domain-independent STRIPS planning.

Subjects: 15.7 Search; 1.11 Planning

Submitted: Apr 25, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.