Domain-independent structured duplicate detection

• Twenty-First National Conference on Artificial Intelligence (AAAI 2006)

The scalability of best-first and breadth-first search algorithms can be greatly extended by using external memory, such as disk, to store generated nodes. We consider structured duplicate detection, an approach to external-memory graph search that limits the number of slow disk I/O operations needed to access search nodes stored on disk by using an abstract representation of the graph to localize memory references. For graphs with sufficient locality, structured duplicate detection outperforms other approaches to external-memory graph search. We describe an automatic method for creating an abstract representation that reveals the local structure of a graph. We then integrate this approach into a domain-independent STRIPS planner and show that it dramatically improves scalability for a wide range of planning problems. The success of this approach strongly suggests that similar local structure can be found in many other graph-search problems.

citation

Zhou, R. ; Hansen, E. A. Domain-independent structured duplicate detection. Twenty-First National Conference on Artificial Intelligence (AAAI 2006); 2006 July 16-20; Boston; MA.