Computing Strongly Connected Components in the Streaming Model
Computing Strongly Connected Components in the Streaming Model
复制标题
计算流模型中的强连接组件
DOI：
10.1007/978-3-642-19754-3_20
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Federico Santaroni
中科院分区：
文献类型：
--
作者：
L. Laura;Federico Santaroni
在本文中，我们提出了第一个算法来计算强连接组件的图中的数据流模型（W-流），其中该图是由一个流的边缘，我们被允许产生中间输出流。该算法简单，有效，并且可以用几行代码实现：它查看流中的每条边，并选择关于树T的适当动作，表示到目前为止看到的图连通性。
我们分析了算法的理论性质：正确性，内存占用（O（n log n）），每项处理时间（由当前高度T的范围内），通过（由最大高度T的范围内）。最后，我们提出了一个简短的实验评估的算法对大规模的合成和真实的图形，证实了其有效性：与图形高达1亿个节点和4G的边缘，只需要很少的通行证，每秒处理数百万条边。
In this paper we present the first algorithm to compute the Strongly Connected Components of a graph in the datastream model (W-Stream), where the graph is represented by a stream of edges and we are allowed to produce intermediate output streams. The algorithm is simple, effective, and can be implemented with few lines of code: it looks at each edge in the stream, and selects the appropriate action with respect to a tree T, representing the graph connectivity seen so far.
We analyze the theoretical properties of the algorithm: correctness, memory occupation (O(n log n)), per item processing time (bounded by the current height of T), and number of passes (bounded by the maximal height of T). We conclude by presenting a brief experimental evaluation of the algorithm against massive synthetic and real graphs that confirms its effectiveness: with graphs with up to 100M nodes and 4G edges, only few passes are needed, and millions of edges per second are processed.