RI-Small: Structured Duplicate Detection: A New Approach to External-Memory and Parallel Graph Search

本项目将开发一种基于结构化重复检测的状态空间启发式搜索方法，利用图的局部性和结构来提高重复检测的效率。结构化重复检测为以下提供了基础：（a）一种新的外部存储器图搜索方法，该方法将存储器层次结构与搜索空间对齐，使得例如，在任何时候只有一小部分已经探索过的节点需要存储在RAM中以执行重复检测，（B）并行图搜索的新方法，其中使用保持图局部性的状态空间的抽象表示来在处理器之间划分存储的节点，以及（c）通过将部分模式数据库存储在磁盘上并将它们分布在多个处理器中，来创建和学习更大和更精确的模式数据库算法的新方法。但是，由于状态空间图搜索是人工智能和计算机科学其他分支中的一种普遍技术，因此该项目开发的新技术有可能使许多应用领域受益，包括生物信息学和计算群论。最后，该研究项目将人工智能和高性能计算相结合，从而为培养这两个领域的学生提供了绝佳的机会。

This project will develop a new approach to scaling up state-space heuristic search based on structured duplicate detection, which leverages graph locality and structure to improve the effciency of duplicate detection. Structured duplicate detection provides a foundation for (a) a new approach to external-memory graph search which aligns the memory hierarchy with the search space, so that for example, only a small fraction of already-explored nodes need to be stored in RAM at any time in order to perform duplicate detection, (b) a new approach to parallel graph search in which an abstract representation of the state space that preserves graph locality is used to partition stored nodes among processors, and (c) a new approach to creating and learning larger and more accurate pattern database heuristics by storing part of the pattern databases on disk and distributing them among multiple processors.The search algorithms developed in this project will be tested on two challenging applications of practical importance: domain-independent planning and explicit-state model checking. But because state-space graph search is a pervasive technique in AI and other branches of computer science, the new techniques developed under this project have the potential to benefit many applications areas, including bioinformatics and computational group theory. Finally, this research project integrates AI and high-performance computing, thus providing an excellent opportunity to train students in both areas.