GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
复制标题
DOI：
10.1145/3514221.3526146
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
D. Tench;Evan West;Victor Zhang;M. A. Bender;Abiyaz Chowdhury;J. Dellas;Martín Farach-Colton;Tyler Seip;Kenny Zhang;Abiyaz Chowd-hury
中科院分区：
文献类型：
--
作者：
D. Tench;Evan West;Victor Zhang;M. A. Bender;Abiyaz Chowdhury;J. Dellas;Martín Farach-Colton;Tyler Seip;Kenny Zhang;Abiyaz Chowd-hury
寻找图的连通分支是贯穿计算机科学和工程的一个基本问题。当图非常大时，或者当它们是动态的时，计算连通分量的任务变得更加困难，这意味着边集会随着时间的推移而发生变化，从而受到边插入和删除的影响。计算大型动态图流上的连接组件的一种自然方法是购买足够的RAM来存储整个图。然而，对于非常大的图，图适合RAM的要求是禁止的。因此，对于可以处理密集动态图的系统存在未满足的需求，特别是当这些图大于可用RAM时。我们提出了一个新的高性能流图处理系统计算的连通组件的图。这个系统，我们称之为GraphZeppelin，使用新的线性草图数据结构（CubeSketch）来解决流连接组件问题，因此需要的空间渐近小于图的无损表示所需的空间。GraphZeppelin针对大规模密集图进行了优化：GraphZeppelin每秒可以处理数百万条边更新（包括插入和删除），即使底层图太大而无法容纳可用RAM。因此，GraphZeppelin极大地增加了可以处理的图形的规模。
Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge insertions and deletions. A natural approach to computing the connected components on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GraphZeppelin, uses new linear sketching data structures (CubeSketch) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph. GraphZeppelin is optimized for massive dense graphs: GraphZeppelin can process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GraphZeppelin vastly increases the scale of graphs that can be processed.