论文标题
有效的半外部深度优先搜索
Efficient Semi-External Depth-First Search
论文作者
论文摘要
随着图形的尺寸迅速增长，目前几乎无法将许多实际图形加载到主内存中。在半外部内存模型上计算深度优先搜索（DFS）结果，即深度优先或DFS-Tree成为一个热门话题。半外部算法假设主存储器至少可以保持图G的跨越树T，并逐渐将t逐渐重组到非平凡的DFS-Tree中。在本文中，我们介绍了半外部DFS问题的全面研究。基于我们对其主要挑战的理论分析，我们引入了一种新的半外部DFS算法，名为EP-DFS，具有轻量级索引n+index。与传统算法不同，我们专注于有效地解决此类复杂问题的问题，不仅在I/OS的情况下，而且更简单的CPU计算（实现友好型）和更少的随机I/O访问（密钥效率）。在合成图和真实图上进行了广泛的实验评估。实验结果证实，我们的EP-DFS算法显着优于现有算法。
As the sizes of graphs grow rapidly, currently many real-world graphs can hardly be loaded in the main memory. It becomes a hot topic to compute depth-first search (DFS) results, i.e., depth-first order or DFS-Tree, on semi-external memory model. Semi-external algorithms assume the main memory could at least hold a spanning tree T of a graph G, and gradually restructure T into a DFS-Tree, which is non-trivial. In this paper, we present a comprehensive study of semi-external DFS problem. Based on our theoretical analysis of its main challenge, we introduce a new semi-external DFS algorithm, named EP-DFS, with a lightweight index N+-index. Unlike traditional algorithms, we focus on addressing such complex problem efficiently not only with less I/Os, but also with simpler CPU calculation (implementation-friendly) and less random I/O accesses (key-to-efficiency). Extensive experimental evaluation is conducted on both synthetic and real graphs. The experimental results confirm that our EP-DFS algorithm significantly outperforms existing algorithms.
