Engineering a Topological Sorting Algorithm for Massive Graphs
Engineering a Topological Sorting Algorithm for Massive Graphs
复制标题
设计海量图的拓扑排序算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
N. Zeh
中科院分区：
文献类型：
--
作者：
Deepak Ajwani;Adan Cosgaya;N. Zeh
提出了一种对有向无环图(DAG)进行拓扑排序的I/O高效算法。对于这个问题，目前还没有可证明的I/O高效算法。同样，我们的算法，我们称之为IterTS，在最坏的情况下性能可能很差。然而，我们的实验表明，IterTS在实践中取得了良好的性能。
IterTS的战略可以概括为以下几点。如果一条边的尾部数小于其头部数，我们称其为满意边。满足DAG中至少一半边的编号很容易找到：随机编号应该具有此属性。IterTS从这样的编号开始，然后迭代地更正编号以满足越来越多的边，直到满足所有边。
为了评估IterTS的运行时间，我们将其与三个竞争对手的运行时间进行了比较：PeelTS，迭代删除源和宿的标准策略的I/O高效实现；ReachTS，最近基于可达性查询的并行分治算法的I/O高效实现；以及Sets，基于半外部DFS算法构建的标准DFS拓扑排序。在我们对各种类型的输入图表的评估中，IterTS的表现一直比PeelTS和ReachTS高出至少一个数量级。在顶点集适合内存的大多数图上设置性能优于IterTS。然而，IterTS在这些输入上往往接近集合的运行时间，更重要的是，SET不能处理顶点集超出主存大小的图，而IterTS能够高效地处理此类输入。
We present an I/O-efficient algorithm for topologically sorting directed acyclic graphs (DAGs). No provably I/O-efficient algorithm for this problem is known. Similarly, the performance of our algorithm, which we call IterTS, may be poor in the worst case. However, our experiments show that IterTS achieves good performance in practise.
The strategy of IterTS can be summarized as follows. We call an edge satisfied if its tail has a smaller number than its head. A numbering satisfying at least half the edges in the DAG is easy to find: a random numbering is expected to have this property. IterTS starts with such a numbering and then iteratively corrects the numbering to satisfy more and more edges until all edges are satisfied.
To evaluate IterTS, we compared its running time to those of three competitors: PeelTS, an I/O-efficient implementation of the standard strategy of iteratively removing sources and sinks; ReachTS, an I/O-efficient implementation of a recent parallel divide-and-conquer algorithm based on reachability queries; and SeTS, standard DFS-based topological sorting built on top of a semi-external DFS algorithm. In our evaluation on various types of input graphs, IterTS consistently outperformed PeelTS and ReachTS, by at least an order of magnitude in most cases. SeTS outperformed IterTS on most graphs whose vertex sets fit in memory. However, IterTS often came close to the running time of SeTS on these inputs and, more importantly, SeTS was not able to process graphs whose vertex sets were beyond the size of main memory, while IterTS was able to process such inputs efficiently.