Dynamic StateSpace Partitioning in ExternalMemory Graph Search

Graph Search Engineering

计算机科学;物理学

Rong Zhou ; Eric A. Hansen

PID  :  82462

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Stateoftheart externalmemory graph search al gorithms rely on a hash function, or equivalently, a statespace projection function, that partitions the stored nodes of the statespace search graph into groups of nodes that are stored as separate files on disk. The scalability and efficiency of the search depends on properties of the partition: whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the statespace graph are partitioned, and how well the partitioning of the state space captures lo cal structure in the graph. All previous work relies on a static partitioning of the state space. In this pa per, we introduce a method for dynamic partition ing of the statespace search graph and show that it leads to substantial improvement of search perfor